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\$
  • \$\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\$ – 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