C++ STL容器中的排序(sort)与查找(find)算法的运算符运用及其重载问题_stl find

C++的标准模板库(Standard Template Library，STL)提供了很多的数据容器，以及许多的算法和其他一些组件，整个STL就是由容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分组成的，其中C++的容器就是各种数据结构的算法的一个集合。

---

C++的容器有两种类型的容器：顺序容器和关联容器。
顺序容器：又称线性容器，将数据组织成有限线性集合，主要有：vector、list、deque等。

• vector(向量)表示一段连续的内存地址，基于数组的实现，可以动态的增加或减少。
• list(链表)表示非连续的内存，基于链表实现。
• deque(双端队列)与vector类似，但是对于首元素提供删除和插入的双向支持。

关联容器：主要有map和set(底层是红黑树–平衡排序二叉树)

• map的元素是以key-value形式存在的，key是键值(键值不能重复)，value是实值(可以重复)，并以key值进行元素排序，查找。
• set的元素是单值(键值与实值相同)的，是唯一的，其以实值排序、查找元素。
• multimap和multiset： 可以存放多个相同的key值。

此外还有unorder_map、unorder_set、unorder_multimap、unorder_multiset无序关联容器，其底层实现是哈希表。

容器类可以自动申请和释放内存，我们无需new和delete操作。

vector、list等线性容器是无序容器，即容器内的元素默认是不排序的；map与set容器都是有序容器，容器中的元素默认是从小到大排序(键值排序)，因而需要定义排序的规则，同时map与set的key值不允许重复的，因此需要去重，就需要定义去重的规则(特别是在使用find函数时)。

无论是线性容器还是关联容器，在使用基本数据结构(int，char等)作为容器的元素类型时，已经定义好了排序规则，而对于struct、class类型的数据则需要先重载运算操作符才可以实现排序sort和查找find。

STL各种容器和算法的sort和find函数对重载运算符的调用情况：

• 1、二叉树类型的容器的std::sort和std::find时都会调用operator < 。
• 2、线性类型(vector、list)容器std::sort算法时会调用operator <；使用std::find算法会调用operator ==。

---

对于类与结构体等自定义类型数据的容器对象，重载运算符operator < 与operator ==有两种形式：一种是在类或结构体中直接以成员函数的形式定义；另一种就是在类外定义一个比较函数compare()，以函数指针(或函数对象)的形式作为函数参数传入(针对sort()排序函数)

std::sort()函数的原型声明如下：

template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
//
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
2
3
4
5

std::find()函数的原型声明如下：

//在[first,last)范围内查找第一个与val相等的元素，并返回这个元素的迭代器（iterator），如果没有找到，则返回last。
template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);
1
2
3

一、线性容器(以vector为例)的重载运算符" < " 和" == "

#include <vector>
#include <algorithm>//包含sort和find算法
#include <iostream>
using namespace std;
class Test
{
public:
	int a;
	int b;
	Test(int m_a, int m_b) {
		a = m_a;
		b = m_b;
	}
	//重载<运算符，先按a升序排列，若a相等，则按b升序排列；如果是降序就是重载">"运算符
	bool operator < (const Test& testobj) const
	{
		if (a < testobj.a)
			return true;
		else if (a == testobj.a)
		{
			if (b < testobj.b)
				return true;
			else
				return false;
		}
		else
			return false;
	}
	//重载 == 运算符
	bool operator == (const Test& testobj) const
	{
		//如果a相等，则判断为相等
		//return a == testobj.a;
		//如果a和b都相等，则判断为相等
		return (a == testobj.a) && (b == testobj.b);
	}
};

//类外定义一个比较函数compare
bool compare(const Test& t1, const Test& t2) {
	if (t1.a != t2.a)
		return t1.a < t2.a;
	else if(t1.b != t2.b)
		return t1.b < t2.b;
	return false;
}
int main()
{
	vector<Test> vec;
	vec.push_back(Test(1, 1));
	vec.push_back(Test(3, 6));
	vec.push_back(Test(2, 1));
	vec.push_back(Test(3, 4));

	//排序sort
	sort(vec.begin(), vec.end());//类中定义好排序规则
	//sort(vec.begin(), vec.end(), compare);//类外定义一个比较函数
	for (int i = 0; i< (int)vec.size(); ++i)
	{
		cout << vec[i].a <<" "<< vec[i].b <<endl;
	}

	//查找元素
	vector<Test>::iterator ite = find(vec.begin(), vec.end(), Test(3, 4));
	if(ite!=vec.end())
	{
	cout << "已找到" << ite->a << " " << ite->b << endl;
	}
	else {
		cout << "cannot find " << endl;
	}

	system("pause");
	return 0;
}
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
65
66
67
68
69
70
71
72
73
74
75

