Zengtudor/noi_outline

Fork 0

Zengtudor f4fb5a79e0 update

2024-10-22 16:59:42 +08:00

29 KiB

Raw Permalink Blame History

类

类的概念及简单应用

官方文档解释
1. 比较复杂，有些东西用不到，想要深入了解时可以自行学习
通俗的说：

C++类就像是“模具”，用来创建“物体”。比如，如果你要建造很多房子，先做一个房子的模具，里面规定了房子有几扇门、几扇窗户。这个模具就是“类”。每次用模具做出来的具体房子就是“对象”。

类里面可以有“属性”（就像房子的面积、颜色）和“方法”（像开门、关窗的操作）。通过这个类，你可以快速制造出多个相似的对象，而不用每次重新定义所有细节。
关于struct 与 class
1. C++ 中 struct与class没有本质区别，只不过class中默认private,struct中默认public

成员函数和运算符重载

程序

#include <iostream>
#include <ostream>
#include <string>
#include <utility>

class Student{
private:
    std::string name;
    int age;
public:
    Student(const std::string &name, const int &age):name(name), age(age){ //重定义构造函数
        std::cout<<"Student "<<name<<" is constructing.\n";
    }
    Student(const Student &that){ // 模仿自动生成的拷贝构造函数
        std::cout<<"Copy constructor\n";
        this->name = that.name;
        this->age = that.age;
    }
    Student(Student&&that){//移动构造函数
        std::cout<<"Move constructor\n";
        this->name = that.name;
        this->age = that.age;
        that.name.clear();
        that.age = -1;
    }
    friend std::ostream& operator<<(std::ostream &os,const Student &s){ // 友元函数与运算符重载
        os<<"Student { name:'"<<s.name<<"', age: "<<s.age<<" }\n";
        return os;
    }
    Student operator+(const Student &that)const{ //运算符重载
        return Student(this->name+that.name, this->age+that.age);
    }
    void say_hello()const{ //打招呼，成员函数
        std::cout<<"Hello, my name is "<<this->name<<" .\n";
    }
};

int main(){
    Student Zengtudor("Zengtudor",18);//构造函数
    Zengtudor.say_hello();//成员函数
    Student Alice("Alice",18);//构造函数
    Student fake_Zengtudor = Zengtudor;//拷贝构造函数
    Student new_Zengtudor = std::move(Zengtudor);//移动构造函数，数据移动到新的，销毁旧的
    std::cout<<Alice;//友元函数，运算符重载
    std::cout<<Alice+new_Zengtudor;//运算符重载+
}

输出

Student Zengtudor is constructing.
Hello, my name is Zengtudor .
Student Alice is constructing.
Copy constructor
Move constructor
Student { name:'Alice', age: 18 }
Student AliceZengtudor is constructing.
Student { name:'AliceZengtudor', age: 36 }

STL模板

容器(container)

官方解释

迭代器(Iterator)

官方解释
说白了，迭代器就是经过抽象化的指针

#include <iostream>
#include <set>

#define NV(v)#v<<" :\t"<<(v)
int main(){
    std::set<int> s;
    s.insert({1,2,3});
    auto it = s.find(2);
    std::cout<<NV(*s.begin())<<'\n';
    // std::cout<<*s.end()<<'\n'; 注意不可以访问end
    std::cout<<NV(*s.rbegin())<<'\n';//访问末尾的正确方式
    std::cout<<NV(*it)<<'\n';
    std::cout<<NV(*--it)<<'\n';
    std::cout<<NV(*(++ ++it))<<'\n';
}

输出

*s.begin() :    1
*s.rbegin() :   3
*it :   2
*--it : 1
*(++ ++it) :    3

对(pair)

在C++中，std::pair 是一个模板类，可以将两个数据组合成一个单一的对象，常用于需要将两个相关的数据项捆绑在一起的时候，例如键值对、坐标对等。下面是std::pair的重点用法：

1. 定义和初始化

std::pair 可以通过多种方式进行初始化：

#include <iostream>
#include <utility>

