Re: count_unique or unique_count - why does it not exist?
Stephen Howe ha scritto:
Hi
Consider a sequence container that is sorted by some criteria
I am surprised that there is not a count_unique() (or unique_count()) that
counts between a range of iterators, considering duplicate elements as 1
element. I don't see that I can use count_if() as that would mean a
predicate with a state.
Or is there? Have I overlooked an algorithm in the C++ library?
The relationship between count() and count_unique() would be analogous to
the SQL aggregate functions:
COUNT(somefield) and COUNT(DISTINCT somefield)
There is no count_unique() algorithm because there are several ways to
implement it, with very different memory requirements, computational
complexity and pre-conditions. It's not very smart to think about having
some general-purpose algorithm for that. Moreover, using creatively
other STL algorithms and containers as building-blocks, it's easy to
obtain the desired result. For example, you could use a set:
template <class InputIterator>
size_t count_unique(InputIterator first, InputIterator last)
{
typedef typename InputIterator::value_type value_type;
return std::set<value_type>(v.begin(), v.end()).size();
}
This is especially effective if you expect a lot of repetitions in the
input range. If, on the other hand you expect very few repetitions and
the elements are very cheap to copy, you could copy everything in a
std::vector, then use std::sort and std::unique.
If the input is already sorted, an exotic but effective solution could
be to define a dummy "counting iterator" that simply increments a
counter each time you assign something to it and then use unique_copy.
In practice:
class counting_iterator
: public std::iterator<std::output_iterator_tag, void, void, void, void>
{
public:
counting_iterator() : count_(0) {}
operator size_t () const { return count_; }
template <typename T>
counting_iterator& operator=(const T&) { return *this; }
counting_iterator& operator*() { return *this; }
counting_iterator& operator++() { ++count_; return *this; }
counting_iterator& operator++(int) { ++count_; return *this; }
private:
size_t count_;
};
template <class InputIterator>
size_t count_unique(InputIterator first, InputIterator last)
{
return std::unique_copy(v.begin(), v.end(), counting_iterator());
}
If you also need the elements then it's silly to have an algorithm that
returns just the count. Simply produce the elements in some container (a
set or a sorted vector+unique) and then use size().
HTH,
Ganesh
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]