C++基础笔记11
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_permutation
和 prev_permutation
是 C++ 标准模板库(STL)中的两个算法函数,用于生成给定序列的下一个和上一个排列。
next_permutation
- 函数原型:
1
2template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); - 参数:
first
和last
:定义了排列范围的双向迭代器,表示[first, last)
区间。
- 返回值:如果存在下一个排列,则返回
true
,并更新序列;如果当前序列已经是最后一个排列,则返回false
,序列保持不变。
prev_permutation
- 函数原型:
1
2template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last); - 参数:
first
和last
:定义了排列范围的双向迭代器,表示[first, last)
区间。
- 返回值:如果存在上一个排列,则返回
true
,并更新序列;如果当前序列已经是第一个排列,则返回false
,序列保持不变。
使用条件
- 序列必须是可排列的,即元素必须支持
operator<
运算。 - 序列必须是有序的,即所有元素都按照某种顺序排列。
示例
以下是一个使用 next_permutation
和 prev_permutation
的示例:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
121 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_permutation
和 prev_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 | map<string ,int> mp; |
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 |
|
输出
1 | 链表中的元素:3 2 1 4 5 |