Counting number of unique elements in a sorted container

Similar to this question, but in C++. Although my priority is performance (and correctness!) rather than readability.

#include <algorithm>
#include <iterator>
#include <cstddef>

template <typename Container>
size_t count_unique(const Container& elements)
{
size_t result {};

for (auto it = std::cbegin(elements), last = std::cend(elements); it != last;) {
++result;
it = std::upper_bound(it, last, *it);
}

return result;
}

• You can special case for already unique sorted containers to the size of the container. – Martin York Jan 8 '16 at 20:59
• Have you tested your implementation against a naive one for an exemplary data set? Can you provide some example data? – MikeMB Jan 9 '16 at 1:23
• @MikeMB I have now! See my answer... – Daniel Jan 9 '16 at 23:50

4 Answers

Worst case is $O(n \log n)$

If we pass an array of completely unique elements, we get a pretty bad runtime. Your solution is good if we expect a lot of duplicates, but bad if we don't.

As an optimization for the worst case, we could add some exponential bounding to find the next element. Basically, replace

it = std::upper_bound(it, last, *it);


with:

std::ptrdiff_t bound = 1;
while (std::distance(it, last) < bound && *std::next(it, bound) == *it) {
bound *= 2;
}

it = std::upper_bound(
std::next(it, bound/2),
std::next(it, std::min(bound, std::distance(it, last))),
*it);


Of course is now pretty bad for non-random access iterators since we have to keep doing lots of distance and advance related calls, so I would simply default to the trivial comparison algorithm in that case. That is:

template <class C>
size_t count_unique(C const& container) {
using It = decltype(std::cbegin(container));
return count_unique(container, std::iterator_traits<It>::iterator_category{});
}

template <class C>
size_t count_unique(C const& container, std::random_access_iterator_tag ) {
// what I suggested
}

template <class C>
size_t count_unique(C const& container, std::forward_iterator_tag ) {
auto first = std::cbegin(container), last = std::cend(container);
if (first == last) return 0;

size_t count = 1;
for (auto next = std::next(first); next != last; ++first, ++next)
{
count += !(*next == *first);
}
return count;
}


Additional Requirements

The binary-search optimization requires that the type the container holds is ordered. You may want to fallback to the simple forward-iterator version if the type is only equality-comparable but not less-than-comparable.

Initialization

I would prefer:

size_t result = 0;


to

size_t result {};


No reason to hide the 0.

Taking on board the answers and comments, I did some benchmarking against other algorithms. It turns out, given a simple probabilistic model for sequence generation (Markov chain with 'switch' probability p), the naive algorithm is better than my algorithm, and a 'mixed' algorithm, similar to the one suggested by Barry, but instead of an absolute cutoff, it keeps track of the longest run seen so far (this type of thing is quite common for statically optimal strategies), and then does a binary search up to a maximum distance of this value past the current position, and then reverts to the naive algorithm if this fails. I haven't proven this is the statistically optimal algorithm for this model.

Here is all the code:

#include <vector>
#include <list>
#include <deque>
#include <iostream>
#include <cstddef>
#include <iterator>
#include <algorithm>
#include <utility>
#include <random>
#include <chrono>

// testing

template <typename Container>
Container generate_samples(const size_t num_samples, const double prob_unique)
{
Container result(num_samples);

static std::default_random_engine gen {};

std::uniform_real_distribution<double> dist {};

typename Container::value_type value {};

std::generate_n(std::begin(result), num_samples,
[prob_unique, &value, &dist] () {
if (dist(gen) > prob_unique) {
return value++;
}
return value;
});

return result;
}

template <typename Container>
std::vector<Container> generate_n_samples(const size_t n, const size_t num_samples,
const double prob_unique)
{
std::vector<Container> result {};
result.reserve(n);

std::generate_n(std::back_inserter(result), n,
[=] () {
return generate_samples<Container>(num_samples, prob_unique);
});

return result;
}

