Here's a working example of O(N log N)
complexity. It first sorts the data, then loops over each element and counts the number occurances by looking for the first mismatch, and then storing the sum of the counts from the current element in a result vector. Note that you can also have counts different from 1 in your initial arrays. The code works without having to specify a specific comparison function because std::array
already has a lexicographic operator<
.
The code below uses C++11 features (auto, lambda) that might not work on your compiler. You might also use initalizer lists to initialize the vector in one statement, but withthe nested vector of pair of int and array, I got a little confused on how many braces I needed to write :-)
#include <algorithm>
#include <array>
#include <iostream>
#include <utility>
#include <vector>
typedef std::pair<int, std::array<char, 3> > Element;
std::vector< Element > v;
std::vector< Element > result;
int main()
{
v.push_back( Element(1, std::array<char, 3>{{'a', 'b', 'c'}}) );
v.push_back( Element(2, std::array<char, 3>{{'a', 'b', 'c'}}) );
v.push_back( Element(1, std::array<char, 3>{{'c', 'd', 'e'}}) );
v.push_back( Element(1, std::array<char, 3>{{'b', 'c', 'd'}}) );
v.push_back( Element(3, std::array<char, 3>{{'b', 'c', 'd'}}) );
// O(N log(N) ) complexity
std::sort(v.begin(), v.end(), [](Element const& e1, Element const& e2){
// compare the array part of the pair<int, array>
return e1.second < e2.second;
});
// O(N) complexity
for (auto it = v.begin(); it != v.end();) {
// find next element
auto last = std::find_if(it, v.end(), [=](Element const& elem){
return it->second != elem.second;
});
// accumulate the counts
auto count = std::accumulate(it, last, 0, [](int sub, Element const& elem) {
return sub + elem.first;
});
// store count in result
result.push_back( Element(count, it->second) );
it = last;
}
for (auto it = result.begin(); it != result.end(); ++it) {
std::cout << it->first << " ";
for (std::size_t i = 0; i < 3; ++i)
std::cout << it->second[i] << " ";
std::cout << "\n";
}
}
Output on Ideone
NOTE: the loop over the sorted elements might seem O(N^2)
(a linear std::find_if
nested inside a linear for
), but it is O(N)
because of the last loop statement it = last
that skips over already searched elements.