Hi.
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).
gcc(g++) uses a red-black tree to represent sets:
template <class _Key, class _Compare, class _Alloc>
class multiset
...
private:
/// @if maint This turns a red-black tree into a [multi]set. @endif
typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
key_compare, _Key_alloc_type> _Rep_type;
/// @if maint The actual tree structure. @endif
_Rep_type _M_t;
...
The _M_t variable above is the multiset itself. This code is in the headers:
bits/stl_set.h
bits/stl_multiset.h
J.
--
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
