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

Question

I had found that list::unique() removes only consecutive elements in a list. I would like to know the reason why the method functions like this.

Remove duplicates from a list explains how to remove the duplicate elements from a list but it doesn't explain why just the consecutive elements are only removed.

The following is my test code:

#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++;
}

}

Why is this method list::unique() designed just to remove consecutive duplicate elements in the list?

Answer 1

Design of the standard library follows the approach of providing the user with a comprehensive set of basic, relatively minimalistic algorithmic "building blocks", which, if necessary, can be manually combined into more complex algorithms. Removal of consecutive equivalent elements happens to such minimalistic algorithm. Removal of non-consecutive equivalent elements in a non-ordered sequence is definitely not a minimalistic algorithm. It is not a natural algorithm for a non-ordered sequence.

Typically, in order to achieve the latter in an non-ordered container the user would have to perform sort and then perform unique. Since the library already provides sort and unique as basic "building blocks", there's no need to provide a separate version of unique algorithm that would work with non-adjacent elements. In that sense sort and unique form an idiomatic pair, just like remove_if and erase in the well-known erase–remove idiom.

Also, the problem with implementing non-adjacent unique is that a "clean" implementation of such functionality would call for a non-reordering operation, i.e. repetitive elements should be removed, but the relative order of the remaining elements should remain unchanged. It is not possible to implement such functionality as a minimalistic "building block". And I'd say that there's not much need for it, since in most practical cases the user will either be happy with sort-then-unique combination or use a different container type altogether.

Answer 2

I agree with your premise that the usage of the word unique is not ideal, relative to longer names perhaps as consecutive_unique. "(The weirder the operation, the longer the name should be)" I would not--myself--have thought mere unique a good name for this, using a longer name and then saving the short name for what you would intuit.

So...why? I am reminded of a hypothetical interview with Richard Feynman, regarding the question of "why are manhole covers round". I'll cite this bit:

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.

In this context, the why will come down to: "The people authorized to open manhole covers could easily be trained to do it safely."

Even if a C++ function has the "intuitive" name, that's no protection against its behavior. You must be cognizant of a lot of details to use a library class or function. In a way, it's good to train you to imagine every method or function is called X... so you read to see what X actually promises contractually.