为什么 list::unique 在 C++ 中只删除连续的元素？

Question

我发现 list::unique() 只删除列表中连续的元素。我想知道为什么这个方法会这样。

Remove duplicates from a list 解释了如何从列表中删除重复的元素，但没有解释为什么只删除连续的元素。

以下是我的测试代码：

#include <algorithm>
#include <iostream>
#include <list>
#include <string>
#include <utility>

using namespace std;

void print_message( const pair<int,string>& message )
{
    cout << message.first << " - " << message.second << endl;
}

int main( )
{
list< pair< int, string > > message;
list< pair< int, string > >::iterator ip;

message.push_back( make_pair( 1, string("Test Foo One")) );
message.push_back( make_pair( 1, string("Test Foo Two")) );
message.push_back( make_pair( 1, string("Test Foo Two")) );
message.push_back( make_pair( 1, string("Test Foo Three" )) );
message.push_back( make_pair( 1, string("Test Foo Two" )));
message.push_back( make_pair( 1, string("Test Foo Two")) );

cout << "ORIGINAL MESSAGES" << endl;
ip = message.begin();
while(ip!=message.end()) {
        print_message(*ip);
        ip++;
}

message.unique();
cout << "\nSEQUENTIAL DUPLICATES REMOVED" << endl;
ip = message.begin();
while(ip!=message.end()) {
        print_message(*ip);
        ip++;
}

}

为什么这个方法list::unique()只是为了删除列表中连续的重复元素而设计的？

Answer 1

标准库的设计遵循为用户提供一套全面的基本、相对简约的算法的方法 "building blocks"，如有必要，可以将其手动组合成更复杂的算法。这种极简算法恰好删除了连续的等价元素。去除无序序列中不连续的等价元素绝对不是极简算法。它不是无序序列的自然算法。

通常，为了在未排序的容器中实现后者，用户必须先执行 sort，然后再执行 unique。由于该库已经提供 sort 和 unique 作为基本 "building blocks"，因此无需提供单独版本的 unique 算法来处理非相邻元素。从这个意义上说，sort 和 unique 形成了一对惯用语，就像著名的 erase–remove idiom.

中的 remove_if 和 erase 一样

此外，实现非相邻 unique 的问题在于 "clean" 实现此类功能将需要非重新排序操作，即应删除重复元素，但相对其余元素的顺序应保持不变。不可能实现像简约 "building block" 这样的功能。而且我会说没有太多需要它，因为在大多数实际情况下，用户要么对 sort-then-unique 组合感到满意，要么完全使用不同的容器类型。

Answer 2

我同意你的前提，即单词 unique 的用法并不理想，相对于较长的名称，例如 consecutive_unique。 "（操作越奇怪，名称就应该越长）" 我自己不会认为只是 unique 一个好名字，使用更长的时间名称，然后根据您的直觉保存短名称。

那么……为什么？关于"why are manhole covers round"的问题，我想起了一个hypothetical interview with Richard Feynman。我将引用这一点：

Interviewer: Do you believe there is a safety issue? I mean, couldn't square covers fall into the hole and hurt someone?

Feynman: Not likely. Square covers are sometimes used on prefabricated vaults where the access passage is also square. The cover is larger than the passage, and sits on a ledge that supports it along the entire perimeter. The covers are usually made of solid metal and are very heavy. Let's assume a two-foot square opening and a ledge width of 1-1/2 inches. In order to get it to fall in, you would have to lift one side of the cover, then rotate it 30 degrees so that the cover would clear the ledge, and then tilt the cover up nearly 45 degrees from horizontal before the center of gravity would shift enough for it to fall in. Yes, it's possible, but very unlikely. The people authorized to open manhole covers could easily be trained to do it safely.

在这种情况下，原因将归结为："The people authorized to open manhole covers could easily be trained to do it safely."

即使 C++ 函数具有 "intuitive" 名称，也无法防止其行为。您必须了解很多细节才能使用库 class 或函数。在某种程度上，训练你想象每个方法或函数都被称为 X 是很好的……所以你阅读以了解 X 在合同中实际承诺了什么。

为什么 list::unique 在 C++ 中只删除连续的元素？

Why list::unique removes only consecutive elements in C++?

c++

generic-programming