this is really a reply to Mike: On Tue, Jan 23, 2007 at 06:01:34AM -0500, Roberto C. Sanchez wrote: > 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. > Mike,
Roberto says several true things, but is perhaps too polite about your misunderstandings of the STL. Here are some things of which you should be aware: std::set<int> does _not_ waste memory. You should use setname.insert( avalue ) to insert avalue into setname. It succeeds only if avalue is not already in the set. You should use setname.size() to learn how many unique values there are. You cannot learn from any memberfunction of set<int> how many times you tried to insert values that were already in the container. Only unique values are kept in a STL set. The STL standard requires that operations be completed by algorithms that meet stated complexity bounds, expressed in big-O notation. The big-O constraints on the set<T> containers pretty much dictate that red-black trees be used for the implementation. Internally, the elements of a STL set must be ordered, and there is a way for the user to define a special version of 'less()' for sets of complicated abstract data types. For int, the standard operator< is quite sufficient. If you interate through a set<int> you will find that the values always are returned in ascending order, regardless of the order in which they were inserted. If they are not in ascending order, you are using a very strange and suspect implementation of STL. The only reason for _not_ using std::set<int> is that you can't, for some reason, gain legal access to a good implementation. But Debian has solved this problem for you. Nicolai M. Josuttis, The C++ Standard Library, covers all this and much more. It is expensive, but perhaps you can find a copy at a nearby university library. HTH -- Paul E Condon [EMAIL PROTECTED] -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
