Re: count_unique or unique_count - why does it not exist?

Stephen Howe ha scritto:


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! ]