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

[Hicham Mouline]

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,

 

[Kai-Uwe Bux]

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