【C++】STL梳理

0x1 C++ STL

C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。

C++ 标准模板库的核心包括以下三个组件：

• 容器（Containers）：用来管理某类对象的集合。每一种容器都有其优点和缺点，所以为了应付程序中的不同需求，STL 准备了七种基本容器类型。
• 迭代器（Iterators）：用来在一个对象集合的元素上进行遍历动作。这个对象集合或许是个容器，或许是容器的一部分。每一种容器都提供了自己的迭代器，而这些迭代器了解该种容器的内部结构。
• 算法（Algorithms）：用来处理对象集合中的元素，比如 Sort，Search，Copy，Erase 那些元素。通过迭代器的协助，我们只需撰写一次算法，就可以将它应用于任意容器之上，这是因为所有容器的迭代器都提供一致的接口。

STL 的基本观念就是将数据和操作分离。数据由容器进行管理，操作则由算法进行，而迭代器在两者之间充当粘合剂，使任何算法都可以和任何容器交互运作。

0x2 C++ STL常用容器

为了应付程序中的不同需求，STL 准备了两类共七种基本容器类型：

• 序列式容器（Sequence containers）：此为可序群集，其中每个元素均有固定位置—取决于插入时机和地点，和元素值无关。如果你以追加方式对一个群集插入六个元素，它们的排列次序将和插入次序一致。STL提供了三个序列式容器：向量（vector）、双端队列（deque）、列表（list），此外你也可以把 string 和 array 当做一种序列式容器。
• 关联式容器（Associative containers）：此为已序群集，元素位置取决于特定的排序准则以及元素值，和插入次序无关。如果你将六个元素置入这样的群集中，它们的位置取决于元素值，和插入次序无关。STL提供了四个关联式容器：集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）。

对于容器，主要的操作有：容器的建立、插入元素、删除元素、查询、遍历、计算元素个数、检查元素是否为空、输出容器包含的内容。

0x3 vector

一种序列式容器，事实上和数组差不多，但它比数组更优越。一般来说数组不能动态拓展，因此在程序运行的时候不是浪费内存，就是造成越界。而 vector 正好弥补了这个缺陷，当内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。

0x31 特点

• 拥有一段连续的内存空间，因此它能非常好的支持随机访问，即 [] 操作符和 .at()，随机访问快。（优点）
• 当向其头部或中间插入或删除元素时，为了保持原本的相对次序，插入或删除点之后的所有元素都必须移动，所以插入或删除的效率比较低。（缺点）
• 在后面插入删除元素最快，此时一般不需要移动内存。（优点）

总结：相当于可拓展的数组（动态数组），随机访问快，在头部和中间插入或删除效率低，但在尾部插入或删除效率高，适用于对象简单，变化较小，并且频繁随机访问的场景。

0x32 构造函数

• vector() ：无参数 - 构造一个空的vector
• vector(size_type num) ：数量(num) - 构造一个大小为num，值为Type默认值的Vector
• vector(size_type num, const TYPE &val)：数量(num)和值(val) - 构造一个初始放入num个值为val的元素的Vector
• vector(const vector &from) ：vector(from) - 构造一个与vector from 相同的vector
• vector(input_iterator start, input_iterator end)：迭代器(start)和迭代器(end) - 构造一个初始值为[start,end)区间元素的Vector(注:半开区间).
• vector(initializer_list<value_type> il, const allocator_type& alloc = allocator_type())C++11新提供的方法，类似如下方式：
• std::vector<int>a{1, 2, 3, 4, 5}
• std::vector<int>a = {1, 2, 3, 4, 5}

0x33 常用API