int main() {
    // 直接构造
    std::pair<int, std::string> p1(1, "apple");
    
    // 使用make_pair构造（推荐）
    auto p2 = std::make_pair(2, "banana");
    
    // 列表初始化（C++11及之后）
    std::pair<int, double> p3 = {3, 4.5};
    
    // 复制构造
    std::pair<int, std::string> p4 = p1;
    
    std::cout << p1.first << ", " << p1.second << std::endl;
    std::cout << p2.first << ", " << p2.second << std::endl;
    std::cout << p3.first << ", " << p3.second << std::endl;
    std::cout << p4.first << ", " << p4.second << std::endl;

    return 0;
}

2. 成员变量

std::pair有两个公开的成员变量：

first：存储第一个数据
second：存储第二个数据

使用示例：

std::pair<int, std::string> p = {10, "hello"};
std::cout << p.first << std::endl;  // 输出 10
std::cout << p.second << std::endl; // 输出 hello

3. 使用`std::make_pair`

std::make_pair 可以自动推导类型，简化构造std::pair的过程：

auto p = std::make_pair(42, "example");
std::cout << p.first << ", " << p.second << std::endl;

4. 比较操作

std::pair 支持字典序比较，即先比较 first，如果 first 相等，则再比较 second：

std::pair<int, int> p1 = {1, 5};
std::pair<int, int> p2 = {1, 10};

if (p1 < p2) {
    std::cout << "p1 is less than p2" << std::endl;
}

上面的代码中，p1 < p2 是 true，因为 1 == 1，然后 5 < 10。

5. 作为容器的元素

std::pair 可以用于标准容器（如std::vector, std::map）中。例如，std::map 的键值对本质上就是 std::pair：

#include <map>

std::map<int, std::string> m;
m.insert(std::make_pair(1, "one"));
m[2] = "two";

for (const auto& item : m) {
    std::cout << item.first << " -> " << item.second << std::endl;
}

6. 结构化绑定（C++17）

在C++17中，可以使用结构化绑定直接从 std::pair 中解构出两个值：

auto [id, name] = std::make_pair(3, "C++");
std::cout << id << ", " << name << std::endl;

7. 应用场景

std::pair 主要用于以下场景：

返回多个值：如果函数需要返回多个值，可以使用 std::pair。
键值对：在 std::map 中使用。
组合相关的数据：如坐标 (x, y)、范围 (start, end)等。

示例：使用`std::pair`返回多个值

std::pair<int, int> getMinMax(const std::vector<int>& nums) {
    int min = *std::min_element(nums.begin(), nums.end());
    int max = *std::max_element(nums.begin(), nums.end());
    return {min, max};
}

int main() {
    std::vector<int> numbers = {5, 7, 2, 9, 1};
    auto [minValue, maxValue] = getMinMax(numbers);
    std::cout << "Min: " << minValue << ", Max: " << maxValue << std::endl;
}

在上面的例子中，getMinMax 函数使用 std::pair 返回了最小值和最大值。

元组(tuple)

在C++中，std::tuple 是一个可以包含多个不同类型元素的容器。它类似于结构体，但更灵活，因为不需要预先定义类型和数量。std::tuple 是在 C++11 中引入的，它在 <tuple> 头文件中定义。

1. 创建和初始化 `std::tuple`

可以使用 std::make_tuple 或直接构造一个 std::tuple 来创建：

#include <iostream>
#include <tuple>
#include <string>

int main() {
    // 使用std::make_tuple
    auto person = std::make_tuple("Alice", 25, 1.75);

    // 直接构造一个std::tuple
    std::tuple<std::string, int, double> person2("Bob", 30, 1.80);

    return 0;
}

2. 访问 `std::tuple` 元素

可以使用 std::get<index> 来访问 tuple 的元素。需要注意的是，索引是从 0 开始的：

std::string name = std::get<0>(person);
int age = std::get<1>(person);
double height = std::get<2>(person);

std::cout << "Name: " << name << ", Age: " << age << ", Height: " << height << std::endl;

3. 修改 `std::tuple` 元素

std::get 也可以用于修改元素的值：

std::get<1>(person) = 26; // 将age改为26

4. 获取 `std::tuple` 的元素数量

可以使用 std::tuple_size 来获取 tuple 的元素数量：

std::cout << "Tuple size: " << std::tuple_size<decltype(person)>::value << std::endl;

5. 使用 `std::tie` 解构 `tuple`

