sort

排序,复杂度为O(nlogn)

sort(Iterator begin, Iterator end, Function comp)

nth_element

将第n小的数字移动到第n位,复杂度O(n)

nth_element(Iterator begin, Iterator nth, Iterator end, Function comp)

nth_element(a,begin(), a.begin()+ k, a.end());

此时输出a[k]的值能得到第k小的数字

lower_bound & upper_bound

传入参数相同皆为Iterator begin, Iterator end, Type v, Function comp

在有序的数组中 lower_bound -> 找到第一个大于等于v的迭代器

​ upper_bound -> 找到第一个大于v的迭代器

复杂度为O(logn)

next_permutation & prev_permutation

next_permutationprev_permutation 是 C++ 标准模板库(STL)中的两个算法函数,用于生成给定序列的下一个和上一个排列。

next_permutation

  • 函数原型
    1
    2
    template <class BidirectionalIterator>
    bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
  • 参数
    • firstlast:定义了排列范围的双向迭代器,表示 [first, last) 区间。
  • 返回值:如果存在下一个排列,则返回 true,并更新序列;如果当前序列已经是最后一个排列,则返回 false,序列保持不变。

prev_permutation

  • 函数原型
    1
    2
    template <class BidirectionalIterator>
    bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
  • 参数
    • firstlast:定义了排列范围的双向迭代器,表示 [first, last) 区间。
  • 返回值:如果存在上一个排列,则返回 true,并更新序列;如果当前序列已经是第一个排列,则返回 false,序列保持不变。

使用条件

  • 序列必须是可排列的,即元素必须支持 operator< 运算。
  • 序列必须是有序的,即所有元素都按照某种顺序排列。

示例

以下是一个使用 next_permutationprev_permutation 的示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
std::vector<int> v = {1, 2, 3};
do {
for (int i : v) {
std::cout << i << " ";
}
std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));

std::cout << "所有排列生成完毕,现在使用 prev_permutation 回溯到上一个排列" << std::endl;
while (std::prev_permutation(v.begin(), v.end())) {
for (int i : v) {
std::cout << i << " ";
}
std::cout << std::endl;
}
return 0;
}

输出:
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
所有排列生成完毕,现在使用 prev_permutation 回溯到上一个排列
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3

应用场景

  • 生成所有可能的排列。
  • 在排列中查找特定的排列。
  • 实现回溯算法。

总之,next_permutationprev_permutation 是两个强大的排列生成工具,可以用于生成和操作序列的所有排列。

unique

函数作用

std::unique 函数的作用是移除容器中所有连续重复的元素,只保留每个元素的第一个出现。它不会真正从容器中删除元素,而是将所有重复的元素移动到容器的末尾,并返回一个新的迭代器,指向新的逻辑结束位置。

返回值

std::unique 函数返回的迭代器是一个指向新逻辑结束位置的迭代器。这个迭代器指向的位置是第一个不重复元素之后的位置,即所有重复元素都被移动到这个位置之后。

迭代器类型

unique(v.begin(), v.end()) 返回的迭代器类型与传入的迭代器类型相同。如果 v 是一个 std::vector,那么返回的迭代器就是 std::vector<int>::iterator 类型;如果 v 是一个 std::list,那么返回的迭代器就是 std::list<int>::iterator 类型。

示例

假设 v 是一个 std::vector<int>,那么 v.begin()v.end() 分别是指向 v 的第一个元素和最后一个元素之后的位置的迭代器。unique(v.begin(), v.end()) 会处理这个范围内的所有元素,移除连续重复的元素,并返回一个新的迭代器,指向新的逻辑结束位置。

使用场景

这个返回的迭代器通常用于与容器的 erase 方法结合使用,以实际从容器中移除重复元素.v.erase(unique(v.begin(), v.end()), v.end());

vector

queue stack deque

queue 队列

操作: push/emplace pop front empty size

pop <— [0, 1, 2, 3] <— push

不支持下标访问

stack 栈

操作: push/emplace pop top empty size

[ ] <—- push [ ] —-> pop

不支持下标访问

deque 双端队列

操作: push_back/emplace_back pop_back push_front/emplace_front pop_front

front back empty size

支持下标访问

priority_queue 优先队列/堆

==优先队列 / 堆 大顶堆 小顶堆==

操作: push/emplace pop top empty size

属于队列的一种 但pop时按大小进行pop

eg. <— [3 2 100 0] <— 执行pop操作依次pop出 100 3 2 0 (从大到小)

priority_queue<int, vector<int>, greater<int>> pq;

set 集合

集合: set 有序唯一

​ multiset 有序 不唯一

