STL容器

STL序列式容器

array数组

array 容器是 C++ 11 标准中新增的 序列容器，简单地理解，它就是在 C++ 普通数组的基础上，添加了一些成员函数和全局函数。在使用上，它比普通数组更安全，且效率并没有因此变差。

和其它容器不同，array 容器的大小是固定的，无法动态的==扩展==或==收缩==，这也就意味着，在使用该容器的过程无法借由增加或移除元素而改变其大小，它只允许访问或者替换存储的元素。

在 array<T,N> 类模板中，T 用于指明容器中的存储的具体数据类型，N 用于指明容器的大小，需要注意的是，这里的 N 必须是常量，不能用变量表示。

1

std::array<double, 10> values;

array的初始化赋值语法

1

std::array<double, 10> values {0.1,1.4,1.8,,2.4};

这里只初始化了前 4 个元素，剩余的元素都会被初始化为 0.0。

vector容器

vector 容器是 STL 中最常用的容器之一，它和 array 容器非常类似，都可以看做是对 C++ 普通数组的 “升级版”。不同之处在于，array 实现的是==静态数组==（容量固定的数组），而 vector 实现的是一个==动态数组==，即可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间，整个过程无需人工干预。

vector 常被称为向量容器，因为该容器擅长在尾部插入或删除元素，在==常量时间内就可以完成==，时间复杂度为 O(1)；而对于在容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间），时间复杂度为线性阶 O(n)。

vector初始化

1

std::vector<int> numbers = {1, 2, 3, 4, 5};		

deque队列

STL 中的 deque 是双端队列容器，deque 容器和 vector 容器有很多相似之处，deque 容器也==擅长在序列尾部添加或删除元素==（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。deque 容器也可以根据需要修改自身的容量和大小。

和 vector 不同的是，deque 还==擅长在序列头部添加或删除元素==，所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是，deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。

当需要向==序列两端频繁的添加或删除元素==时，应首选 deque 容器。

list链表

STL 中的 list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。

list 容器中各个元素的前后顺序是靠指针来维系的，每个元素都配备了 2 个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null，因为它前面没有元素；同样，尾部元素的后向指针也总为 null。

基于这样的存储结构，list 容器具有一些其它容器（array、vector 和 list）所不具备的优势，==即它可以在序列已知的任何位置快速插入或删除元素==（时间复杂度为O(1)）。并且在 list 容器中移动元素，也比其它容器的效率高。

使用 list 容器的缺点是，==它不能像 array 和 vector 那样，通过位置直接访问元素==。举个例子，如果要访问 list 容器中的第 3 个元素，==它不支持容器对象名[3]这种语法格式==，正确的做法是从容器中第一个元素或最后一个元素开始遍历容器，直到找到该位置。

实际场景中，==如何需要对序列进行大量添加或删除元素的操作==，而直接访问元素的需求却很少，这种情况建议使用 list 容器存储序列。

STL关联式容器

STL 中的关联式容器主要包括 map、multimap、set 以及 multiset。和 序列式容器 不同的是，关联式容器在存储元素时还会为每个元素在配备一个键，整体以键值对的方式存储到容器中。

相比序列式容器，关联式容器可以通过键值直接找到对应的元素，而无需遍历整个容器。另外，关联式容器在存储元素，默认会根据各元素==键值的大小做升序排序==。相比其它类型容器，关联式容器==查找、访问、插入和删除指定元素的效率更高==。

pair

C++ STL 标准库提供了 pair 类模板，其专门用来将 2 个普通元素 first 和 second（可以是 C++ 基本数据类型、结构体、类自定的类型）创建成一个新元素 <first, second>。

通过其构成的元素格式不难看出，使用 pair 类模板来创建 “键值对” 形式的元素，再合适不过。

pair初始化

• 使用花括号

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

	#include <utility>

int main() {
    std::pair<int, double> myPair = {42, 3.14};
    // 或者可以使用构造函数的简化语法
    // std::pair<int, double> myPair{42, 3.14};

    // 使用 myPair 进行操作...

    return 0;				
}

• 使用构造函数

1
2
3
4
5
6
7
8
9

#include <utility>

int main() {
    std::pair<int, double> myPair(42, 3.14);

    // 使用 myPair 进行操作...

    return 0;
}

• 使用make_pair

1
2
3
4
5
6
7
8
9

#include <utility>

int main() {
    std::pair<int, double> myPair = std::make_pair(42, 3.14);

    // 使用 myPair 进行操作...

    return 0;
}

通过pair.first和pair.second分别访问K和V

map