std::tie 可以将 tuple 的内容分解为多个变量：

std::string name;
int age;
double height;

std::tie(name, age, height) = person;
std::cout << "Name: " << name << ", Age: " << age << ", Height: " << height << std::endl;

还可以忽略不需要的元素，用 std::ignore：

std::tie(name, std::ignore, height) = person;

6. 比较 `std::tuple`

std::tuple 支持比较运算符（==, !=, <, <=, >, >=），按照字典顺序进行比较：

std::tuple<int, int, int> t1(1, 2, 3);
std::tuple<int, int, int> t2(1, 3, 2);

if (t1 < t2) {
    std::cout << "t1 is less than t2" << std::endl;
}

7. 合并 `std::tuple`

可以使用 std::tuple_cat 将多个 tuple 合并：

auto t1 = std::make_tuple(1, 2);
auto t2 = std::make_tuple(3.5, "hello");
auto t3 = std::tuple_cat(t1, t2);

std::cout << std::get<0>(t3) << ", " << std::get<1>(t3) << ", " 
          << std::get<2>(t3) << ", " << std::get<3>(t3) << std::endl;

8. 使用结构化绑定 (C++17)

在 C++17 中，引入了结构化绑定，可以更加方便地解构 tuple：

auto [name, age, height] = person;
std::cout << "Name: " << name << ", Age: " << age << ", Height: " << height << std::endl;

总结

std::tuple 非常适合在需要返回多个不同类型的值、或处理不同类型的数据集合时使用。它的灵活性和便捷的接口使得它成为 C++ 中一种非常实用的工具。

集合(set)

std::set 是 C++ 标准库中的一种关联容器，主要用于存储不重复的元素，并且会自动按照元素的顺序进行排序。常见的用法包括插入、删除、查找元素等。std::set 的底层实现通常是基于红黑树，因此它的操作（插入、删除、查找）时间复杂度都是 O(log n)。

下面是 std::set 的一些基本用法和示例。

1. 引入头文件

要使用 std::set，需要包含头文件：

#include <set>

2. 定义 `std::set`

std::set<int> s; // 定义一个存储 int 类型元素的集合
std::set<std::string> strSet; // 定义一个存储字符串的集合

3. 插入元素

使用 insert 函数来插入元素。如果元素已经存在，则不会插入。

s.insert(5);
s.insert(10);
s.insert(5); // 重复插入无效，set 中仍然只有一个 5

for (int x : s) {
    std::cout << x << " "; // 输出: 5 10
}

4. 删除元素

erase(value): 删除指定值的元素。
erase(iterator): 删除指定位置的元素。
erase(begin, end): 删除指定范围内的元素。

s.erase(5); // 删除元素 5

auto it = s.find(10);
if (it != s.end()) {
    s.erase(it); // 删除迭代器位置上的元素 10
}

5. 查找元素

find(value): 返回一个指向找到元素的迭代器，如果找不到则返回 end()。
count(value): 返回元素出现的次数，对于 set 来说，要么是 0 要么是 1。

if (s.find(5) != s.end()) {
    std::cout << "5 is in the set" << std::endl;
}

if (s.count(10) > 0) {
    std::cout << "10 is in the set" << std::endl;
}

6. 大小与清空

size(): 返回集合中元素的个数。
empty(): 判断集合是否为空。
clear(): 清空集合中的所有元素。

std::cout << "Size: " << s.size() << std::endl; // 输出集合的大小

if (!s.empty()) {
    std::cout << "The set is not empty." << std::endl;
}

s.clear(); // 清空集合

7. 遍历 `std::set`

可以使用迭代器或者基于范围的 for 循环进行遍历。

for (auto it = s.begin(); it != s.end(); ++it) {
    std::cout << *it << " ";
}

// 或者
for (const auto &x : s) {
    std::cout << x << " ";
}

8. 自定义排序规则

默认情况下，std::set 按照元素的 < 运算符排序。如果需要自定义排序规则，可以使用比较函数或仿函数。

// 降序排序
std::set<int, std::greater<int>> s_desc;
s_desc.insert(3);
s_desc.insert(1);
s_desc.insert(2);

for (int x : s_desc) {
    std::cout << x << " "; // 输出: 3 2 1
}

9. 其它常用操作