​ unordered_set 无序 唯一

操作: insert erase find count

有序 元素支持 < 无序 元素支持hash

map

第一个元素是string,第二个元素任意

map<string, int> mp;

multimap

unordered_map

操作:insert/emplace erase find [ ]

也可以通过下标运算通过key来输出value

1
2
3
4
5
6
7
8
map<string ,int> mp;
mp.insert(make_pair("xiaozhang" , 99));
mp.insert({"xiaoli", 95});
mp.emplace("guojia", 92);
cout << mp["xiaozhang"] <> endl;// 99
//如果输出map中原来没有的 会插入进map中,此时value是第二个参数的默认值
cout << mp["whatever"] << endl;// 0
cout << mp.size() << endl;//得到4

list

std::list 是C++标准模板库(STL)中的一个双向链表容器。它提供了高效的插入和删除操作,尤其是在链表的头部和尾部。与数组或 std::vector 不同,std::list 的元素不是连续存储的,而是通过指针连接的节点。

常见函数

以下是 std::list 的一些常用成员函数,按功能分类介绍:

构造和析构

  • std::list():默认构造函数,创建一个空的链表。
  • std::list(size_t n, const T& value):创建一个包含 n 个值为 value 的元素的链表。
  • std::list(const std::list& other):拷贝构造函数,创建一个与 other 相同的链表。
  • std::list(std::list&& other):移动构造函数,将 other 的内容移动到新链表中。
  • ~std::list():析构函数,销毁链表中的所有元素。

    迭代器

  • begin():返回指向链表第一个元素的迭代器。

  • end():返回指向链表末尾(最后一个元素之后)的迭代器。
  • rbegin():返回指向链表最后一个元素的反向迭代器。
  • rend():返回指向链表开头(第一个元素之前)的反向迭代器。

容量

  • empty():检查链表是否为空,返回布尔值。
  • size():返回链表中元素的数量。
  • max_size():返回链表可以容纳的最大元素数量。

元素访问

  • front():返回链表中第一个元素的引用。
  • back():返回链表中最后一个元素的引用。

修改器

  • push_front(const T& value):在链表头部插入一个值为 value 的元素。
  • pop_front():删除链表头部的元素。
  • push_back(const T& value):在链表尾部插入一个值为 value 的元素。
  • pop_back():删除链表尾部的元素。
  • insert(iterator pos, const T& value):在指定位置 pos 插入一个值为 value 的元素。
  • erase(iterator pos):删除指定位置 pos 的元素。
  • clear():删除链表中的所有元素。
  • swap(std::list& other):交换两个链表的内容。

操作

  • reverse():反转链表中的元素顺序。
  • sort():对链表中的元素进行排序。
  • unique():删除链表中连续重复的元素。
  • merge(std::list& other):将两个已排序的链表合并为一个有序链表。

示例代码

以下是一个使用 std::list 的示例代码,展示了如何使用一些常见函数:

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
#include <iostream>
#include <list>

int main() {
// 创建一个空的链表
std::list<int> myList;

// 在链表头部插入元素
myList.push_front(1);
myList.push_front(2);
myList.push_front(3);

// 在链表尾部插入元素
myList.push_back(4);
myList.push_back(5);

// 输出链表中的元素
std::cout << "链表中的元素:";
for (int value : myList) {
std::cout << value << " ";
}
std::cout << std::endl;

// 删除链表头部的元素
myList.pop_front();

// 删除链表尾部的元素
myList.pop_back();

// 输出链表中的元素
std::cout << "删除头部和尾部后的元素:";
for (int value : myList) {
std::cout << value << " ";
}
std::cout << std::endl;

// 在链表中间插入元素
auto it = myList.begin();
++it; // 移动到第二个元素
myList.insert(it, 10);

// 输出链表中的元素
std::cout << "在链表中间插入元素后的元素:";
for (int value : myList) {
std::cout << value << " ";
}
std::cout << std::endl;

// 删除指定位置的元素
myList.erase(it);

// 输出链表中的元素
std::cout << "删除指定位置的元素后的元素:";
for (int value : myList) {
std::cout << value << " ";
}
std::cout << std::endl;

// 反转链表
myList.reverse();

// 输出链表中的元素
std::cout << "反转链表后的元素:";
for (int value : myList) {
std::cout << value << " ";
}
std::cout << std::endl;

return 0;
}

输出

1
2
3
4
5
链表中的元素:3 2 1 4 5
删除头部和尾部后的元素:2 1 4
在链表中间插入元素后的元素:2 10 1 4
删除指定位置的元素后的元素:2 1 4
反转链表后的元素:4 1 2

STL usage