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 2	template <class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

参数：
- first 和 last：定义了排列范围的双向迭代器，表示 [first, last) 区间。
返回值：如果存在下一个排列，则返回 true，并更新序列；如果当前序列已经是最后一个排列，则返回 false，序列保持不变。

`prev_permutation`

函数原型：

1 2	template <class BidirectionalIterator> bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

参数：
- first 和 last：定义了排列范围的双向迭代器，表示 [first, last) 区间。
返回值：如果存在上一个排列，则返回 true，并更新序列；如果当前序列已经是第一个排列，则返回 false，序列保持不变。

使用条件

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

示例

以下是一个使用 next_permutation 和 prev_permutation 的示例：

#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
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

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 的示例代码，展示了如何使用一些常见函数：

#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;
}

输出

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

STL usage

sort

nth_element

lower_bound & upper_bound

next_permutation & prev_permutation

next_permutation

prev_permutation