Containers

简介

容器是用来存储数据的序列，每个容器都作为模板类实现。不同的容器提供了不同的存储方式和访问模式。一般分为 4 种类型：

  • 序列容器：是指那些在容器中按顺序存放元素的容器类。

    • std::array 是一种固定大小的数组容器，与 C 语言中的数组相比，具有更好的类型安全和内存管理特性。支持快速随机访问
    • std::vector 是一种连续存储动态数组，可以在运行时根据需要动态调整大小。自动管理内存，不需要手动分配和释放。支持快速随机访问
    • std::deque 全称是 double-ended queue ，是一个动态数组，它提供了快速的随机访问能力，同时允许在两端进行高效的插入和删除操作
    • std::list 将数据存储在非连续内存中。容器中的每个元素都通过指针指向前一个元素和后一个元素，称为双向链表。链表只提供了从第一个元素或最后一个元素访问容器的方法——即不支持元素的随机访问。
    • std::forward_list 也像 list 一样以顺序方式存储数据，但不同之处在于forward_list 仅存储序列中下一个元素的位置。它实现了单向链表

  • 关联容器：会在新元素插入时自动排序，可实现快速搜索

    • std::set：是一种用于存储唯一元素的有序集合，底层使用红黑树实现
    • std::multiset：是一种允许重复元素的有序集合
    • std::map：是一种有序的键值对容器，按键排序，且键是唯一的。这使得它非常适合需要快速查找、插入和删除的场景
    • std::multimap：键值对的有序集合，允许重复的键

  • 无序关联容器：实现可快速搜索的未排序（哈希）数据结构

    • std::unordered_set：无序集合
    • std::unordered_multiset：无序多重集合
    • std::unordered_map：无序映射
    • std::unordered_multimap：无序多重映射

  • 容器适配器：用于将一种容器或适配成另一种容器

    • std::stack 是一种后进先出的数据结构，容器内的元素是线性排列的，但只允许在一端（栈顶）进行添加和移除操作
    • std::queue 是一种先进先出的数据结构，它允许在一端添加元素（称为队尾），并在另一端移除元素（称为队首）。
    • std::priority_queue

vector

vector 是一种连续存储动态数组，可以在运行时根据需要动态调整大小。自动管理内存，不需要手动分配和释放。

#include <vector>

std::vector<type> myVec;

vector 可通过多种方式进行初始化

Constructor Description
vector() 创建一个空的容器
vector(n) 创建一个包含 n 个默认值元素的容器
vector(n, value) 创建一个包含 n 个值为 value 的容器
vector(il) 使用初始化列表 il 构造容器 
// Creating an empty vector
vector<int> v;

// Creating a vector of 5 elements from initializer list
vector<int> v = {1, 4, 2, 3, 5};

// Creating a vector of size 5 where each element initialized to 9
vector<int> v(5, 9);

// Initialize the std::vector v by arr
int arr[] = {11, 23, 45, 89};
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> v = {arr, arr + n};

// Initialize the vector v2 from vector v1 
vector<int> v1 = {11, 23, 45, 89};
vector<int> v2(v1.begin(), v1.end());

以下是 std::vector 的一些常用成员函数：

Function Description
operator[pos] 返回指定位置的元素，不带边界检查
at(pos) 返回指定位置的元素，带边界检查
front() 返回第一个元素
back() 返回最后一个元素
data() 返回指向底层数组的指针
size() 返回当前元素数量
capacity() 返回当前分配的容量
reserve(n) 预留至少 n 个元素的存储空间
resize(n) 更改向量的大小
empty() 检查向量是否为空
clear() 清空所有元素
insert(pos_iter, val)
insert(pos_iter, n, val)
insert(pos_iter, first, last)		 在指定位置插入元素
erase(pos_iter)
erase(first, last)		 删除指定位置或范围的元素
push_back(val) 在末尾添加元素
pop_back() 删除末尾元素
begin() / end() 返回指向向量的第一个/最后一个元素的迭代器 
#include<iostream>
#include<vector> 
using namespace std;

int main() {
    // Initializing the array elements
    vector<char> vec = {'a', 'c', 'f', 'd', 'z'};

    // Printing number of vector elements
    cout << "The number of vector elements is : ";
    cout << vec.size() << endl;

    // Printing vector elements
    for (int element : vec) {
        cout << element << " ";
    }
    cout << endl;

    // Accessing and printing values
    cout << "Acessing value at index 3 using at() : ";
    cout << vec.at(2) << " " << endl; 
    cout << "Acessing value at index 3 using operator[] : ";
    cout << vec[2] << " " << endl; 
    cout << "Acessing value at 3 using iterator : "
    cout << *(vec.begin() + 2) << " " << endl; 

    // Accessing value at invalid index 10
    try {
        cout << vec.at(10) << std::endl;  
    } catch (const out_of_range& e) {
        cout << "Exception: " << e.what() << endl;
    }

    // Modify the element at index 2
    vec[2] = 'F';
    vec.at(2) = 'F';
    *(vec.begin() + 2) = 'F';

    // Printing first element of vector 
    cout << "First element of vector is : ";
    cout << "First element: " << vec.front() << endl;

    // Printing last element of vector 
    cout << "Last element of vector is : ";
    cout << "Last element: " << vec.back() << endl;

    // Inserting 'z' at the back
    vec.push_back('z'); 

    // Inserting 'c' at index 1
    vec.insert(vec.begin() + 1, 'c');

    // Find the element 'f'
    auto it = find(vec.begin(), vec.end(), 'f');
    cout << *it << endl;

    // Deleting element 'f'
    vec.erase(find(vec.begin(), vec.end(), 'f'));

    return 0;
}

