C++刷题实践--排序总结

STL容器的排序场景

在STL中，容器需要用到排序的场景，按照使用方法，可以分为如下四类：

• STL自动排序的关联型容器（底层结构采取红黑树），如set、map等
• stack、queue和priority-queue都有特定的出入口，不允许用户对元素进行排序访问。
• 使用sort算法的支持随机访问的容器：vector,deque,string
• list的迭代器属于双向迭代，需要使用自己sort成员函数。

重点：vector和map

vector

一维?vector：

vector<int> vec{1,2,3,4};

//默认从小到大排序  1234
sort(vec.begin(),vec.end());
//从大到小排序 4321
sort(vec.begin(),vec.end(),greater<int>());

二维?vector + cmp：

?vector<vector< int >>

//默认优先对第一元素进行从小到大排序，第一元素相同的，按照第二元素从小到大排序

vector<vector<int>> vec{{0,2},{1,5},{1,9},{4,6},{5,9},{8,10}};

//默认优先对第一元素进行从小到大排序，第一元素相同的，按照第二元素从小到大排序
sort(vec.begin(),vec.end()); //[0,2],[1,5],[1,9],[4,6],[5,9],[8,10]

• C++ sort函数自定义cmp函数中参数带&符号

static bool cmp(const vector<int>& v1, const vector<int>& v2){
    //如果第一元素相等，则比较第二元素
    if (v1[0] == v2[0])
        return v1[1] < v2[1];
    return v1[0] > v2[0];
}

vector<vector<int>> vec{{0,2},{1,5},{1,9},{4,6},{5,9},{8,10}};
sort(vec.begin(),vec.end(),cmp);
//[8,10],[5,9],[4,6],[1,5],[1,9],[0,2]

匿名函数Lambda :

vector<vector<int>> vec{{0,2},{1,5},{1,9},{4,6},{5,9},{8,10}};

sort(vec.begin(),vec.end(),[&](const vector<int> &v1, const vector<int> &v2){
    //如果第一元素相等，则比较第二元素
    if (v1[0] == v2[0])
        return v1[1] < v2[1];
    return v1[0] > v2[0];
});
//[8,10],[5,9],[4,6],[1,5],[1,9],[0,2]

map

• map容器默认排序规则为 按照key值进行 从小到大排序（不能按照value排序），利用仿函数，可以改变排序规则
• 对于自定义数据类型，map必须要指定排序规则

map中的按key的默认排序

class MyCompare {
public:
	bool operator()(int v1, int v2) { //v1和v2是两个pair的key
		return v1 > v2;
	}
};

void test01() 
{
	//默认从小到大排序
    //map<int, int, MyCompare> m;
	//利用仿函数实现从大到小排序
	map<int, int, MyCompare> m;

	m.insert(make_pair(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(make_pair(3, 30));
	m.insert(make_pair(4, 40));
	m.insert(make_pair(5, 50));

	for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
		cout << "key:" << it->first << " value:" << it->second << endl;
	}
}

map希望按value排序-解决方法

????????虽然不能直接用sort对map进行排序，但因为map中所有元素都是pair 。可以把map中的pair元素放到序列容器（如vector）中，然后再对这些元素进行排序。

bool compare(const pair<string,int>& a,const pair<string,int>& b){
	if(a.second==b.second)return a.first<b.first;
        else return a.second>b.second;
}
map<string,int> m{{"a",1},{"b",2},{"c",3}};

vector<pair<string,int>> v(m.begin(),m.end());//将map中的元素拷贝到vector中

sort(v.begin(),v.end(),compare);//实现value的排序

set

内置数据类型：

//set 容器默认的存储的是升序。
set<int> S = {1,3,2};

//可改为降序
set<int, greater<int>> S = {1,3,2};

自定义数据类型：

#include <set>
#include <string>
?
class Person
{
public:
    Person(string name, int age)
    {
        this->m_Name = name;
        this->m_Age = age;
    }
?
    string m_Name;
    int m_Age;
?
};
class comparePerson
{
public:
    bool operator()(const Person& p1, const Person &p2)//注意const
    {
        //按照年龄进行排序  降序
        return p1.m_Age > p2.m_Age;
    }
};
?
void test01()
{
    set<Person, comparePerson> s;
?
    Person p1("刘备", 23);
    Person p2("关羽", 27);
    Person p3("张飞", 25);
    Person p4("赵云", 21);
?
    s.insert(p1);
    s.insert(p2);
    s.insert(p3);
    s.insert(p4);
?
    for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age << endl;
    }
}
int main() {
?
    test01();
?
    system("pause");
?
    return 0;
}

注意：对于自定义数据类型，set必须指定排序规则才可以插入数据

参考

C++，自定义sort排序算法，map（key和value分别如何排序），set，priority_queue 自定义存储顺序_c++ map key sort-CSDN博客

C++ vector 自定义排序规则（vector＜vector＜int＞＞、vector＜pair＜int,int＞＞）_vector自定义排序-CSDN博客

C++：map自定义排序_c++ map排序-CSDN博客