Re: help with C algorythm (find unique value in an array) could you please make changes

[Jeronimo Pellegrini <pellegrini@mpcnet.com.br>]

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.