a和b值都相等才判断为相等，查找Test(3,4)输出结果为：

a和b值都相等才判断为相等，查找Test(3,3)输出结果为：

为了可以访问自定义类中的private和protected成员，可以将比较函数compare()声明为类的友元函数，形式如下：

class Test
{
//........
friend bool compare(const Test& t1);
};

bool compare(const Test& t1){}
1
2
3
4
5
6
7

---

二、二叉树容器(以set为例)的重载运算符" < "

set容器里的值是没有重复的，每插入一个新元素，需要判定是否与容器中已有的元素相等，若相等则不插入，又因为set容器是有序的，判断是否相等不能重载" == "运算符，只能重载" < "运算符。

其实，set容器在判定已有元素a和新插入元素b是否相等时，是这么做的：1）将a作为左操作数，b作为右操作数，调用比较函数，并返回比较值 2）将b作为左操作数，a作为右操作数，再调用一次比较函数，并返回比较值。如果1、2两步的返回值都是false，则认为a、b是相等的，则b不会被插入set容器中；如果1、2两步的返回值都是true，则可能发生未知行为，因此，记住一个准则：$永远让比较函数对相同元素返回false。$

有结构体对象，将其插入set容器，并按照id去重，按照热度hot进行排序，有两种方式自定义比较函数：

1、重载" < "运算符，示例代码如下：

#include <iostream>
#include <set>
using namespace std;
struct song
{
    int m_id;
    int m_hot;
    song(int id,int hot)
    {

        this->m_id = id;
        this->m_hot = hot;
    }
    bool operator<(const struct song& right)const   //重载<运算符
    {
        if(this->m_id == right.m_id)     //根据id去重
            return false;
        else
        {
            if(this->m_hot != right.m_hot)
            {
                return this->m_hot > right.m_hot;      //按hot值降序排序
            }
            else
            {
                return this->m_id > right.m_id;     
            }
        }
    }
};
void main()
{
    std::set<song> mySet;
    song s1(10,100);
    song s2(20,200);
    song s3(20,300);
    song s4(30,200);
    mySet.insert(s1);    //插入s1
    mySet.insert(s2);    //插入s2
    mySet.insert(s3);    //s3和s2的id相同，不插入
    mySet.insert(s4);    //插入s4
    for(auto it:mySet)
    {
        std::cout<<"id:"<<it.m_id<<",hot:"<<it.m_hot<<std::endl;
    }
    std::cout<<"end"<<std::endl;
    song s5(20,200);
    auto ite=mySet.find(s5);
    if(ite!=mySet.end()){
    cout<<ite->m_id<<endl;
    } else{
    cout<<"cannot find s5"<<endl;
    }
}
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

输出结果为：

2、重载（）运算符，示例代码如下：

#include <iostream>
#include <set>
using namespace std;
struct song
{
    int m_id;
    int m_hot;
    song(int id,int hot)
    {

        this->m_id = id;
        this->m_hot = hot;
    }  
};
struct comp   
{
    bool operator()(struct song left,struct song right)  const//重载（）运算符
    {

        if(left.m_id == right.m_id)     //根据id去重
            return false;
        else
        {
            if(left.m_hot != right.m_hot)
            {
                return left.m_hot > right.m_hot;      //降序
            }
            else
            {
                return left.m_id > right.m_id;     
            }
        }
    }
};
void main()
{
    std::set<song,comp> mySet;      //写法和2.1中的的区别
    song s1(10,100);
    song s2(20,200);
    song s3(20,300);
    song s4(30,200);
    mySet.insert(s1);    //插入s1
    mySet.insert(s2);    //插入s2
    mySet.insert(s3);    //s3和s2的id相同，不插入
    mySet.insert(s4);    //插入s4
    for(auto it:mySet)
    {
        std::cout<<"id:"<<it.m_id<<",hot:"<<it.m_hot<<std::endl;
    }
    std::cout<<"end"<<std::endl;

    song s5(20,200);
    auto ite=mySet.find(s5);
    if(ite!=mySet.end()){
    cout<<ite->m_id<<endl;
    } else{
    cout<<"cannot find s5"<<endl;
    }
}
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

参考博文：
https://www.cnblogs.com/litaozijin/p/6665595.html
https://www.cnblogs.com/caiyishuai/p/8678242.html