list

list 将数据存储在非连续内存中。容器中的每个元素都通过指针指向前一个元素和后一个元素，称为双向链表。链表只提供了从第一个元素或最后一个元素访问容器的方法——即不支持元素的随机访问。

#include <list>

std::list<type> myList;

list 和 vector一样，可通过多种方式进行初始化。

以下是 std::list 的一些常用的成员函数：

Function Description
push_back(val) 在链表末尾添加元素
push_front(val) 在链表头部添加元素
pop_back() 删除链表末尾的元素
pop_front() 删除链表头部的元素
insert(pos_iter, val)
insert(pos_iter, n, val)
insert(pos_iter, first, last)		 在指定位置插入元素
erase(pos_iter)
erase(first, last)		 删除指定位置或范围的元素
clear() 清空所有元素
size() 返回链表中的元素数量
empty() 检查链表是否为空
front() 返回链表第一个元素
back() 返回链表最后一个元素
remove(val) 删除所有等于指定值的元素
sort() 对链表中的元素进行排序
merge(other) 合并另一个已排序的链表
reverse() 反转链表
begin() / end() 返回容器的起始/结束迭代器 
#include <iostream>
#include <list>
using namespace std;

int main() {
    std::list<int> lst = {10, 20, 30};

    // Inserting an element at the end
    lst.push_back(5);

    // Inserting an element at the beginning
    lst.push_front(1);

    // Inserting an element at a specific position
    auto it = lst.begin();
    advance(it, 2);
    lst.insert(it, 4);

    // Deleting last element
    lst.pop_back();

    // Deleting first element
    lst.pop_front();

    return 0;
}

合并两个已排序的链表

#include <iostream>
#include <list>
using namespace std;

int main() {
    // declaring the lists 
    // initially sorted 
    list<int> list1 = { 10, 20, 30 }; 
    list<int> list2 = { 40, 50, 60 }; 

    // merge operation 
    list2.merge(list1); 

    return 0;
}

set

set 是一种用于存储唯一元素的有序集合，特别适合需要快速查找、插入和删除操作的场景。

#include <set>

std::set<type> mySet;
std::set<type, comp> mySet;

以下是 std::list 的一些常用的成员函数：

Function Description
insert(val)
insert(first, last)
insert({val1,val2,...})		 插入元素
emplace(val) 将新元素插入容器中
erase(val)
erase(pos_iter)
erase(first, last)		 删除指定位置或范围的元素
clear() 清空所有元素
size() 返回容器中的元素数量
empty() 检查容器是否为空
find(key) 查找集合中的元素
contains(key) 查看元素是否存在
count(key) 返回指定元素的计数
merge(other) 将一个 Set 合并到另一个 Set
equal_range(key)
upper_bound(key) 大于key的第一个元素的迭代器
lower_bound(key) 小于key的第一个元素的迭代器
begin() / end() 返回容器的起始/结束迭代器

我们不能像 vector 中那样按索引访问集合的元素。在 set 中，我们必须分别递增或递减从 begin() 或  end() 方法获取的迭代器，才能按位置访问元素。也可以在 next()  或 advance() 函数的帮助下完成。

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 4, 2, 3, 5};

    // Accessing first element
    auto it1 = s.begin();

    // Accessing third element
    auto it2 = next(it1, 2);

    cout << *it1 << " " << *it2;
    return 0;
}

元素的插入

#include <iostream>
#include <set>
#include <vector>

int main() {
    // Create an empty set
    std::set<int> st;

    // Insert elements into set
    st.insert(5);
    st.emplace(3);
    st.insert(5);

    // Insting the multiple values
    st.insert({12, 45, 11, 78, 9}); 

    // Inserting values of vector to set
    std::vector<int> vec = {1, 2, 3};
    st.insert(vec.begin(), vec.end());
}

查找指定值是否存在

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s = {1, 3, 5, 7, 9};
    int x = 5;

    // Check if the element exists using find()
    if (s.find(x) != s.end()) {
        cout << "Element found";
    } else {
        cout << "Element not found";
    }

    // Check if the element exists using count()
    if (s.count(x) > 0) {
        cout << "Element found";
    } else {
        cout << "Element not found";
    }

    // Check if element exists using contains()
    if (s.contains(x)) {
        cout << "Element found";
    } else {
        cout << "Element not found";
    }

    return 0;
}

map

map 是一种有序的键值对容器，容器中的元素是按照键的顺序自动排序的，这使得它非常适合需要快速查找和有序数据的场景。

#include <map>

std::map<key_type, value_type, comp> myMap;

声明和初始化 map 的不同方法

#include <map>
using namespace std;

int main() {
    // Inializing std::map using initializer list
    map<int, char> m = {{1, 'a'},
                        {3, 'b'},
                        {2, 'c'}};

    
    // Create and initialize the map with vector
    vector<pair<int, char>> v = {{1, 'a'},
                                 {3, 'b'}, 
                                 {2, 'c'}};

    map<int, char> m(v.begin(), v.end());

    for (auto& p : m)
        cout << p.first << " " << p.second << "\n";
}

以下是 std::map 的一些常用成员函数：

Function Description
operator[key] 返回或修改指定key的元素
at(key) 返回或修改指定key的元素，带边界检查
size() 返回当前元素数量
insert({key, val})
insert(first, last)
`insert(