• Operators : 对vector进行赋值或比较
• v1 == v2
• v1 != v2
• v1 <= v2
• v1 >= v2
• v1 < v2
• v1 > v2
• v[]
• assign()：对Vector中的元素赋值
• at() : 返回指定位置的元素
• back() : 返回最末一个元素
• begin() : 返回第一个元素的迭代器
• capacity() : 返回vector所能容纳的元素数量(在不重新分配内存的情况下）
• clear() : 清空所有元素
• empty() : 判断Vector是否为空（返回true时为空）
• end() : 返回最末元素的迭代器(译注:实指向最末元素的下一个位置)
• erase() : 删除指定元素
• front() : 返回第一个元素
• get_allocator() : 返回vector的内存分配器
• insert() : 插入元素到Vector中
• max_size() : 返回Vector所能容纳元素的最大数量（上限）
• pop_back() : 移除最后一个元素
• push_back() : 在Vector最后添加一个元素
• rbegin() : 返回Vector尾部的逆迭代器
• rend() : 返回Vector起始的逆迭代器
• reserve() : 设置Vector最小的元素容纳数量
• resize() : 改变Vector元素数量的大小
• size() : 返回Vector元素数量的大小
• swap() : 交换两个Vector

0x34 example

#include <iostream>
#include <vector>

using namespace std;

int main() {

    vector<int> vecTemp;

    for (int i = 0; i < 6; i++) {
        vecTemp.push_back(i);
    }

    for (int i = 0; i < vecTemp.size(); i++) {
        cout << vecTemp[i] << " "; // 输出：0 1 2 3 4 5
    }
    
    std::cout << '\n';

    return 0;
}

Output

0 1 2 3 4 5

0x4 deque

deque是Double-Ended Queues(双向队列)的缩写，是双向开口的连续内存空间（动态将多个连续空间通过指针数组接合在一起），随时可以增加一段新的空间。deque 的最大任务就是在这些分段的连续空间上，维护其整体连续的假象，并提供随机存取的接口。

0x41 特点

• 一旦要在 deque 的头部和尾部增加新空间，便配置一段定量连续空间，串在整个 deque 的头部或尾部，因此不论在头部或尾部插入元素都十分迅速。 (优点）
• 在中间部分安插元素则比较费时，因为必须移动其它元素。（缺点）
• deque 是 list 和 vector 的折中方案。兼有 list 的优点，也有 vector 随机访问效率高的优点。

总结：支持随机访问，但效率没有 vector 高，在头部和尾部插入或删除效率高，但在中间插入或删除效率低，适用于既要频繁随机访问，又要关心两端数据的插入与删除的场景。

0x42 构造函数

• deque<T> queT：queue采用模板类实现，queue对象的默认构造形式
• deque<T> queT(size)：构造大小为size的deque，其中值为T类型的默认值
• deque<T> queT(size, val)：构造大小为size的deque，其中值为val
• deque(const deque &que)：拷贝构造函数
• deque(input_iterator start, input_iterator end)：迭代器构造函数

0x43 常用API

• back()：返回最后一个元素
• front()：返回第一个元素
• insert()
• pop_back()： 删除尾部的元素
• pop_front()： 删除头部的元素
• push_back()：在尾部加入一个元素
• push_front()： 在头部加入一个元素
• at()：访问指定位置元素
• operator[] (size_type n)：重载[]操作符
• empty()：判断队列是否为空
• size()：返回队列的大小

0x44 example

#include <iostream>
#include <deque>

using namespace std;

int main() {

    std::deque<int> first;                   /// 默认构造形式
    std::deque<int> second(5, 200);     /// 构造大小为5的deque，其中值为200
    std::deque<int> third(second.begin(), second.end());    /// 迭代器构造函数
    std::deque<int> fourth(third);           /// 拷贝构造函数

    /// 迭代器构造函数可用于复制数组
    int myInts[] = {19, 20, 21, 22};
    std::deque<int> fifth(myInts, myInts + sizeof(myInts) / sizeof(int));

    std::cout << "The contents of fifth are:";
    for (std::deque<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
        std::cout << ' ' << *it;

    std::cout << '\n';

    return 0;
}

Output

The contents of fifth are: 19 20 21 22

0x5 list

List 由双向链表（doubly linked list）实现而成，元素存放在堆中，每个元素都是放在一块内存中。没有空间预留习惯，所以每分配一个元素都会从内存中分配，每删除一个元素都会释放它占用的内存。

0x51 特点

• 内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随机存取变得非常没有效率，因此它没有提供 [] 操作符的重载。（缺点）
• 由于链表的特点，在任意位置的插入和删除效率都较高。（优点）
• 只支持首尾两个元素的直接存取，想获取其他元素（访问时间一样），则需要遍历链表。（缺点）

总结：不支持随机访问，在任意位置的插入和删除效率都较高，适用于经常进行插入和删除操作并且不经常随机访问的场景。

0x52 构造函数

• list (const allocator_type& alloc = allocator_type())
• list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type())
• template <class InputIterator> list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())
• list (const list& x)

0x53 常用API

• assign() ：给list赋值
• back() ：返回最后一个元素
• begin() ：返回指向第一个元素的迭代器
• clear() ：删除所有元素
• empty() ：如果list是空的则返回true
• end() ：返回末尾的迭代器
• erase() ：删除一个元素
• front() ：返回第一个元素
• get_allocator() ：返回list的配置器
• insert() ：插入一个元素到list中
• max_size() ：返回list能容纳的最大元素数量
• merge() ：合并两个list
• pop_back() ：删除最后一个元素
• pop_front() ：删除第一个元素
• push_back() ：在list的末尾添加一个元素
• push_front() ：在list的头部添加一个元素
• rbegin() ：返回指向第一个元素的逆向迭代器
• remove() ：从list删除元素
• remove_if() ：按指定条件删除元素
• rend() ：指向list末尾的逆向迭代器
• resize() ：改变list的大小
• reverse() ：把list的元素倒转
• size() ：返回list中的元素个数
• sort() ：给list排序
• splice() ：合并两个list
• swap() ：交换两个list
• unique() ：删除list中重复的元素

0x54 example

#include <iostream>
#include <list>

using namespace std;

int main() {

    list<char> listTemp;

    for (char c = 'a'; c <= 'z'; ++c)
        listTemp.push_back(c);

    while (!listTemp.empty()) {
        cout << listTemp.front() << " ";
        listTemp.pop_front();
    }

    return 0;
}

Output

a b c d e f g h i j k l m n o p q r s t u v w x y z 

0x6 set

set（集合）顾名思义，就是数学上的集合，集合中以一种特定的顺序保存唯一的元素。

0x61 特点

• 使用红黑树实现，其内部元素依据其值自动排序，每个元素值只能出现一次，不允许重复。
• 每次插入值的时候，都需要调整红黑树，效率有一定影响。（缺点）
• map 和 set 的插入或删除效率比用其他序列容器高，因为对于关联容器来说，不需要做内存拷贝和内存移动。（优点）

总结：由红黑树实现，其内部元素依据其值自动排序，每个元素值只能出现一次，不允许重复，且插入和删除效率比用其他序列容器高，适用于经常查找一个元素是否在某集合中且需要排序的场景。

0x62 构造函数

• set()：无参数 - 构造一个空的set
• set(InputIterator first, InputIterator last) ：迭代器的方式构造set
• set(const set &from) ：copyd的方式构造一个与set from 相同的set
• set(input_iterator start, input_iterator end) ：迭代器(start)和迭代器(end) - 构造一个初始值为[start,end)区间元素的Vector(注:半开区间).
• set (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())C++11新提供的方法，类似如下方式：
• std::set<int>a{1, 2, 3, 4, 5};

0x63 常用API

• begin() ：返回指向第一个元素的迭代器
• clear() ：清除所有元素
• count() ：返回某个值元素的个数
• empty() ：如果集合为空，返回true
• end() ：返回指向最后一个元素的迭代器
• equal_range() ：返回集合中与给定值相等的上下限的两个迭代器
• erase() ：删除集合中的元素
• find() ：返回一个指向被查找到元素的迭代器
• get_allocator() ：返回集合的分配器
• insert() ：在集合中插入元素
• lower_bound() ：返回指向大于（或等于）某值的第一个元素的迭代器
• key_comp() ：返回一个用于元素间值比较的函数
• max_size() ：返回集合能容纳的元素的最大限值
• rbegin() ：返回指向集合中最后一个元素的反向迭代器
• rend() ：返回指向集合中第一个元素的反向迭代器
• size() ：集合中元素的数目
• swap() ：交换两个集合变量
• upper_bound() ：返回大于某个值元素的迭代器
• value_comp() ：返回一个用于比较元素间的值的函数

0x64 example

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> setTemp;

    setTemp.insert(3);
    setTemp.insert(1);
    setTemp.insert(2);
    setTemp.insert(1);


    for (int it : setTemp) {
        cout << it << " ";
    }

    return 0;
}

