C/C++(5) ——STL基础篇（一）
文章目录
- C/C++(5) ——STL基础篇（一）
- 1.请你讲讲STL有什么基本组成
- 2.说说STL中map/hashtable/unordered_map、deque、list的实现原理
- 2.1 map实现原理
- 2.2 hashtable/unordered_map（也称散列表，直译作哈希表）实现原理
- 2.3 deque实现原理
- 2.4 list实现原理
- 3.STL 容器用过哪些，查找的时间复杂度是多少，为什么？
- 3.1 vector
- 3.2 deque
- 3.3 list
- 3.4 map、set、multimap、multiset
- 3.5 unordered_map、unordered_set
- 4.说说 push_back 和 emplace_back 的区别
- 5.STL 中 vector 与 list 具体是怎么实现的？常见操作的时间复杂度是多少？
- 5.1 vector 一维数组
- 5.2 list 双向链表
- 5.3 常见时间复杂度
参考回答：
分配器给容器分配存储空间，算法通过迭代器获取容器中的内容，仿函数可以协助算法完成各种操作，配接器用来套接适配仿函数。
标准模板库STL主要由6大组成部分：
2.说说STL中map/hashtable/unordered_map、deque、list的实现原理分配器（Allocator）
为STL提供空间配置的系统。
其中主要工作包括两部分：①对象的创建与销毁；②内存的获取与释放。
容器(Container)
是一种数据结构， 如list, vector, 和deques，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器。
算法（Algorithm）
是用来操作容器中的数据的模板函数。例如，STL用sort()来对一 个vector中的数据进行排序，用find()来搜索一个list中的对象， 函数本身与他们操作的数据的结构和类型无关，因此他们可以用于从简单数组到高度复杂容器的任何数据结构上。
迭代器（Iterator）
提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。 迭代器就如同一个指针。事实上，C++ 的指针也是一种迭代器。 但是，迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符方法的类对象。
仿函数（Function object）
仿函数又称之为函数对象， 其实就是重载了操作符的struct,没有什么特别的地方。
配接器（Adaptor）
简单的说就是一种接口类，专门用来修改现有类的接口，提供一中新的接口；或调用现有的函数来实现所需要的功能。主要包括3中适配器Container Adaptor、Iterator Adaptor、Function Adaptor。
参考回答：
map、hashtable/unordered_map、deque、list实现机理分别为红黑树、函数映射、双向队列、双向链表，他们的特性分别如下：
map内部实现了一个红黑树（红黑树是非严格平衡的二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树有自动排序的功能，因此map内部所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉树（又名二叉查找树、二叉排序树）存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值。使用中序遍历可将键值按照从小到大遍历出来。
2.2 hashtable/unordered_map（也称散列表，直译作哈希表）实现原理hashtable采用了函数映射的思想记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。这决定了哈希表特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。
2.3 deque实现原理deque内部实现的是一个双向队列。元素在内存连续存放。随机存取任何元素都在常数时间完成（仅次于vector）。所有适用于vector的操作都适用于deque。在两端增删元素具有较佳的性能（大部分情况下是常数时间）。内部结构比较神奇，主体是一个数组，但每个元素都存放一个数组的指针，真实的数据存放在各个小数组内。
2.4 list实现原理list内部实现的是一个双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。无成员函数，给定一个下标i，访问第i个元素的内容，只能从头部挨个遍历到第i个元素。
3.STL 容器用过哪些，查找的时间复杂度是多少，为什么？参考回答：
STL中常用的容器有vector、deque、list、map、set、multimap、multiset、unordered_map、unordered_set等。容器底层实现方式及时间复杂度分别如下：
采用一维数组实现，元素在内存连续存放，不同操作的时间复杂度为：
3.2 deque插入: O(N)
查看: O(1)
删除: O(N)
采用双向队列实现，元素在内存连续存放，不同操作的时间复杂度为：
3.3 list插入: O(N)
查看: O(1)
删除: O(N)
采用双向链表实现，元素存放在堆中，不同操作的时间复杂度为：
3.4 map、set、multimap、multiset插入: O(1)
查看: O(N)
删除: O(1)
上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:
3.5 unordered_map、unordered_set插入: O(logN)
查看: O(logN)
删除: O(logN)
上述容器采用哈希表实现，不同操作的时间复杂度为：
插入: O(1)，最坏情况O(N)
查看: O(1)，最坏情况O(N)
删除: O(1)，最坏情况O(N)
【注意】：容器的时间复杂度取决于其底层实现方式。
| 容器 | 容器上的迭代器类别 |
|---|---|
| vector | 随机访问 |
| deque | 随机访问 |
| list | 双向 |
| set/multiset | 双向 |
| map/multimap | 双向 |
| stack | 不支持迭代器 |
| queue | 不支持迭代器 |
| priority_queue | 不支持迭代器 |
参考回答
如果要将一个临时变量push到容器的末尾，push_back()需要先构造临时对象，再将这个对象拷贝到容器的末尾，而emplace_back()则直接在容器的末尾构造对象，这样就省去了拷贝的过程。
class A
{
public:
A(int i) {
str = to_string(i);
cout << "构造函数" << endl;
}
~A() {}
A(const A& other) : str(other.str) {
cout << "拷贝构造" << endl;
}
public:
string str;
};
int main() {
vector vec;
vec.reserve(10);
for (int i = 0; i < 10; i++) {
vec.push_back(A(i)); //调用了10次构造函数和10次拷贝构造函数
// vec.emplace_back(i); //调用了10次构造函数和0次拷贝构造函数
}
}
5.STL 中 vector 与 list 具体是怎么实现的？常见操作的时间复杂度是多少？
参考回答
5.1 vector 一维数组5.2 list 双向链表特点：元素在内存连续存放，动态数组，在堆中分配内存，元素连续存放，有保留内存，如果减少大小后内存也不会释放。
优点：和数组类似开辟一段连续的空间，并且支持随机访问，所以它的查找效率高其时间复杂度O(1)。
缺点：由于开辟一段连续的空间，所以插入删除会需要对数据进行移动比较麻烦，时间复杂度O（n），另外当空间不足时还需要进行扩容。
5.3 常见时间复杂度特点：元素在堆中存放，每个元素都是存放在一块内存中，它的内存空间可以是不连续的，通过指针来进行数据的访问。
优点：底层实现是循环双链表，当对大量数据进行插入删除时，其时间复杂度O(1)。
缺点：底层没有连续的空间，只能通过指针来访问，所以查找数据需要遍历其时间复杂度O（n），没有提供[]操作符的重载。
①vector插入、查找、删除时间复杂度分别为：O(n)、O(1)、O(n)；
②list插入、查找、删除时间复杂度分别为：O(1)、O(n)、O(1)。
