Sort for Built-in Containers

Description

There are lots of built-in containers in C++, via which we can easily and efficiently achieve what we want. However, sometimes the sorting ability of them is relatively limited and as a result, we have to come up with the custom comparer to re-define the sorting feature. I will try to discuss most of them encountering different situations.

Strict Weak Ordering
Almost all functions/containers (except for example priority_queue) require the ordering to satisfy the standard mathematical definition of a strict weak ordering, or else the behavior of the functions/containers will be undefined.

Let f(x, y) be a comparison function. f is in strict weak ordering if it satisfies three invariants:

Irreflexivity: f(x, x) = false.
Antisymmetry: If f(x, y) then !f(y, x).
Transitivity: If f(x, y) and f(y, z) then f(x, z).
Transitivity of Equivalence: Let equal(x, y) = !f(x, y) && !f(y, x). If equal(x, y) and equal(y, z) then equal(x, z).

Methods

Define operator<()

This method can be used if you want objects of a custom class to be able to be sorted naturally just as usual primitive types. If you want ascending order then return < otherwise >.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Edge{
public:
int from, to , weight;
Edge(int a, int b, int c): from(a), to(b), weight(c){}
bool operator < (Edge other) const{
return weight < other.weight;
}
};
int main()
{
vector<Edge> edges;
for(int i = 0; i < 10; ++i) edges.emplace_back(i, i+2, 20-i);
cout<<"Original vector: "<<endl;
for(int i = 0; i < 10; ++i) cout<<edges[i].weight<<",";
cout<<endl;
cout<<"Sorted ascending vector: "<<endl;
sort(edges.begin(), edges.end());
for(int i = 0; i < 10; ++i) cout<<edges[i].weight<<",";
cout<<endl;
random_shuffle(edges.begin(), edges.end());
cout<<"Shuffled vector: "<<endl;
for(int i = 0; i < 10; ++i) cout<<edges[i].weight<<",";
cout<<endl;
cout<<"Ascending set: "<<endl;
set<Edge> edgeSet(edges.begin(), edges.end());
for(auto e: edgeSet) cout<<e.weight<<",";
cout<<endl;
cout<<"Keys ascending map: "<<endl;
map<Edge, int> edgeMap;
for(int i = 0; i < edges.size(); ++i) edgeMap[edges[i]] = i*5;
for(auto& pair: edgeMap) cout<<"key: "<<pair.first.weight<<",";
cout<<endl;
cout<<"Descending max heap: "<<endl;
priority_queue<Edge> maxHeap(edges.begin(), edges.end());
while(maxHeap.size()){
cout<<maxHeap.top().weight<<",";
maxHeap.pop();
}
cout<<endl;
return 0;
}

The output will be as follows:

1
2
3
4
5
6
7
8
9
10
11
12
Original vector:
20,19,18,17,16,15,14,13,12,11,
Sorted ascending vector:
11,12,13,14,15,16,17,18,19,20,
Shuffled vector:
17,11,14,16,18,19,15,12,13,20,
Ascending set:
11,12,13,14,15,16,17,18,19,20,
Keys ascending map:
key: 11,key: 12,key: 13,key: 14,key: 15,key: 16,key: 17,key: 18,key: 19,key: 20,
Descending max heap:
20,19,18,17,16,15,14,13,12,11,

But there are also other usages for particular containers using primitive types, especially when you try to customize the behavior of the order for the primitive types: sort, set and map, and priority_queue.

Set and map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
struct cmpClass{
bool operator()(const int& a, const int& b) const {
return a > b;
}
};
int main()
{
int myints[] = {10, 60, 50, 20};
vector<int> v(myints, myints+4);
auto cmpFunc = [](const int a, const int b) { return a > b; };
cout<<"Sorted int vector using lambda function: "<<endl;
sort(v.begin(), v.end(), [](const int a, const int b) { return a < b; });
for(int i = 0; i < v.size(); ++i) cout<<v[i]<<",";
cout<<endl;
random_shuffle(v.begin(), v.end());
cout<<"Shuffled int vector: "<<endl;
for(int i = 0; i < v.size(); ++i) cout<<v[i]<<",";
cout<<endl;
sort(v.begin(), v.end(), cmpFunc);
cout<<"Sorted int vector using cmpFunc: "<<endl;
for(int i = 0; i < v.size(); ++i) cout<<v[i]<<",";
cout<<endl;
cout<<"Ascending int set using less<int>: "<<endl;
set<int, less<int>> lessSet(v.begin(), v.end());
for(auto n: lessSet) cout<<n<<",";
cout<<endl;
cout<<"Descending int set using cmpFunc: "<<endl;
set<int, decltype(cmpFunc)> funcSet(cmpFunc);
for(int i = 0; i < v.size(); ++i) funcSet.insert(v[i]);
for(auto n: funcSet) cout<<n<<",";
cout<<endl;
cout<<"Descending int set using cmpClass: "<<endl;
set<int, cmpClass> classSet(v.begin(), v.end());
for(auto n: classSet) cout<<n<<",";
cout<<endl;
cout<<"Descending keys in map using greater<int>: "<<endl;
map<int, int, greater<int>> greaterMap;
for(int i = 0; i < v.size(); ++i) greaterMap[v[i]] = v[i]*3;
for(auto& pair: greaterMap) cout<<"key: "<<pair.first<<",";
cout<<endl;
cout<<"Descending keys in map using cmpFunc: "<<endl;
map<int, int, decltype(cmpFunc)> funcMap(cmpFunc);
for(int i = 0; i < v.size(); ++i) funcMap[v[i]] = 2*v[i];
for(auto& pair: funcMap) cout<<"key: "<<pair.first<<",";
cout<<endl;
cout<<"Descending keys in map using cmpClass: "<<endl;
map<int, int, cmpClass> classMap;
for(int i = 0; i < v.size(); ++i) classMap[v[i]] = 3*v[i];
for(auto& pair: classMap) cout<<"key: "<<pair.first<<",";
cout<<endl;
return 0;
}

