如何在C++中从列表中删除一对重复出现的元素？（保留仅出现一次的元素）

Question

我尝试使用unique，但是unique只会移除重复项。

我的程序应该这样做，例如列表包含1,2,2,2,3,4,4。我应该只删除重复的数字对，输出应该是1,2,3（删除了一对2和4）。

- lily

---

如果列表包含1,2,3,2,4,2,4，输出应该是1,2,3,2,4,2,4还是1,2,3？ - johnchen902

它应该是1、2、3。列表首先被排序。 - lily

Answer 1

遍历数据并删除成对的元素 (示例代码):

list<int> data{1, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 6};

for (auto i = data.begin(); i != data.end();)
{
    auto n = std::next(i);

    if (n == data.end())
        break;

    if (*i == *n)
    {
        i = data.erase(i);
        i = data.erase(i);
    }
    else
        i++;
}

输出

1 2 3 4 5 6 

对于 1 2 2 2 3 4 4，使用 1 2 3 来代替。

以上代码适用于 C++11 及以上版本，如果您没有此版本，请尝试以下代码：

for (list<int>::iterator i = data.begin(); i != data.end();)
{
    list<int>::iterator n = i; 
    n++;

    if (n == data.end())
        break;

    if (*i == *n)
    {
        i = data.erase(i);
        i = data.erase(i);
    }
    else
    i++;
}

- masoud

---

我收到了一个错误，说“next”不是“std”的成员。你有什么线索吗？ - lily

Answer 2

我建议使用sort和unique函数来完成这个任务。

std::sort (my_vector.begin(), my_vector.end() );
std::vector<int>::iterator it;
it = std::unique (my_vector.begin(), my_vector.end() );
my_vector.resize( std::distance(my_vector.begin(),it) );

参考资料: http://www.cplusplus.com/reference/algorithm/unique/ -- 这里有一个例子，您可以使用谓词比较来自定义unique的行为。

编辑-- 如果您想要删除连续的元素，则可以查看std::adjacent_find。

编辑-- 如果您只关心删除连续的元素，则首先对列表进行排序，然后迭代它。如果两个元素是连续的，则使用std::remove_if或类似方法删除它们。

- Bill

---

std::unique 可以使用 predicate 函数进行修改，以满足您的自定义需求 :) 我只是举了一个例子。 - Bill

我已经尝试了adjacent_find，如果列表中连续包含相同的数字，例如1,2,2,2,3...它会删除所有的2。我的要求是只删除一对2。 - lily

Answer 3

如果您能想出一个不在列表中的哨兵值，这里有一种稍微更通用的处理此问题的方法。作为一个附带好处，这可能在向量上工作得更好，因为vector::erase非常慢。

#include <cassert>
#include <vector>
#include <iterator>
#include <iostream>
#include <algorithm>

template <class ITR>
void replace_pairs_with_sentinel(ITR begin, ITR end,
    const typename std::iterator_traits<ITR>::value_type& sentinel)
{
    // handle empty sequence
    if ( begin == end ) return;

    // ensure no sentinel values exist
    assert ( std::find(begin, end, sentinel) == end );

    ITR prev = begin++;
    while ( begin != end ) {
        if ( *begin == *prev ) {
            *prev = *begin = sentinel;
        }
        prev = begin++;
    }
}

int main (int argc, char* argv[])
{
    int data[] = {1, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 6};
    std::vector<int> v( data, data + sizeof(data) / sizeof(int) );

    replace_pairs_with_sentinel( v.begin(), v.end(), -INT_MAX );
    std::vector<int>::iterator end_itr = std::remove( v.begin(), v.end(), -INT_MAX );
    v.resize( end_itr - v.begin() );
    std::copy( v.begin(), v.end(), std::ostream_iterator<int>( std::cout, " " ) );
    return 0;
}

- MarkB

---

这对于std::list将可以正常工作。这种方法要求容器已经排序，但是您说这个假设是成立的。 - MarkB

Answer 4

你可以轻松地遍历列表。获取第一个项目并搜索其他项目以查找精确匹配项，如果找到任何匹配项，则删除两者。当循环结束时，您应该有一个不包含任何对的列表。

- Semih Yagcioglu