What's the efficient way to count duplicates of each pair of a vector?

Question

Is there any efficient way to count duplicates of each pair in a vector? For example, if I have a vector like this:

 vector<pair<int, int> > duplicates={{1,2},{3,2},{2,1},{5,6},{5,6},{1,2},{2,1},{5,6}};

The output should be:

 {1,2}:2
 {3,2}:1
 {2,1}:2
 {5,6}:3

And TO be CLEAR, I am just curious about how to solve this problem more efficiently. I have tried to compare each pair of this vector and it seems not a smart way.

Answer 1

An easy way is to use a map or unordered map to count them:

#include <iostream>
#include <vector>
#include <map>
int main( int argn, char **argc)
{
    std::vector<std::pair<int, int> > duplicates={{1,2},{3,2},{2,1},{5,6},{5,6},{1,2},{2,1},{5,6}};
    std::map<std::pair<int, int>, int> checker;
    for (const auto &elem: duplicates)
    {
        ++checker[elem];
    }

    for (const auto &elem: checker) std::cout << "{" << elem.first.first <<
                                                 "," << elem.first.second <<
                                                 "}: " << elem.second << std::endl;

    return 0;
}

Note that map insertion/recovery is O(log(n)), and the loop around make it aprox. O(n*log(n))

EDIT:

Following the additional note of the OP, here is a better (faster) implementation using unordered_map:

#include <iostream>
#include <vector>
#include <unordered_map>

namespace std
{
template <>
struct hash<std::pair<int,int>>
{
    size_t operator()(pair<int, int> const &p) const
    {
        // Fine for 64bit size_t and 32bit int. Otherwise, some collision may happens.
        size_t result = (static_cast<size_t>(p.first) <<(sizeof(std::size_t)<<2))
                        + static_cast<size_t>(p.second);
        return result;
    }
};
}

int main( int argn, char **argc)
{
    std::vector<std::pair<int, int> > duplicates={{1,2},{3,2},{2,1},{5,6},{5,6},{1,2},{2,1},{5,6}};
    std::unordered_map<std::pair<int, int>, int> checker;
    for (const auto &elem: duplicates)
    {
        ++checker[elem]; // value initialized with 0
    }

    for (const auto &elem: checker) std::cout << "{" << elem.first.first <<
                                                 "," << elem.first.second <<
                                                 "}: " << elem.second << std::endl;

    return 0;
}

Insertion in unordered_map, using a hash make it usually constant (worse case when there are collision is linear). Final complexity in average is O(N)

Answer 2

I have a simple solution:

1. Sort vector of pairs
2. Then just a loop if match consecutive pairs then increase counter

General search Complexity: n*n
This search Complexity: nlog(n)