std::set<int> does _not_ waste memory.
Paul,
Yes, but I didn't say it wasted memory. I said it would use extra
memory, since the original problem was posed as finding unique values
in an array, I assume you are given an array of values up front with
which to work with. In this case, inserting all those items into an
extra set data structure will use extra memory (it will allocate it
dynamically with inserts). What I presented works with the original
array given to you without using other unnecessary data structures.
The only time you might wish to use a set in this case if you don't
want the original array to be modified, since it is sorted in the
process.
By the way, does the standard ask for O(log N) insertions, or
amortized O(log N) insertions, in which case Splay trees, AVL trees,
skip lists, or hashes could provide a valid implementation
alternative?
And The C++ Standard Library book by Nicolai M. Josuttis is very good
indeed, and I own it and have read through it.
-Mike
--
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
