number of distinct elements in a const container and iterating over the distinct elements

Discussion in 'C++' started by Hicham Mouline, Apr 11, 2010.

  1. Hello,
    I have posted this question elsewhere:
    >Given a std::vector<T> and a Compare<T> comparator, how can I:
    >
    > 1. determine the number of different elements in the vector?
    > 2. get iterators to the list of distinct elements in the vector?


    The answer given was:

    >With 2 iterators b and e,
    > std::sort(b, e);
    > m = std::unique(b, e, Compare<T>());
    >Then you have the std::distance(b, m) unique elements available in the
    >range [b, m).


    My question was incomplete.
    1. I wish to keep the container const and it may be unsorted.
    2. I wish to avoid making a copy if possible and would accept a slower
    algorithm if there is one.
    3. Is it possible to then iterate (possibly by writing a new iterator) over
    the distinct elements?

    regards,
     
    Hicham Mouline, Apr 11, 2010
    #1
    1. Advertising

  2. Hicham Mouline

    Kai-Uwe Bux Guest

    Hicham Mouline wrote:

    > Hello,
    > I have posted this question elsewhere:
    >>Given a std::vector<T> and a Compare<T> comparator, how can I:
    >>
    >> 1. determine the number of different elements in the vector?
    >> 2. get iterators to the list of distinct elements in the vector?

    >
    > The answer given was:
    >
    >>With 2 iterators b and e,
    >> std::sort(b, e);
    >> m = std::unique(b, e, Compare<T>());
    >>Then you have the std::distance(b, m) unique elements available in the
    >>range [b, m).

    >
    > My question was incomplete.
    > 1. I wish to keep the container const and it may be unsorted.
    > 2. I wish to avoid making a copy if possible and would accept a slower
    > algorithm if there is one.
    > 3. Is it possible to then iterate (possibly by writing a new iterator)
    > over the distinct elements?


    Sure, with almost the same algorithm as above. You need to introduce yet
    another level of indirection. Use a custom predicate like:

    class ForwardCompare {

    typedef std::vector<T> T_vector;

    T_vector * reference; // point to the original vector

    bool operator() ( T_vector::size_type i, T_vector::size_type j ) const {
    return( Compare<T>()( reference->at(i), reference->at(j) ) );
    }

    };

    Now, you create a vector of indices from 0 to size-1, sort that vector using
    ForwardCompare, make it unique using ForwardCompare and what you end up with
    is a vector containing indices to pairwise Compare<T>-different elements of
    the original vector.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Apr 11, 2010
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Travis L Spencer
    Replies:
    3
    Views:
    382
    Travis L Spencer
    Jan 21, 2005
  2. will
    Replies:
    1
    Views:
    1,170
    Pavel Lepin
    Aug 15, 2007
  3. Javier
    Replies:
    2
    Views:
    621
    James Kanze
    Sep 4, 2007
  4. fungus
    Replies:
    13
    Views:
    946
    fungus
    Oct 31, 2008
  5. Ulrich Eckhardt
    Replies:
    6
    Views:
    365
    Bryan
    May 12, 2010
Loading...

Share This Page