登录以参加训练计划

链表——list

链表：需要双向操作或频繁在任意位置插入，可以选择链表这种数据结构。

创建链表​

#include<list>
list<int> myList;  // 创建空链表，名字叫 myList

添加元素

myList.push_back(10);  // 在末尾加（值=10）
myList.push_front(5);  // 在开头加（值=5）

指定位置前添加元素

auto it = myList.begin();  // 让 it 指向第一个
it++;                      // it 现在指向第二
myList.insert(it, 7);      // 在 it 前面插入 7

遍历链表

for (int pearl : myList) {  // 对每颗珍珠做事情
    cout << pearl << " ";
}
// 输出：7 10

删除链表元素

myList.pop_front();  // 删除开头
myList.pop_back();  // 删除结尾元素

队列——queue

在 C++ 中，有queue、deque 和 priority_queue，虽然都叫队列，但它们底层实现机制是不一样的：

• queue：它是一个先进先出（FIFO）的数据结构，底层通常由动态数组或链表实现。
• deque：它是一个双端队列，既可以在前面插入也可以在后面插入，删除元素也同样可以在两端进行。底层通常由一段段定长的数组组成，当需要增长时，会新增一段更长的数组，并将原数据移动到新数组中。
• priority_queue：它是一个堆实现的，底层通常用堆来管理数据。

尽管 queue 和 priority_queue 底层实现机制不同，但是它们对外的接口是一致的，也就是说，你可以使用 push()、front()、back()、pop() 等操作来操作它们，但 priority_queue 会保证队列顶部是最大（或最小）的元素。

deque 和 queue 的区别在于，deque 允许在任何位置高效地插入和删除，而 queue 只能在队尾插入，队首删除。

因此，尽管 queue、deque 和 priority_queue 底层实现机制不同，但是它们的用法是类似的。

以下是一个使用 queue 的例子：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    // 入队
    q.push(1);
    q.push(2);
    q.push(3);

    // 输出队首元素
    std::cout << "Front: " << q.front() << std::endl;

    // 出队
    q.pop();

    // 输出队首元素
    std::cout << "Front after pop: " << q.front() << std::endl;

    return 0;
}

对于 priority_queue，它会自动将最大（或最小）的元素放在顶部，以下是一个使用 priority_queue 的例子：

#include <iostream>
#include <queue>
#using 
int main() {
    std::priority_queue<int> q;

    // 入队
    q.push(3);
    q.push(1);
    q.push(2);

    // 输出队首元素，因为是 priority_queue，所以是最大的元素
    std::cout << "Front: " << q.top() << std::endl;

    // 出队
    q.pop();

    // 输出队首元素
    std::cout << "Front after pop: " << q.top() << std::endl;

    return 0;
}

pair

在 C++ 中，std::pair 是一个容器适配器，用于存储两个值的组合。pair 通常用于需要关联两个数据项的场景，例如：

1. 关联键值对：

   • pair 可以用于存储类似于字典或映射中的键值对。
   • 例如，std::map 和 std::unordered_map 中的元素就是 pair。

2. 算法返回值：

   • 许多 C++ 标准库算法（如 std::minmax）返回 pair 类型的值，表示一对相关的结果。

3. 数据结构中的元素：

   • 在需要同时处理两个相关数据时，pair 可以作为一个元素类型。

4. 状态表示：

   • 在算法中，pair 可以表示某种状态或条件，例如在图论中表示一个边的两个端点。

pair 的基本用法

创建 pair 对象

std::pair<int, int> p1(1, 2); // 直接构造
std::pair<int, int> p2 = make_pair(3, 4); // 使用 make_pair 构造
std::pair<int, int> p3 = {5, 6}; // C++11 以后可以直接初始化