lower_bound(value): 返回第一个大于或等于 value 的迭代器。
upper_bound(value): 返回第一个大于 value 的迭代器。

s.insert(1);
s.insert(3);
s.insert(5);

auto lb = s.lower_bound(3); // 指向 3
auto ub = s.upper_bound(3); // 指向 5

示例代码

#include <iostream>
#include <set>

int main() {
    std::set<int> s;

    // 插入元素
    s.insert(1);
    s.insert(5);
    s.insert(3);

    // 遍历集合
    for (int x : s) {
        std::cout << x << " "; // 输出: 1 3 5
    }
    std::cout << std::endl;

    // 查找元素
    if (s.find(3) != s.end()) {
        std::cout << "Found 3" << std::endl;
    }

    // 删除元素
    s.erase(3);

    // 检查大小
    std::cout << "Size: " << s.size() << std::endl;

    return 0;
}

多重集合(multiset)

std::multiset 是 C++ 标准库中的一个容器，用于存储可以重复的元素，且元素会自动按照特定的顺序排列。std::multiset 是一个关联容器，底层通常使用红黑树实现，因此支持高效的插入、删除和查找操作。

主要特性

元素可以重复：与 std::set 不同，std::multiset 允许插入重复元素。
自动排序：插入的元素会根据给定的比较函数（默认是 operator<）自动排序。
性能：查找、插入和删除操作的平均时间复杂度为 O(log n)。

常用操作

以下是一些 std::multiset 的常用操作：

包含头文件：
```
#include <set>
```

定义和初始化：

std::multiset<int> ms;  // 定义一个整型的multiset
std::multiset<int> ms2 = {1, 2, 2, 3, 4};  // 初始化

插入元素：

ms.insert(5);
ms.insert(3);
ms.insert(3);  // 允许重复

删除元素：

ms.erase(3);  // 删除一个值为3的元素，若存在多个3，删除一个

查找元素：

auto it = ms.find(2);  // 查找值为2的元素
if (it != ms.end()) {
    std::cout << "Found: " << *it << std::endl;
}

计数元素：

size_t count = ms.count(2);  // 计数值为2的元素个数

遍历元素：

for (const auto& val : ms) {
    std::cout << val << " ";
}

大小和清空：

std::cout << "Size: " << ms.size() << std::endl;  // 返回元素个数
ms.clear();  // 清空multiset

示例代码

以下是一个使用 std::multiset 的简单示例：

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    // 插入元素
    ms.insert(5);
    ms.insert(3);
    ms.insert(3);
    ms.insert(7);
    ms.insert(1);

    // 遍历元素
    std::cout << "Elements in multiset: ";
    for (const auto& val : ms) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 查找元素
    auto it = ms.find(3);
    if (it != ms.end()) {
        std::cout << "Found: " << *it << std::endl;
    }

    // 计数
    std::cout << "Count of 3: " << ms.count(3) << std::endl;

    // 删除元素
    ms.erase(3);  // 删除一个3
    std::cout << "After erasing one 3, elements: ";
    for (const auto& val : ms) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

双端队列(deque)

deque（双端队列）是C++标准库中提供的一种序列容器，它支持从两端高效地插入和删除元素。与vector不同，deque允许在头部和尾部都进行高效的操作，适合需要频繁在两端插入和删除的场景。

1. 引入头文件

使用deque之前，需要包含头文件：

#include <deque>

2. 创建`deque`

可以使用默认构造函数或指定初始值来创建一个deque：

std::deque<int> dq; // 创建一个空的 deque
std::deque<int> dq2(5, 10); // 创建一个包含5个10的 deque

3. 常用操作

以下是一些常用的deque操作：

3.1 插入元素

在头部插入元素：push_front()
在尾部插入元素：push_back()

dq.push_front(1); // 在头部插入 1
dq.push_back(2);  // 在尾部插入 2

3.2 删除元素

从头部删除元素：pop_front()
从尾部删除元素：pop_back()

dq.pop_front(); // 删除头部元素
dq.pop_back();  // 删除尾部元素

3.3 访问元素

使用下标访问元素：operator[]
使用 at() 方法安全访问元素
使用 front() 和 back() 访问头尾元素

