C++语言系列-STL容器和算法

本文将对C++语言中的标准模板库STL容器进行简单介绍，重点在于如何使用。

容器类

STL中的容器包括以下类别：

• vector: 动态数组，底层基于数组来实现，在容量不足的时候能够自动进行扩容。
• list: 链表
• stack: 先进后出的栈
• set: 基于红黑树实现的集合，插入或者查找的时间复杂度在$O(nlogn)$
• unordered_set:基于哈希表实现的集合，插入或者查找的时间复杂度基本上在$O(1)$
• map: 基于红黑树实现，插入或者查找的时间复杂度在$O(nlogn)$，性能相对稳定，且因为有序性可以支持范围查找
• unordered_map: 基于哈希表实现，插入或者查找的时间复杂度基本上在$O(1)$，性能相对不稳定
• queue：新进先出的单向队列
• deque: 双端队列
• priority_queue: 底层基于大顶堆或者小顶堆来实现，优先级队列，能够以$O(logn)$的时间复杂度取出队列中所有的元素的最小值
• string: 字符串

下面以代码的方式给出各种容器的使用方法，包括如何使用迭代器进行遍历，如何使用算法进行排序，如下：

/*多年刷题经验总结的stl常用的接口
*/
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<queue>  // 包括priority_queue
#include<deque>
#include<string>
#include<algorithm>
//  g++  -Wno-all  -o demo   stl.cpp
class Demo {
public:int A;Demo(){}Demo(int A) {this -> A = A;}
};struct Demo1
{bool operator()(const int &lhs, const int &rhs) const{ // 后面const修饰表示该函数为常成员函数，不会修改成员变量return lhs > rhs;}
};bool compare(const int &l1, const int &l2)
{return l1 > l2;
}void use_vector() {std::vector<int> v1;   // 空的vectorstd::vector<int> v2(3);  // 含有三个默认值的vectorstd::vector<int> v3(3, -1); // 三个值为-1的vectorstd::vector<std::vector<int>> v4 = {{1, 2}, {3, 4}};  // 二维数组// 获取元素数量, 所有容器通用, 调用的还有empty, 以及可以迭代操作的容器会有begin和end两个获取迭代器的通用函数int size = v3.size();  std::cout << "v3.size() = " << size << std::endl;v3[1] = 2;std::cout << "v3[1] = " << v3[1] << std:: endl;  // 通过[]直接读写对应位置的元素v3.push_back(1);  // 在某位添加元素v3.pop_back();   // 删除末尾的元素for (auto item: v3) {std::cout << item << std::endl;}// 排序, 倒排序std::sort(v3.begin(), v3.end(), compare);for (auto item: v3) {std::cout << item << std::endl;}
}void use_list() {std::list<int> l1;// 提供的api可以完美实现队列和双端队列l1.push_back(0);   // 尾部插入l1.push_back(1);l1.push_front(2);  // 头部插入l1.push_front(3);// 分别访问头部和尾部的元素std::cout << l1.front() << " " << l1.back() << std::endl;l1.pop_back();   // 尾部删除l1.pop_front();  // 头部删除，无返回值std::cout << l1.front() << " " << l1.back() << std::endl;
}void use_stack() {std::stack<int> s1;s1.push(-1);s1.push(-2);std::cout << s1.top() << std::endl;s1.pop();  // 无返回值std::cout << s1.top() << std::endl;
}void use_set()
{std::set<int> s1{1, 2};std::unordered_set<int> s2{3, 4};// set 和unordered_set 的查找和插入,删除操作是一样的if (s1.find(1) != s1.end()){ // 通过这种方式判断元素是否存在std::cout << "1 int s1" << std::endl;}s1.erase(1);if (s1.find(1) != s1.end()){std::cout << "1 int s1" << std::endl;}if (s2.find(1) != s2.end()){std::cout << "1 not int s2" << std::endl;}s2.insert(1);if (s2.find(1) != s2.end()){std::cout << "1 not int s2" << std::endl;}// 此外，基于有序，set还能提供以下两个函数auto it1 = s1.lower_bound(2); // 小于等于的元素对应的迭代器auto it2 = s1.upper_bound(1); // 大于元素对应的迭代器std::cout << *it1 << " " << *it2 << std::endl;
}void use_map()
{std::map<int, int> m1;std::unordered_map<int, int> m2;// 以下为两种类型的map都有的操作,直接通过[]读写元素m1[1] = -1;m2[0] = 1;m1.erase(1);auto it = m2.find(0);std::cout << it->second << std::endl;// 如何遍历for (auto it = m2.begin(); it != m2.end(); it++){std::cout << it->first << " " << it->second << std::endl;}
}void use_queue() {// 单向队列std::queue<int> q1;q1.push(-1);q1.push(-2);std::cout << q1.front() << std::endl;std::cout << q1.back() << std::endl;q1.pop();  // 无返回值std::deque<int> q2;q2.push_back(0);   // 尾部插入q2.push_back(1);q2.push_front(2);  // 头部插入q2.push_front(3);// 分别访问头部和尾部的元素std::cout << q2.front() << " " << q2.back() << std::endl;q2.pop_back();   // 尾部删除q2.pop_front();  // 头部删除，无返回值std::cout << q2.front() << " " << q2.back() << std::endl;// 重点关注优先级队列的创建，分别传入类型，底层容器（可选，默认vector），排序方式（可选，默认大顶堆)std::priority_queue<int, std::vector<int>, Demo1> q3;q3.push(37);q3.push(14);q3.push(559);q3.push(14);std::cout << q3.top() << std::endl;  // 打印最小数q3.pop();q3.pop();std::cout << q3.top() << std::endl; // 37// 介绍emplacestd::queue<Demo> q4;// emplace 原地构造对象，相比于push操作，push会先构造一个对象，然后调用拷贝构造函数或者移动构造函数在容器的对应位置构造一个，而emplace直接在容器的对应位置构造，效率更高q4.emplace(-1);
}void use_string() {char *str = "abcd";// 构造方法std::string s1 = std::string(4, 'c');  // "cccc"std::string s2 = std::string(str);  // 两种构造方法// 通过[]直接读写某个位置的字符s1[0] = 'b';std::cout << s1[0] << std::endl;std::string s3 = s1.append(s2);  // 拼接字符串std::cout << s3 << std::endl;int pos1 = s2.find("b", 1);  // 从字符串的1号位置往右查找第一个子串int pos2 = s1.rfind("c", 2); // 从字符串的2号位置往左查找第一个子串int ret = s1.compare(s2);  // 比较大小，大于返回1， 小于返回-1， 相等返回0std::string s4 = s1.substr(1, 2); // 截取从1号位置开始的后面两个字符作为子字符串std::cout << pos1 << " " << pos2 << " " << ret << " " << s4 << std::endl;
}int main() {std::cout << "test use vector" << std::endl;use_vector();std::cout << "test use list" << std::endl;use_list();std::cout << "test use stack" << std::endl;use_stack();std::cout << "test use set" << std::endl;use_set();std::cout << "test use map" << std::endl;use_map();std::cout << "test use queue" << std::endl;use_queue();std::cout << "test use string" << std::endl;use_string();return 0;
}