检测 std::list 中的相等元素

Question

是否有更好的方法来查找 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;
}

Answer 1

使用STL算法adjacent_find:

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

Answer 2

实际上有一种非常好的和紧凑的方法来获取一组数据中所有重复项的列表，无论它是否排序。我们可以做的是利用 std::map/std::unordered_map 并使用元素值作为地图的键，并使该值成为该值 "inserted" 的次数。看起来像

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 的大小。

Answer 3

既然你说列表是排序的，那么std::adjacent_find会检测是否有重复：

#include <algorithm>

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

如果您想对所有重复项进行处理，那么我们可以遍历这些对：

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

检测 std::list 中的相等元素

Detect equal elements in a std::list

c++

stdlist