How to find duplicate elements' index in C++?

Question

Is there any STL function in C++ that allows me to find all indices of duplicates in an array?

For eg:

int array[] = {1,1,2,3,4};

Should return 0,1

Answer 1

Efficiently, you could use a std::unordered_set(to uniquely keep track of duplicate indices) and std::unordered_map(to keep track of unique numbers and their indices).

This does it in O(N * [O(1) + ... + O(1)]) ...approximately = O(N):

template<typename ForwardIterator>
std::vector<int> get_duplicate_indices(ForwardIterator first, ForwardIterator last){
    std::unordered_set<int> rtn;
    std::unordered_map<int, int> dup;
    for(std::size_t i = 0; first != last; ++i, ++first){
        auto iter_pair = dup.insert(std::make_pair(*first, i));
        if(!iter_pair.second){
            rtn.insert(iter_pair.first->second);
            rtn.insert(i);
        }
    }
    return {rtn.begin(), rtn.end()};
}

Explanation:

Given an array A

• Using a set of unique indices, rtn.

• Using a KV (Key-Value) map, dup; where k is an element in the array A, and v is the index of that element in the array.

• For Each item, a with index i in the array:

  • find kv if a exists as k in dup
  • If it exists,
    • Insert i into rtn
    • Insert v into rtn
  • Else, add a and i as kv into dup
• return rtn

See a full example: Live on Coliru.

---

For an input of:

int array[] = {1,1,2,3,4};

We have an output of:

1 0

Again,

For an input of:

int array[] = {1, 1, 2, 3, 4, 1, 0, 0, 9};

We have an output of:

7 0 5 1 6

If you need the indices in order, you could simply sort the resulting array.