1
\$\begingroup\$

Problem

I need a collection with non-duplicate values minimising memory allocation during access operations. I am prepared to compromise with a slight decrease of performance to make up for the improved "garbage generation".

Solutions Considered (including discarded ones for reference)

  1. Extend ArrayList to include a check on add(E e) for duplicates and do nothing if value exists. (this may include other methods too)
  2. Use HashSet (discarded) - iteration of elements causes instantiation of a new Iterator which defeats the requirement of minimal memory allocation during access.
  3. Convert HashSet to ArrayList (discarded) - creates more memory allocaiton than HashSet iteration.

Question

Is the extention of ArrayList to reject duplicate values a sensible way to achieve non-duplicate collection with minimal memory allocation? Are there alternative methods I should consider?

Notes

Most advised solutions to eliminate duplicates in ArrayList I have seen refer to using HashSet or other object instantiation which defeat my minimal memory allocation requirement. The only implementation I can think of is a basic "for iteration" of the ArrayList checking equality of the added value against each existing element.

Class NonDuplicateList extends ArrayList{
    @Override
    boolean add(E e){
        for(int i = 0; i < this.size(); i++){
            if(this.get(i).equals(e)
                return false;
        }
        return super.add(e);
    }
}

For completion this question is being posted on gamedev stackexchange as the game dev community is more sensitive to the subjects of memory allocation and garbage collection impact, so hopefully I won't get comments along the lines of iterator allocation memory allocation is insignificant :-)

\$\endgroup\$

closed as off-topic by Almo, Alexandre Vaillancourt Feb 20 at 17:03

  • This question does not appear to be about game development within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ How relevant are performance and memory allocation for add and delete operations? When they aren't that important, then I might have a suggestion. \$\endgroup\$ – Philipp Feb 20 at 16:32
  • 2
    \$\begingroup\$ I'm voting to close this question because it is cross-posted on StackOverflow. Cross-posting is not allowed on StackExchange sites. If you decide to delete the other question, we could reopen this one. \$\endgroup\$ – Alexandre Vaillancourt Feb 20 at 17:03
  • \$\begingroup\$ Thanks - this can be closed or even deleted as StackOverflow is more appropriate for this question. \$\endgroup\$ – Adunato Feb 21 at 12:09