map 做为 关联容器 的一种，存储的都是 pair 对象，也就是用 pair 类模板创建的键值对。其中，各个键值对的键和值可以是任意数据类型，包括 C++ 基本数据类型（int、double 等）、使用结构体或类自定义的类型。

通常情况下，map 容器中存储的各个键值对都选用 string 字符串作为键的类型。

与此同时，在使用 map 容器存储多个键值对时，该容器会自动根据各键值对的键的大小，按照既定的规则进行排序。默认情况下，map 容器选用 std::less<T> 排序规则（其中 T 表示键的数据类型），其会根据键的大小对所有键值对做升序排序。

当然，根据实际情况的需要，我们可以手动指定 map 容器的排序规则，既可以选用 STL 标准库中提供的其它排序规则（比如 std::greater<T>），也可以自定义排序规则。

另外需要注意的是，使用 map 容器存储的各个键值对，==键的值既不能重复也不能被修改==。换句话说，map 容器中存储的各个键值对不仅键的值独一无二，键的类型也会用 const 修饰，这意味着只要键值对被存储到 map 容器中，其键的值将不能再做任何修改。

map 容器存储的都是 pair 类型的键值对元素，更确切的说，该容器存储的都是 pair<const K, T> 类型（其中 K 和 T 分别表示键和值的数据类型）的键值对元素。

map初始化

• 使用初始化列表：

• 使用迭代器范围初始化：

• 使用插入操作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <map>

int main() {
    std::map<int, std::string> myMap;

    myMap.insert(std::make_pair(1, "one"));
    myMap.insert(std::make_pair(2, "two"));
    myMap.insert(std::make_pair(3, "three"));

    // 使用 myMap 进行操作...

    return 0;
}

set

STL 中的 set 也是一种 关联式容器，其用来存储一组不重复的元素集合，而且，set 存储元素和 map 以及 multimap 类似，==都是有序的==。

从语法上讲 set 容器并没有强制对存储元素的类型做 const 修饰，即 set 容器中存储的元素的值是可以修改的。但是，C++ 标准为了防止用户修改容器中元素的值，对所有可能会实现此操作的行为做了限制，使得在正常情况下，用户是无法做到修改 set 容器中元素的值的。

对于初学者来说，切勿尝试直接修改 set 容器中已存储元素的值，这很有可能破坏 set 容器中元素的有序性，最正确的修改 set 容器中元素值的做法是：先删除该元素，然后再添加一个修改后的元素。

set初始化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#使用初始化列表
std::set<int> mySet = {1, 2, 3, 4, 5};

#使用插入初始化
std::set<int> mySet;
mySet.insert(1);
mySet.insert(2);
mySet.insert(3);
mySet.insert(4);
mySet.insert(5);

STL无序关联式容器

unordered_map

unordered_map 容器，直译过来就是 “无序 map 容器” 的意思。所谓 “无序”，指的是 unordered_map 容器不会像 map 容器那样对存储的数据进行排序。

换句话说，unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。

具体来讲，unordered_map 容器和 map 容器一样，以键值对，即 pair 类型 的形式存储数据，存储的各个键值对的键互不相同且不允许被修改。

但由于 unordered_map 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。

unordered_set

unordered_set 容器，可直译为 “无序 set 容器”，即 unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。

STL unordered_set特征

1. 不再以键值对的形式存储数据，而是直接存储数据的值。
2. 容器内部存储的各个元素的值都互不相等，且不能被修改。
3. 不会对内部存储的数据进行排序。

容器的常见操作

排序

要对 std::vector 进行排序，可以使用标准库提供的排序算法 std::sort。std::sort 函数可以按升序对容器中的元素进行排序。以下是对 std::vector 进行排序的示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> myVector = {5, 2, 3, 1, 4};

    // 使用 std::sort 对容器进行排序
    std::sort(myVector.begin(), myVector.end());

    // 输出排序后的结果
    for (const auto& element : myVector) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    return 0;
}

遍历

迭代器遍历unordered_map，迭代器是一个类似指针的对象。在 C++ 中，迭代器是一种抽象的概念，它提供了一组操作符（如 * 和 ++）来访问容器中的元素。迭代器可以被视为容器内部的指针，它指向容器中的某个元素或位置。

对于 std::unordered_map 容器，myMap.begin() 返回的是一个迭代器，指向容器中第一个键值对的位置。通过解引用迭代器，可以获取该位置上的键值对。

遍历vector容器，通过* 解引用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <iostream>
#include <vector>

int main() {
    std::vector<int> myVector = {1, 2, 3, 4, 5};

    // 使用迭代器遍历容器
    for (auto it = myVector.begin(); it != myVector.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}