template <typename D = std::chrono::milliseconds, typename Container, typename F>
std::pair<size_t, unsigned> benchmark(const std::vector<Container>& samples, F f)
{
size_t total_unique {0};

const auto start = std::chrono::system_clock::now();

for (const auto& s : samples) {
total_unique += f(s);
}

const auto end = std::chrono::system_clock::now();

const auto total_time = static_cast<unsigned>(std::chrono::duration_cast<D>(end - start).count());

return std::make_pair(total_unique, total_time);
}

// algorithms

template <typename Container>
size_t count_unique_naive(const Container& elements)
{
size_t result {0};

using ValueType = typename Container::value_type;

for (auto it = std::cbegin(elements), last = std::cend(elements); it != last; ++result) {
it = std::find_if_not(std::next(it), last, [=] (const auto& x) { return x == *it; });
}

return result;
}

template <typename Container>
size_t count_unique_bsearch(const Container& elements)
{
size_t result {0};

for (auto it = std::cbegin(elements), last = std::cend(elements); it != last; ++result) {
it = std::upper_bound(it, last, *it);
}

return result;
}

template <typename Container>
size_t count_unique_mix(const Container& elements)
{
size_t result {0};

size_t longest_run_length {0};

auto num_elements_remaining = elements.size();

using ValueType = typename Container::value_type;

for (auto it = std::cbegin(elements), last = std::cend(elements); it != last; ++result) {
const auto bound = std::next(it, std::min(longest_run_length, num_elements_remaining));

auto it2 = std::upper_bound(it, bound, *it);

if (bound != last && it2 == bound && *it == *bound) {
it2 = std::find_if_not(std::next(it2), last, [=] (const auto& x) { return x == *it; });
}

const auto curr_run_length = static_cast<size_t>(std::distance(it, it2)); // always positive

num_elements_remaining -= curr_run_length;

longest_run_length = std::max(longest_run_length, curr_run_length);

it = it2;
}

return result;
}

int main()
{
using Container = std::vector<unsigned>;

const size_t num_samples {100};
const size_t num_elements_per_sample {10000000};
const double prob_unique {0.92};

const auto samples = generate_n_samples<Container>(num_samples, num_elements_per_sample, prob_unique);

using Duration = std::chrono::milliseconds;

const auto r1 = benchmark<Duration>(samples, [] (const auto& s) { return count_unique_naive(s); });
const auto r2 = benchmark<Duration>(samples, [] (const auto& s) { return count_unique_bsearch(s); });
const auto r3 = benchmark<Duration>(samples, [] (const auto& s) { return count_unique_mix(s); });

std::cout << "count_unique_naive   : Total num unique = " << r1.first << ". Time taken = " << r1.second << std::endl;
std::cout << "count_unique_bsearch : Total num unique = " << r2.first << ". Time taken = " << r2.second << std::endl;
std::cout << "count_unique_mix     : Total num unique = " << r3.first << ". Time taken = " << r3.second << std::endl;

return 0;
}


Compile with:

g++ count_unique.cpp -std=c++14 -O3 -o count-unique


On my machine, with the other variables the same as in the given code, count_unique_mix is only better than count_unique_naive for prob_different approx > 0.95, and count_unique_bsearch is only better than count_unique_mix when prob_different is very close to 1.

• Nice answer! Testing on my machine using g++ version 5.3.1 on a 64-bit Linux box shows my std::accumulate based version faster than all three of these. Can you test? – Edward Jan 9 '16 at 22:17
• Well, generate_samples has a static local. Also, it zero-initializes before overwriting it. You could use boost::counting_iterator and boost::transform_iterator to fix that, but I doubt it's worth bothering for the test-harness. The early exit for the lambda in it doesn't really make things more readable either. I also wonder why you add a default to the first template-parameter of benchmark and then don't use it. All in all, I concurr with Edward. – Deduplicator Jan 9 '16 at 22:50
• @Edward Your algorithm does indeed appear to be fastest for most cases, but gives different results to the other three algorithms. – Daniel Jan 9 '16 at 23:25
• Yes, I think something is awry with it but have yet to pinpoint the problem. – Edward Jan 10 '16 at 1:35
• Almost tempted to vote down a perfectly valid answer to have this one come out tops ;-/ – greybeard Jan 10 '16 at 5:43

