【C++】STL梳理-阿里云开发者社区

0x1 C++ STL0x1 C++ STL

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

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

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

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

00x2 C++ STL常用容器x2 C++ STL常用容器

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

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

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

0x3 vector0x3 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 il, const allocator_type& alloc = allocator_type())C++11新提供的方法，类似如下方式：

std::vectora{1, 2, 3, 4, 5}
std::vectora = {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

00x4 dequex4 deque

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

0x41 特点

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

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

0x42 构造函数

deque queT：queue采用模板类实现，queue对象的默认构造形式
deque queT(size)：构造大小为size的deque，其中值为T类型的默认值
deque 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 list0x5 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 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 set0x6 set0x6 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 il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())C++11新提供的方法，类似如下方式：

std::seta{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 map0x7 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 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 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 容器配接器0x8 容器配接器

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

0x81 stack

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

0x811 构造函数

stack 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 explicit queue (const Alloc& alloc)
template queue (const container_type& ctnr, const Alloc& alloc)
template queue (container_type&& ctnr, const Alloc& alloc)
template queue (const queue& x, const Alloc& alloc)
template 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 就是容器类型（Container必须是具备随机存取能力的容器，支持如下方法：empty(), size(), front(), push_back(),pop_back()。比如vector,deque等等，但不能用list。STL里面默认用的是vector）。可选
Functional 就是比较的方式。可选

0x832 常用API

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

【C++】STL梳理

0x1 C++ STL0x1 C++ STL

00x2 C++ STL常用容器x2 C++ STL常用容器

0x3 vector0x3 vector

0x31 特点

0x32 构造函数

0x33 常用API

0x34 example

00x4 dequex4 deque

0x41 特点

0x42 构造函数

0x43 常用API

0x44 example

0x5 list0x5 list

0x51 特点

0x52 构造函数

0x53 常用API

0x54 example

0x6 set0x6 set0x6 set

0x61 特点

0x62 构造函数

0x63 常用API

0x64 example

0x7 map0x7 map

0x71 特点

0x72 构造函数

0x73 常用API

0x74 example

0x8 容器配接器0x8 容器配接器

0x81 stack

0x811 构造函数

0x812 常用API

0x82 queue

0x821 构造函数

0x822 常用API

0x83 priority_queue

0x831 构造函数

0x832 常用API

热门文章

最新文章

相关课程

相关电子书