On Mon, Jan 22, 2007 at 11:36:18PM -0500, Mike Polyakov wrote: > Michael, > > >Why not just use a std::set<int> here? Repeated inserts of the same > >value will be ignored. > > True, but that will use extra memory. Since pointers are iterators, > this can be done on ordinary array in place without extra memory. Only > thing is that unique() function modifies the original array. I have > used back_insert_iterator with extra class to keep track of the number > of unique elements, but now the code is not neat anymore: > I think that std::set<> is the better approach. IIRC, the standard does not mandate how it is implemented, so it is very likely implemented as an array (at least for primitive types). If the set is unordered (that is, you don't expect to get things back out in the same order as you insert them), then the implementation is free to sort the integers as they are inserted. This makes duplicate insertions happen faster than O(N), since the whole thing would start off with a binary search. So, if you plan to have lots of duplicates, this is probably more efficient overall since you plan to find the element already there and the more expensive actual insertion, likely O(N log N), would happen less frequently. Regards, -Roberto -- Roberto C. Sanchez http://people.connexer.com/~roberto http://www.connexer.com
Attachment:
signature.asc
Description: Digital signature