CODEWITHSUNDEEP
c++stdlist
user11914177
user11914177

Reputation: 955

Detect equal elements in a std::list

Is there a better way of finding elements of a std::list that have the same value as manually going over the sorted list and comparing each element like this:

for(auto it = l.begin(); it != l.end(); it++) {
        auto nextElement = it;
        nextElement++;

        if(nextElement == l.end())
            break;

        if(*it == *nextElement)
            cout << "Equal" << endl;
}

Upvotes: 0

Views: 1187

Answers (3)

Toby Speight
Toby Speight

Reputation: 30762

Since you say the list is sorted, then std::adjacent_find will detect whether there are duplicates:

#include <algorithm>

if (std::adjacent_find(l.begin(), l.end()) != l.end()) {
    // we have at least one duplicate
}

If you wish to do something with all the duplicates, then we can loop over the pairs:

for (auto it = std::adjacent_find(l.begin(), l.end());
          it != l.end();
          it = std::adjacent_find(std::next(it), l.end())
{
    // *it and *std::next are duplicates (and there may be more)
}

It's possible that we want to find and process all of each group of identical elements together:

auto begin = std::adjacent_find(l.begin(), l.end());
while (begin != l.end()) {
    auto end = std::find_if_not(begin, l.end(),
                                [begin](auto n){ return n == *begin;});

    // All elements from begin (inclusive) to end (exclusive) are equal.
    // Process them here.

    begin = std::adjacent_find(end, l.end());
}

Upvotes: 0

n314159
n314159

Reputation: 5075

Use the STL algorithm adjacent_find:

auto it = l.begin()
while((it = std::adjacent_find(it, l.end())) != l.end()){
  std::cout << "Equal\n";
  ++it;
}

Upvotes: 1

NathanOliver
NathanOliver

Reputation: 180500

There is actually a really nice and compact way to get a list of all of the duplicates in a set of data, whether it is sorted or not. What we can do is leverage std::map/std::unordered_map and use the elements value as the key for the map, and make the value a count of the number of times that value was "inserted". That would look like

std::unordered_map<int, int> histogram;
for (auto e : l)
    ++histogram[e]; // gets a count of the number of duplicates

and then all you need to do is iterate the map and check for entries that have a mapped value greater than 1. That would look like

for (const auto& pair : histogram)
    if (pair.second > 1)
        std::cout << "value: " << pair.first << " has " << pair.second << " matches.\n";

Using a std::map this is O(NlogN + M) and using an unoredered_map this is O(N + M) where N is the size of l and M is the size of histogram.

Upvotes: 3

Related Questions