The out put will be as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Sorted int vector using lambda function:
10,20,50,60,
Shuffled int vector:
10,60,50,20,
Sorted int vector using cmpFunc:
60,50,20,10,
Ascending int set using less<int>:
10,20,50,60,
Descending int set using cmpFunc:
60,50,20,10,
Descending int set using cmpClass:
60,50,20,10,
Descending keys in map using greater<int>:
key: 60,key: 50,key: 20,key: 10,
Descending keys in map using cmpFunc:
key: 60,key: 50,key: 20,key: 10,
Descending keys in map using cmpClass:
key: 60,key: 50,key: 20,key: 10,

Priority_queue

  • primitive types including int, float, …, and pair;
  • cmpClass for comparer;
  • cmpFunction for comparer.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct cmpClass{
bool operator()(const int a, const int b) const {
return a < b;
}
};
int main()
{
int myints[] = {10, 60, 50, 20};
vector<int> v(myints, myints+4);
cout<<"Sorted ascending vector using less<int>: "<<endl;
sort(v.begin(), v.end(), less<int>());
for(int i = 0; i < v.size(); ++i) cout<<v[i]<<",";
cout<<endl;
cout<<"Min heap using greater<int>: "<<endl;
priority_queue<int, vector<int>, greater<int>> minIntHeap(myints, myints+4);
while(minIntHeap.size()) {
cout<<minIntHeap.top()<<",";
minIntHeap.pop();
}
cout<<endl;
vector<pair<int, int>> vv;
for(int i = 0; i < 10; ++i) vv.emplace_back(20-i, i);
cout<<"Unsorted pair vector: "<<endl;
for(int i = 0; i < vv.size(); ++i) cout<<vv[i].first<<",";
cout<<endl;
cout<<"Sorted ascending pair vector: "<<endl;
sort(vv.begin(), vv.end(), less<pair<int, int>>());
for(int i = 0; i < vv.size(); ++i) cout<<vv[i].first<<",";
cout<<endl;
cout<<"Min heap using greater<pair<int, int>>: "<<endl;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minPairHeap(vv.begin(), vv.end());
while(minPairHeap.size()){
cout<<minPairHeap.top().second<<",";
minPairHeap.pop();
}
cout<<endl;
cout<<"Max heap using cmpClass to compare int: "<<endl;
priority_queue<int, vector<int>, cmpClass> maxClassHeap(v.begin(), v.end());
while(maxClassHeap.size()){
cout<<maxClassHeap.top()<<",";
maxClassHeap.pop();
}
cout<<endl;
cout<<"Min heap using cmpFunc to compare int: "<<endl;
auto cmpFunction = [](const int a, const int b) { return a > b; };
priority_queue<int, vector<int>, decltype(cmpFunction)> minFuncHeap(cmpFunction);
for(int i = 0; i < v.size(); ++i) minFuncHeap.push(v[i]);
while(minFuncHeap.size()){
cout<<minFuncHeap.top()<<",";
minFuncHeap.pop();
}
cout<<endl;
return 0;
}

The output will be as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Sorted ascending vector using less<int>:
10,20,50,60,
Min heap using greater<int>:
10,20,50,60,
Unsorted pair vector:
20,19,18,17,16,15,14,13,12,11,
Sorted ascending pair vector:
11,12,13,14,15,16,17,18,19,20,
Min heap using greater<pair<int, int>>:
9,8,7,6,5,4,3,2,1,0,
Max heap using cmpClass to compare int:
60,50,20,10,
Min heap using cmpFunc to compare int:
10,20,50,60,
  • a more complex usage for funcCmp.
1
2
3
auto cmp = [&nums1, &nums2](const pair<int, int>& a, const pair<int, int>&b) {
return nums1[a.first]+nums2[a.second] > nums1[b.first]+nums2[b.second]; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> minHeap(cmp);

Basics

  1. Access the inner map via the outer map
1
2
auto inner_map = cost_function.find(c0);
int minCost = inner_map->second.find(c1)->second;

Always welcome new ideas and practical tricks, just leave them in the comments!