Output

1 2 3 

当 set 集合中的元素为结构体时，该结构体必须实现运算符 < 的重载：

#include <set>
#include <string>

using namespace std;

struct People {
    string name;
    int age;

    bool operator<(const People p) const {
        return age < p.age;
    }
};

int main(int argc, char *argv[]) {
    set<People> setTemp;

    setTemp.insert({"天理", 19});
    setTemp.insert({"天工", 20});
    setTemp.insert({"天大", 21});
    setTemp.insert({"南开", 18});

    set<People>::iterator it;
    for (it = setTemp.begin(); it != setTemp.end(); it++) {
        printf("学校：%s 就读年龄：%d\n", (*it).name.c_str(), (*it).age);
    }

    return 0;
}

Output

学校：南开 就读年龄：18
学校：天理 就读年龄：19
学校：天工 就读年龄：20
学校：天大 就读年龄：21

可以看到结果是按照年龄由小到大的顺序排列。另外 string 要使用c_str()转换一下，否则打印出的是乱码。

Multiset 和 set 相同，只不过它允许重复元素，也就是说 multiset 可包括多个数值相同的元素。这里不再做过多介绍。

0x7 map

map 由红黑树实现，其元素都是 “键值/实值” 所形成的一个对组（key/value pairs)，map 内部自建一颗红黑树，这颗树具有对数据自动排序的功能，所以在 map 内部所有的数据都是有序的。

0x71 特点

• 每个元素都有一个键，且只能出现一次，不允许重复。
• 根据 key 值快速查找记录，查找的复杂度基本是 O(logN)，如果有 1000 个记录，二分查找最多查找 10次(1024)。（优点）
• 每次插入值的时候，都需要调整红黑树，效率有一定影响。（缺点）
• 增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。（优点）
• 对于迭代器来说，可以修改实值，而不能修改 key。

