[Boost-users] Distinct elements in a std::vector<T>

Subject: [Boost-users] Distinct elements in a std::vector<T>
From: Hicham Mouline (hicham_at_[hidden])
Date: 2010-04-10 17:22:50

Hello,

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?

My naive implementation for 1 is:
/// v is const-ref to a std::vector<T>
std::vector<T>::size_type distinct = v.empty()? 0: 1;
std::vector<T>::const_iterator j;
for (std::vector<T>::const_iterator i = v.begin()+1; i!=v.end(); ++i)
{
  j = std::find(v.begin(), i, *i, Compare<T>());
  if (j!=i)
    ++distinct;
}

Obviously, this is of worst order n*(n+1)/2. I'm sure a better order can be
achieved.
I don't quite see how to do 2.

Does anything in the C++ std lib or boost facilitate this?

Regards,