The other answers have addressed most issues, but I wanted to expand on one, which is that while the container is sorted, the sort ordering is not necessarily ascending. The result is that the only valid comparison is == rather than < which is what std::upper_bound implicitly uses.

Here is test code to demonstrate the problem:

int main()
{
std::vector<std::complex<float>> v1{2, 3, 8, 8, 10, 10, 10, 16, 18, 19};
const std::vector<int> v2{2, 3, 8, 8, 10, 10, 10, 16, 18, 19};
std::list<std::string> v3{"one", "one", "two", "three", "four", "four"};
std::list<std::string> v4{"four", "five", "six"};
std::list<std::string> v5{};

assert(count_unique(v1) == 7);
assert(count_unique(v2) == 7);
assert(count_unique(v3) == 4);
assert(count_unique(v4) == 3);
assert(count_unique(v5) == 0);
}


As you can verify, the tests for the std::complex vector and the two std::string lists fail because std::complex does not implement operator< and because although std::string does, it's not the ordering that was used to sort the containers.

While we could fix that with your original code, I thought it might be thought-provoking to provide an alternative implementation that both addresses that problem and also abuses std::accumulate to do our counting.

template <typename container>
size_t count_unique(const container& v)
{
if (v.cbegin() == v.cend()) return 0;
auto &first = *(v.cbegin());
auto lambda = [&first](size_t a, const auto &b){
static const auto *prev = &first;
if (*prev != b) ++a;
prev = &b;
return a;
};
return std::accumulate(++v.cbegin(), v.cend(), 1, lambda);
}


If you are OK with the empty set returning a value of 1 (and there may be some mathematical justification for that, even though the cardinality of an empty set is usually understood as being 0), then you can eliminate the first line containing the early bailout.

• (See Barry's Additional Requirements) There, there's std::equal_range - "suffering" from the same "top-down-approach" to the boundary, and wasting energy on the left boundary. Annoyed that I can't seem to find a "doubling-then-halfing-probe-distance" search for equal_range or similar. – greybeard Jan 9 '16 at 20:15
• Yes, @Barry got one part of the problem (no operator<) but not the other part which is that that wasn't necessarily the operator used to sort the container. It would be interesting to try to reimplement std::equal_range that incorporated a binary search. A really smart implementation might choose algorithms based on container size. – Edward Jan 9 '16 at 20:20
• … choose algorithms based on container size - and expected distance to the boundary: if closer than sqrt(tail_len) doubling should be faster, otherwise binary search is just fine. Wait - what about choosing the factor for the "increase probing distance phase" based on expected ratio of tail to boundary … – greybeard Jan 9 '16 at 20:44
• :D Eagerly awaiting your implementation. – Edward Jan 9 '16 at 21:29
• You know, that static variable is a really bad idea... still, otherwise good, so upvoted. – Deduplicator Jan 9 '16 at 22:13

I'm not sure how generic you aim to be, but suppose the elements in the container are (positive) integers. Now, especially if you expect the container to be dense, you could also compute a histogram of the elements. Consider the following:

template <typename Container>
size_t count_unique_dense(const Container& elements)
{
assert(std::is_sorted(elements.cbegin(), elements.cend()));

const auto max = elements.back() + 1;
std::vector<Container::value_type> hist(max);

for (auto it = elements.cbegin(), end = elements.cend(); it != end; ++it)
++hist[*it];

return std::count(hist.cbegin(), hist.cend(), 1);
}


Since you only care about uniqueness (and not occurrence count), you could push the idea further as well by using less space per histogram entry.

For simplicity, I'm skipping the details of making this generic (I'm assuming the container is really say a vector). So this is only an algorithmic idea that will be fast in certain cases. It is also a bit unnecessary for this particular algorithm to assume the input is sorted; we could also just find the maximum element first, and then proceed (but this assumption should make things run faster, and be more cache friendly).