STL 常用算法

发表于 2023-01-01 更新于 2025-07-20 分类于程序设计竞赛

STL 常用算法

创建队列对象：queue<元素类型> 队列名; 队列添加元素：队列名.push(元素名); 去掉队首元素：队列名.pop();

访问队首元素：队列名.front(); 访问队尾元素：队列名.back(); 判断是否为空：队列名.empty(); 返回队列大小：队列名.size();

优先队列的小于号重载

struct T
{
    int x, y, z;
    friend bool operator < (const T &t1, const T &t2)
    // bool operator < (const T t2) const
    {
        return t1.z < t2.z;  // { return z < t2.z; }
    } t;
};

栈

STL中栈的基本用法创建栈对象- stack<元素类型> 栈名; 栈顶添加元素- 栈名.push(元素名); 删除栈顶元素- 栈名.pop(); 访问栈顶元素- 栈名.top(); //要先确保栈非空 判断是否为空- 栈名.empty(); 返回栈的大小- 栈名.size();

vector向量

STL中vector的基本用法取向量首元素的迭代器: 向量名.begin(); 取向量尾元素下一地址: 向量名.end(); 取向量首元素的值: 向量名.front(); 取向量尾元素的值: 向量名.back(); 下标形式访问: int value0 = 向量名[0]; // 类似普通数组的访问往尾部添加一个元素: 向量名.push_back(value); // 最常见操作 删除尾部第一个元素: 向量名.pop_back(); 判断向量是否为空: 向量名.empty(); 求向量元素个数: 向量名.size(); // 实际元素个数，不是容量翻转向量: reverse(a.begin() , a.end());

使用迭代器iterator可以小于号

set集合

默认升序

STL中set的基本用法 set的声明: set<int> s; set的清空: s.clear(); 插入一个元素x: s.insert(x); // 如果集合中之前没有，则成功插入并自动排序，否则不插入；查询有否元素x: int hav = s.count(x); // 返回0或1 查找x并返回迭代器: set<int>::iterator it = s.find(x); 判断是否为空集: bool isempty = s.empty(); 求集合元素个数: int n = s.size(); 删除元素x: s.erase(x);

不连续存储，不可以用小于号

降序set排序

如果想对set中元素降序排列，如何处理？

set<int, greater<int> > st;
set<int, greater<int> >::iterator it;
st.insert(3); st.insert(5);
st.insert(2); st.insert(3);
for (it = st.begin(); it != st.end(); it++)
	printf("%d ", *it);

结构体则重载小于运算符

string类

string s; s.length 或 s.size 》》+ - += > < = 取出子串 s.substr(2,3) s.substr(2) 取二以后的插入字符串 s.insert(2,“23”) 找子串第一次出现地址 s.find(“apple”) STL

STL算法操作string对象示例

string s("afgcbed");

sort(s.begin(), s.end());
cout << s << endl; // 输出 abcdefg

next_permutation(s.begin(), s.end());
cout << s << endl; // 输出 abcdegf

reverse(s.begin(), s.end()); // 翻转字符串
cout << s << endl; // 输出 fgedcba

map键值对容器（key/value）

map<int, string> m; 定义一个空map m m.count(k); 返回m中键值等于k的元素的个数(1或0) m.find(k); 存在则返回指向该元素的迭代器，否则返回结束地址end() m.erase(k); 删除m中键为k的元素，返回删除元素的个数(1或0) m.erase(p); 从m中删除迭代器p所指向的元素 m.insert(e); e是一个用在m上的value_type类型的值(一个pair)，如果键e.first不在m中，则插入一个值为e.second的新元素；如果该键在m中已存在，那么不进行任何操作 m.clear(); 清空map m m.empty(); 判断map m是否为空

可以方便的插入map：

int main()
{
    map<int, string> mapStudent;
    mapStudent[1] = "student_one"; //方便的数据插入方式
    mapStudent[2] = "student_two";
    mapStudent[3] = "student_three";
    map<int, string>::iterator iter;
    for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
        cout << iter->first << " " << iter->second << endl;
    return 0;
}

下（上）一个全排列

next(prev)_permutation

STL中的算法 (next_permutation)

next_permutation 通常用于生成序列的全排列。例如：

int a[] = {1, 2, 3};
do {
    cout << a[0] << " " << a[1] << " " << a[2] << endl;
} while (next_permutation(a, a+3));

若当前调用排列已经到达最大字典序（比如 321），则函数返回 false。修改函数的参数（比如 (a, a+2)）则可以只对部分长度进行全排列。

二分查找功能

STL中的二分查找三兄弟:

查找某个元素是否在指定范围出现（返回真或假） binary_search(first, last, val)
查找第一个“大于或等于”某个元素的位置(地址，不是下标) lower_bound(first, last, val)
查找第一个“大于”某个元素的位置（地址，不是下标） upper_bound(first, last, val)

如果所有元素都小于val则返回最后一个位置+1，即last位置 输入的first last 都是地址 lower_bound(); upper_bound(); binary_search();