总结：元素为键值对，key 和 value 可以是任意你需要的类型，每个元素都有一个键，且只能出现一次，不允许重复，根据 key 快速查找记录，适用于需要存储一个数据字典，并要求方便地根据key找value的场景。

0x72 构造函数

• map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())
• template <class InputIterator> map (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type())
• map (const map& x)
• map (const map& x, const allocator_type& alloc)
• map (map&& x)
• map (map&& x, const allocator_type& alloc)
• map (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())

0x73 常用API

• begin() ：返回指向map头部的迭代器
• clear() ：删除所有元素
• count() ：返回指定元素出现的次数
• empty() ：如果map为空则返回true
• end() ：返回指向map末尾的迭代器
• equal_range() ：返回特殊条目的迭代器对
• erase() ：删除一个元素
• find() ：查找一个元素
• get_allocator() ：返回map的配置器
• insert() ：插入元素–
• key_comp() ：返回比较元素key的函数
• lower_bound() ：返回键值>=给定元素的第一个位置
• max_size() ：返回可以容纳的最大元素个数
• rbegin() ：返回一个指向map尾部的逆向迭代器
• rend() ：返回一个指向map头部的逆向迭代器
• size() ：返回map中元素的个数
• swap() ：交换两个map
• upper_bound() ：返回键值>给定元素的第一个位置
• value_comp() ：返回比较元素value的函数

0x74 example

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    map<int, string> mapTemp;

    mapTemp.insert({1, "后端码匠"});
    mapTemp.insert({2, "音视频开发"});
    mapTemp.insert({3, "后端开发"});
    mapTemp.insert({4, "前端开发"});
    mapTemp.insert({4, "客户端开发"});

    map<int, string>::iterator it;
    for (it = mapTemp.begin(); it != mapTemp.end(); it++) {
        printf("编号：%d 岗位：%s\n", (*it).first, (*it).second.c_str());
    }

    return 0;
}

Output

编号：1 岗位：后端码匠
编号：2 岗位：音视频开发
编号：3 岗位：后端开发
编号：4 岗位：前端开发

multimap 和 map 相同，但允许重复元素，也就是说 multimap 可包含多个键值（key）相同的元素。这里不再做过多介绍。

0x8 容器配接器

除了以上七个基本容器类别，为满足特殊需求，STL还提供了一些特别的（并且预先定义好的）容器配接器，根据基本容器类别实现而成。包括：

0x81 stack

stack（堆栈）实现了一个先进后出（FILO）的数据结构。

0x811 构造函数

• stack<T> stkT ：采用模板类实现，stack对象的默认构造形式
• stack(const stack &stk) ：拷贝构造函数

0x812 常用API

• size()：返回栈中的元素数
• top()：返回栈顶的元素
• pop()：从栈中取出并删除元素
• push(x)：向栈中添加元素x
• empty()：在栈为空时返回true

0x82 queue

queue 容器对元素采取 FIFO（先进先出）的管理策略。也就是说，它是个普通的缓冲区（buffer）。

0x821 构造函数

• explicit queue (const container_type& ctnr)
• explicit queue (container_type&& ctnr = container_type())
• template <class Alloc> explicit queue (const Alloc& alloc)
• template <class Alloc> queue (const container_type& ctnr, const Alloc& alloc)
• template <class Alloc> queue (container_type&& ctnr, const Alloc& alloc)
• template <class Alloc> queue (const queue& x, const Alloc& alloc)
• template <class Alloc> queue (queue&& x, const Alloc& alloc)

0x822 常用API

• back() ：返回最后一个元素
• empty() ：如果队列空则返回真
• front()：返回第一个元素
• pop()：删除第一个元素
• push()：在末尾加入一个元素
• size()：返回队列中元素的个数

0x83 priority_queue

优先队列类似队列， 但是在这个数据结构中的元素按照一定的规则排列有序。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高优先级先出 （first in, largest out）的行为特征。首先要包含头文件#include, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。

0x831 构造函数

priority_queue<Type, Container, Functional>：

• Type 就是数据类型，
• Container 就是容器类型（Container必须是具备随机存取能力的容器，支持如下方法：empty(), size(), front(), push_back(),pop_back()。比如vector,deque等等，但不能用list。STL里面默认用的是vector）。可选
• Functional 就是比较的方式。可选

0x832 常用API

• top() ：访问队头元素
• empty() ：队列是否为空
• size() ：返回队列内元素个数
• push() ：插入元素到队尾 (并排序)
• emplace() ：原地构造一个元素并插入队列
• pop() ：弹出队头元素
• swap() ：交换内容