1. The associated container implements its own comparison type

We often define a container.

vector<int> vec;

In fact, this is the abbreviation of the following function.

vector<int, less<int>> vec;

vector<int, less<int>, allocator<int>> vec;

It is only the default. The default size comparison function and distribution are specified in the container. Of course, this is mainly for associated containers, because sequence containers are sequential.

However, if we store pointers in the container and have certain order requirements for the output, the default comparison function may not meet our needs. If we use the default less type, we compare the size of the pointer, not the size of the memory pointed to by the pointer.

Take string * as an example. Assuming that we can output according to the size of the string when we need to output, we need to create a comparison type for comparing strings.

struct StringPtrLess : public binary_function<const string*, const string*, bool>
 {    
    bool operator()(const string* p1, const string* p2)
    {
        return *p1 < *p2;
    }
}

Using the StringPtrLess above, we can use it as the comparison type of the container:

typedef set<string*, StringPtrLess> StringPtrSet;

StringPtrSet sp;

for(StringPtrSet::const_iterator iter = sp.bengin(); iter != sp.end(); ++iter)
{
    cout << **iter << endl;
}

The above print function for each element needs to dereference the pointer once, which is easy to ignore in our daily life. Therefore, for this problem, we can dereference the pointer in advance.

void print(const string* p)
{
    count << *p << endl;
}

for_each(sp.bengin(), sp.end(); print);

Alternatively, we can write a generic dereference type for use with the transform function.

struct Dereference{
    template<typename T> const T& operator(const T* ptr) const
    {
        return *ptr;
    }  
};

transform(sp.bengin(), sp.end(), ostream_iterator<string>(cout, "\n"), Dereference())

In the above example, we have written customized comparison types. It is mainly applicable to associated containers whose elements are pointers, references, iterators, etc. Because the default comparison type will be stored according to the size of the pointer, rather than the actual memory size pointed to by the pointer.

But why not use a comparison function directly? And be sure to compare types.

bool stringLess(const string* p1, const string* p2)
{
    return *p1 < *p2;
}

typedef set<string*, stringLess> StringSet; 

The above code cannot be compiled. This is mainly because the three parameters of the set template are types, not simple functions.

Let's push generalization from a special case.

struct DereferenceLess
 {
    template<typename T> bool operator()(const T p1, const T p2)
    {
        return *p1 < *p2;
    }
}

2. The comparison function must return false when it is equivalent

This clause is only useful when you manually implement the comparison type. If you choose to use the default less as the comparison function, you don't have to take special consideration.

set<int, less_equal<int>> s;
s.insert(10);

In the above example, we first created a collection container whose element is of type int, and specified that the elements are sorted with "< =". Then insert 10 into the container; Next, we continue to insert 10 into the container; That is, execute the following code:

s.insert(10);

What will happen?

According to our normal thinking and experience, this line of code will fail to execute, and elements with the same value will not be inserted into the container. Because our default set is created like this.

set<int> s;

The sorting method is not specified, that is, it is sorted by less by default.

But what about the reality?

In the second attempt to insert(10), execute the compare type function to compare the size. The container finds the location where the element can be inserted. After encountering 10, the two call the comparison type function for comparison.

!(A1 <= A2) && !(A2 <= A1)   ==>  !true && !true

Then it is found that this value is always false.

In other words, in the view of the container, the 10 we inserted before and after are not equal, that is, they are not equivalent.

That means that the second 10 will be inserted next to the first 10. In this way, we are equivalent to destroying the original characteristics of the container. Any comparison function that returns true if it is equal will certainly lead to the current situation. The function of the comparison function is to indicate the return value in the order defined by the function. Whether one value precedes another. Equal values are never sequential. Therefore, for equal values, the comparison function needs to always return false.

This is true for set map, but will there be the same problem for multiset and multimap containers that can contain duplicate key values?

multiset<int, less_equal<int>> s;

s.insert(10);
s.insert(10);

Then we equal the container_ Range operation. We'll get a pair of iterators. This pair of iterators defines an interval containing these two values.

But equal_range does not specify an interval with equal values, but an interval with equal values.

#include<iostream>
#include<set>
#include<algorithm>

using namespace std;

int main()
{
	multiset<int, less_equal<int> > s;
	s.insert(10);
	s.insert(10);
	s.insert(11);
	
	pair<multiset<int>::iterator, multiset<int>::iterator> range = equal_range(s.begin(), s.end(), 10);
	
	for(multiset<int>::iterator it = range.first; it != range.second; ++it)
	{
			//cout << *it << " " ;
	}
	
	cout << *range.first << " " << *(++range.first) << " "  << *range.second << endl;	// 10 10 11
	return 0;	
}

The results were surprising. That is, use equal_ After range, we get an interval with equal values.