Обнаружение равных элементов в std :: list - PullRequest
Новая
       52

Обнаружение равных элементов в std :: list

1 голос
/ 08 января 2020

Есть ли лучший способ найти элементы списка std :: list, которые имеют то же значение, что и ручной просмотр отсортированного списка и сравнить каждый элемент следующим образом: 

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

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

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

Ответы [ 3 ]

3 голосов
/ 08 января 2020

На самом деле существует действительно хороший и компактный способ получить список всех дубликатов в наборе данных, независимо от того, отсортированы они или нет. Что мы можем сделать, это использовать std::map / std::unordered_map и использовать значение элементов в качестве ключа для карты, а также сделать значение счетчиком числа раз, когда это значение было «вставлено». Это выглядело бы как 

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

, и тогда все, что вам нужно было бы сделать, это выполнить итерацию карты и проверить записи, у которых сопоставленное значение больше 1. Это выглядело бы как 

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

Используя std::map это O(NlogN + M) и unoredered_map это O(N + M), где N это размер l и M это размер histogram.

2 голосов
/ 08 января 2020

Использовать алгоритм STL adjacent_find: 

auto it = l.begin()
while((it = std::adjacent_find(it, l.end())) != l.end()){
  std::cout << "Equal\n";
  ++it;
}
0 голосов
/ 08 января 2020

Поскольку вы говорите, что список отсортирован, то std::adjacent_find определит, есть ли дубликаты: 

#include <algorithm>

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

Если вы будете sh делать что-то со всеми дубликатами, то мы можем l oop по парам: 

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)
}

Возможно, мы хотим найти и обработать все группы идентичных элементов вместе: 

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());
}
...