int first = dq.front(); // 获取头部元素
int last = dq.back();   // 获取尾部元素
int second = dq[1];     // 获取第二个元素

3.4 大小和容量

size() 获取元素个数
empty() 判断是否为空

size_t size = dq.size(); // 获取 deque 的大小
bool isEmpty = dq.empty(); // 判断 deque 是否为空

3.5 清空容器

使用 clear() 清空所有元素

dq.clear(); // 清空 deque

4. 示例代码

下面是一个完整的示例，演示如何使用deque：

#include <iostream>
#include <deque>

int main() {
    // 创建一个双端队列并添加元素
    std::deque<int> dq;
    dq.push_back(10);
    dq.push_back(20);
    dq.push_front(5);
    
    // 输出当前元素
    std::cout << "当前 deque 元素: ";
    for (const auto& elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 删除头部和尾部元素
    dq.pop_front(); // 删除 5
    dq.pop_back();  // 删除 20

    std::cout << "删除后 deque 元素: ";
    for (const auto& elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 访问头尾元素
    std::cout << "头部元素: " << dq.front() << std::endl;
    std::cout << "尾部元素: " << dq.back() << std::endl;

    return 0;
}

5. 注意事项

deque的底层实现使其在插入和删除时比vector更高效，但在随机访问时可能比vector慢。
deque适合用作队列和栈，支持高效的插入和删除操作。

优先队列(priority_queue)

在 C++ 中，priority_queue 是一个 STL（标准模板库）容器适配器，用于管理优先队列。优先队列是一种特殊类型的队列，其中每个元素都有一个优先级。优先级较高的元素会被优先处理，而不是按照它们被添加的顺序。

基本特性

元素顺序：在 priority_queue 中，元素会根据优先级进行排序。默认情况下，优先级最高的元素位于队列的顶部（即最前面），并且可以快速访问和移除。
底层容器：priority_queue 通常使用堆（heap）作为其底层数据结构，默认是最大堆（max heap）。这意味着最大元素总是位于队列的顶部。
模板类：priority_queue 是一个模板类，可以与任意类型的元素一起使用，但需要提供比较函数来确定优先级。

基本操作

以下是 priority_queue 的一些基本操作和用法：

定义优先队列：

#include <queue>
#include <vector>
#include <iostream>

std::priority_queue<int> pq; // 默认最大堆

添加元素：
```
pq.push(10);
pq.push(5);
pq.push(20);
```

访问顶部元素：

std::cout << "Top element: " << pq.top() << std::endl; // 输出 20

移除顶部元素：
```
pq.pop(); // 移除 20
```

检查是否为空：

if (!pq.empty()) {
    std::cout << "Queue is not empty" << std::endl;
}

获取队列大小：

std::cout << "Size of queue: " << pq.size() << std::endl;

自定义比较

如果你想创建一个最小堆（即优先级最低的元素在顶部），可以使用自定义比较函数。下面是一个示例：

#include <queue>
#include <vector>
#include <iostream>

struct Compare {
    bool operator()(int a, int b) {
        return a > b; // 小的优先
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(20);

    std::cout << "Top element (min-heap): " << minHeap.top() << std::endl; // 输出 5

    return 0;
}

映射(map)

std::map 是 C++ 标准库中的一个关联容器，它提供了一种基于键-值对存储数据的方式。std::map 内部实现通常是平衡二叉树（例如红黑树），这使得它在插入、删除和查找操作上具有对数时间复杂度。下面是一些关于 std::map 的基本用法和特性：

1. 基本特性

键唯一性：每个键在 std::map 中都是唯一的。如果插入一个已经存在的键，旧的值将被新值覆盖。
有序性：std::map 中的元素是按照键的顺序排列的，默认情况下使用 < 运算符进行比较。
支持自定义比较：可以通过提供自定义比较器来定义排序方式。

2. 常用操作

以下是一些常用的操作及示例代码：

2.1 包含头文件

#include <iostream>
#include <map>

2.2 创建和初始化

std::map<std::string, int> myMap;  // 键为字符串，值为整数

// 初始化
std::map<std::string, int> myMap = {
    {"apple", 2},
    {"banana", 3},
    {"orange", 5}
};

2.3 插入元素

myMap["grape"] = 4;  // 插入新元素
myMap.insert({"pear", 1});  // 使用 insert 方法插入

2.4 查找元素

auto it = myMap.find("banana");  // 查找键为 "banana" 的元素
if (it != myMap.end()) {
    std::cout << "Found banana: " << it->second << std::endl;  // 输出对应的值
} else {
    std::cout << "Banana not found!" << std::endl;
}

2.5 删除元素

myMap.erase("apple");  // 删除键为 "apple" 的元素

2.6 遍历元素

for (const auto& pair : myMap) {
    std::cout << pair.first << ": " << pair.second << std::endl;  // 输出每个键值对
}

2.7 其他常用操作

获取大小：myMap.size() 返回元素个数。
检查是否为空：myMap.empty() 检查 map 是否为空。

3. 示例代码

以下是一个完整的示例代码，展示了 std::map 的基本用法：

#include <iostream>
#include <map>

int main() {
    // 创建一个 map
    std::map<std::string, int> myMap;

    // 插入元素
    myMap["apple"] = 2;
    myMap["banana"] = 3;
    myMap["orange"] = 5;

    // 查找元素
    auto it = myMap.find("banana");
    if (it != myMap.end()) {
        std::cout << "Found banana: " << it->second << std::endl;
    }

    // 遍历元素
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 删除元素
    myMap.erase("apple");

    // 检查大小
    std::cout << "Size: " << myMap.size() << std::endl;

    return 0;
}

多重映射(multimap)

std::multimap 是 C++ STL（标准模板库）中的一个关联容器，用于存储键值对，其中一个键可以对应多个值。与 std::map 不同，std::multimap 允许相同的键多次出现，因此适合需要重复键的场景。

主要特点

存储键值对：std::multimap 存储的是 std::pair<const Key, Value> 类型的数据。
自动排序：插入的元素会根据键自动排序，默认是升序排列。
键的重复性：相同的键可以多次插入。
性能：插入、删除、查找操作的时间复杂度是 O(log n)。

常用操作

以下是 std::multimap 的一些常用操作：

定义和初始化：

#include <iostream>
#include <map>

std::multimap<int, std::string> mmap;
mmap.insert(std::make_pair(1, "apple"));
mmap.insert(std::make_pair(1, "banana"));
mmap.insert(std::make_pair(2, "cherry"));

遍历：

for (const auto& pair : mmap) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

查找元素：

auto range = mmap.equal_range(1); // 获取所有键为1的元素
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << std::endl; // 输出 apple 和 banana
}

删除元素：

mmap.erase(1); // 删除所有键为1的元素

示例代码

以下是一个完整的示例代码，展示 std::multimap 的基本用法：

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mmap;

    // 插入元素
    mmap.insert(std::make_pair(1, "apple"));
    mmap.insert(std::make_pair(1, "banana"));
    mmap.insert(std::make_pair(2, "cherry"));
    mmap.insert(std::make_pair(3, "date"));
    
    // 遍历并打印元素
    std::cout << "Multimap elements:" << std::endl;
    for (const auto& pair : mmap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找特定键的所有值
    std::cout << "\nValues with key 1:" << std::endl;
    auto range = mmap.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << std::endl; // 输出 apple 和 banana
    }

    // 删除键为1的所有元素
    mmap.erase(1);

    // 打印删除后的元素
    std::cout << "\nAfter erasing key 1:" << std::endl;
    for (const auto& pair : mmap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

注意事项

键的唯一性：虽然同一个键可以有多个值，但键本身在容器中仍然是唯一的。
性能：对于需要频繁插入和删除的场景，std::multimap 提供了相对较高的性能，但在需要大量查找时，std::unordered_multimap（基于哈希表实现）可能会提供更好的性能。

算法模板库中的常用函数

C++ STL（标准模板库）中提供了丰富的算法函数，这些算法函数可以极大地简化编程任务并提高代码的可读性和效率。以下是一些常用且实用的算法函数，按类别进行分类：

1. 排序和排列算法

std::sort: 对容器中的元素进行排序，支持自定义比较函数。

std::vector<int> vec = {5, 2, 9, 1};
std::sort(vec.begin(), vec.end());

std::stable_sort: 稳定排序，保持相等元素的相对顺序。
std::partial_sort: 对部分元素进行排序，前n个元素会被排好序。
std::next_permutation: 生成下一个字典序排列。

2. 查找算法

std::find: 在容器中查找特定值。

auto it = std::find(vec.begin(), vec.end(), 2);

std::binary_search: 在已排序的容器中查找某个值，使用二分查找，时间复杂度为O(log n)。
std::lower_bound 和 std::upper_bound: 在已排序容器中查找第一个不小于（或大于）给定值的元素位置。

3. 修改算法

std::copy: 将元素从一个容器复制到另一个容器。

std::transform: 对容器中的每个元素应用给定的函数，并将结果存储到另一个容器。

std::vector<int> squares;
std::transform(vec.begin(), vec.end(), std::back_inserter(squares), [](int x) { return x * x; });

std::remove: 移除容器中的特定元素，实际上是标记，需结合 erase 使用。
std::fill: 将指定值填充到容器的元素中。

4. 集合算法

std::set_union: 计算两个集合的并集。
std::set_intersection: 计算两个集合的交集。
std::set_difference: 计算两个集合的差集。
std::set_symmetric_difference: 计算两个集合的对称差集。

5. 数值算法

std::accumulate: 对容器中的元素进行累加（或其他二元操作）。
```
int sum = std::accumulate(vec.begin(), vec.end(), 0);
```
std::inner_product: 计算两个容器元素的内积。
std::adjacent_difference: 计算相邻元素的差。

6. 其他常用算法

std::for_each: 对容器中的每个元素应用给定的操作。
std::count: 统计容器中某个值的出现次数。
std::all_of, std::any_of, std::none_of: 检查容器中是否所有、任意或没有元素满足特定条件。

7. 并行算法（C++17及以上）

std::for_each(std::execution::par, ...): 在并行执行上下文中对元素进行操作。
std::sort(std::execution::par, ...): 并行排序容器中的元素。

29 KiB Raw Permalink Blame History Unescape Escape

类

类的概念及简单应用

成员函数和运算符重载

STL模板

容器(container)

迭代器(Iterator)

对(pair)

1. 定义和初始化

2. 成员变量

3. 使用std::make_pair

4. 比较操作

5. 作为容器的元素

6. 结构化绑定（C++17）

7. 应用场景

示例：使用std::pair返回多个值

元组(tuple)

1. 创建和初始化 std::tuple

2. 访问 std::tuple 元素

3. 修改 std::tuple 元素

4. 获取 std::tuple 的元素数量

5. 使用 std::tie 解构 tuple

6. 比较 std::tuple

7. 合并 std::tuple

8. 使用结构化绑定 (C++17)

总结

集合(set)

1. 引入头文件

2. 定义 std::set

3. 插入元素

4. 删除元素

5. 查找元素

6. 大小与清空

7. 遍历 std::set

8. 自定义排序规则

9. 其它常用操作

示例代码

多重集合(multiset)

主要特性

常用操作

示例代码

双端队列(deque)

1. 引入头文件

2. 创建deque

3. 常用操作

3.1 插入元素

3.2 删除元素

3.3 访问元素

3.4 大小和容量

3.5 清空容器

4. 示例代码

5. 注意事项

优先队列(priority_queue)

基本特性

基本操作

自定义比较

映射(map)

1. 基本特性

2. 常用操作

2.1 包含头文件

2.2 创建和初始化

2.3 插入元素

2.4 查找元素

2.5 删除元素

2.6 遍历元素

2.7 其他常用操作

3. 示例代码

多重映射(multimap)

主要特点

常用操作

示例代码

注意事项

算法模板库中的常用函数

1. 排序和排列算法

2. 查找算法

3. 修改算法

4. 集合算法

5. 数值算法

6. 其他常用算法

7. 并行算法（C++17及以上）

29 KiB

Raw Permalink Blame History

3. 使用`std::make_pair`

示例：使用`std::pair`返回多个值

1. 创建和初始化 `std::tuple`

2. 访问 `std::tuple` 元素

3. 修改 `std::tuple` 元素

4. 获取 `std::tuple` 的元素数量

5. 使用 `std::tie` 解构 `tuple`

6. 比较 `std::tuple`

7. 合并 `std::tuple`

2. 定义 `std::set`

7. 遍历 `std::set`

2. 创建`deque`