STL概念及其部分容器知识

STL基本概念#

STL(Standard Template Library,标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要出现在 c++ 中，但是在引入 c++ 之前该技术已经存在很长时间了。 STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator),容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。STL(Standard Template Library)标准模板库,在我们 c++ 标准程序库中隶属于 STL 的占到了 80%以上。

1. STL是什么#

了解 中文与英文的全称广义上分为哪三个这三个之间的关系主要采用了什么，相比传统的由（）库有什么优势 1 1 1 1 1 标准模板库（Standard Template Library）广义上分为：容器(container)、算法(algorithm)、迭代器(iterator) 容器和算法之间通过迭代器进行无缝衔接 STL 几乎所有的代码都采用了==模板类或者模板函数==，这相比传统的由函数和类组成的库来说提供了更好的==代码复用机会==

2. STL有哪六大组件#

了解 1 1 1 1 1 容器、算法、迭代器、仿函数、适配器、空间配置器

3. STL的容器是什么#

是各种（），如（），用来（）从现实角度看，STL容器是一种（） 1 1 1 1 1 是各种数据结构，如vector,list,deque,set,map等，用来存放数据从现实角度看，STL容器是一种class template

4. STL的算法是什么#

就是各种（），如（）从现实角度看，STL算法是一种（） 1 1 1 1 1 就像它的名字一样，就是各种常用的算法，如sort,find,copy,for_each 从现实角度看，STL算法是一种function template

5. STL的迭代器是什么#

扮演了（）之间的胶合剂从现实来看，迭代器是一种将（）等指针相关操作重载的（）所有的STL（）都有自己专属的迭代器 1 1 1 1 1 扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将operator* , operator-> ,operator++,operator—等指针相关操作予以重载的class template 所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素

原生指针(native pointer)也是一种迭代器。

容器特点#

可以用下标访问的容器有（既可以插入也可以赋值）：vector、deque、map；

特别要注意一下，vector和deque如果没有预先指定大小，是不能用下标法插入元素的！

序列式容器才可以在容器初始化的时候指定大小，关联式容器不行；

注意，关联容器的迭代器不支持it+n操作，仅支持it++操作

序列式容器#

vector相关知识点#

6. 使用场景#

1 1 1 1 1 数组

7. 特点#

本质是（）的（），空间不足时如何分配空间删除元素时，（），所以（）对删除或插入操作的执行效率（），越靠后插入或删除执行效率（）（）的容器底层内存空间（）扩容机制 1 1 1 1 1 (1) 本质是一个动态分配的数组(当数组空间内存不足时，都会执行: 分配新空间-复制元素-释放原空间);

(2) 当删除元素时，不会释放限制的空间，所以vector容器的容量(capacity)大于vector容器的大小(size);

(3) 对于删除或插入操作，执行效率不高，越靠后插入或删除执行效率越高;

(4) 高效的随机访问的容器。

(5) 底层内存空间连续

(6) 扩容机制：当旧的存储空间不够时，扩充一个新的空间，空间大小为原来大小的两倍，复制元素到新的空间，并释放旧空间。

8. 底层数据结构#

是（），所以支持（），插入尾部空间复杂度（） 1 1 1 1 1 是数组，所以支持O（1）快速随机访问，插入尾部为O（n）

9. 创建vector对象#

2种 1 1 1 1 1 vector v1;// 空数组 vector v1(10);// 数组中有10个0

10. 基本操作#

大小尾插尾删获取头部元素获取尾部元素头部元素迭代器尾部元素迭代器插入 1 1 1 1 1 大小v.size(); 尾插v.push_back(); 尾删v.pop_back(); 获取头部元素v.front(); 获取尾部元素v.back(); 头部元素迭代器v.begin(); 尾部元素迭代器v.end(); 插入v.insert(pos, elem);// pos位置，elem元素

deque相关知识点#

11. deque特点#

中英文全称有（）和（），分别是有什么功能向（）插入元素效率较高，为什么向（）插入元素效率较低 1 1 1 1 1 (1) deque(double-ended queue 双端队列);

(2) 具有分段数组、索引数组, 分段数组是存储数据的，索引数组是存储每段数组的首地址;

(3) 向两端插入元素效率较高！

若向两端插入元素，如果两端的分段数组未满，既可插入;如果两端的分段数组已满，

则创建新的分段函数，并把分段数组的首地址存储到deque容器中即可)。

中间插入元素效率较低

12. deque的底层数据结构#

底层内存空间（），通常是（）通过（）数组中的（）来管理不同的（） 1 1 1 1 1 底层内存空间不一定连续，通常是一段一段的连续空间，通过map（非STL中的map）数组中的指针来管理不同的连续空间。

13. deque如何实现“整体连续”#

通过建立（），deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果

当 deque 容器需要在头部或尾部增加存储空间时，它会（），同时在（）的开头或结尾添加（），由此该空间就串接到了 deque 容器的头部或尾部 1 1 1 1 1 通过建立 map 数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果

当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。

14. 创建deque对象#

两种 1 1 1 1 1 deque d1; deque d2(10);

list相关知识点#

15. list特点#

是（），（）效率高，（）效率低 1 1 1 1 1 是双向链表，可以高效地进行首尾插入删除元素。中间==删除==元素效率低

16. list的底层数据结构#

是（），每个节点都有（） 1 1 1 1 1 是一个双向链表（每个节点有指向前驱和指向后继的两个指针）

关联式容器#

map容器相关知识点#

17. map的使用场景#

3种 1 1 1 1 1 去重类问题可以打乱重新排列的问题有清晰的一对一关系的问题

18. map的特点#

（）是单重映射，（）是多重映射 map与multimap的区别 map和multimap内部自建了（），可以对数据（），（）效率高，所以map、multimap里的数据都是（），这也是我们通过map简化代码的原因。自动建立（）的对应关系 key和value一一对应的关系可以（） 1 1 1 1 1 (1) map为单重映射、multimap为多重映射;

(2) 主要区别是map存储的是无重复键值的元素对，而multimap允许相同的键值重复出现，既一个键值可以对应多个值。

(3) map和multimap内部自建了一颗红黑二叉树，可以对数据进行自动排序，插入、删除效率高，所以map、multimap里的数据都是有序的，这也是我们通过map简化代码的原因。

(4)自动建立key-value的对应关系，key和value可以是你需要的任何类型。

(5) key和value一一对应的关系可以去重

19. map的底层数据结构#

由（）实现，（）高，因为（） 1 1 1 1 1 都由红黑树实现，但空间占用率高，因为每个节点要保存父、子节点和红黑性质。

20. map创建对象#

（）类似两种 1 1 1 1 1 map与multimap类似

map<T1,T2> m;

map<T1,T2, op> m; //op为排序规则，默认规则是less**（升序排列）**只会按键==去排序！，可以用结构体重载（）对键自定义排序

代码示例

1
#include <map>
2
#include <string>
3
#include <iostream>
4
using namespace std;
5
int main(){
6
    //关键是这句话 按字符串长度排序 也只能对键进行排序
7
    map<string, int, greater<string> > mapStudent;
8
    mapStudent["LiMin"]=90;
9
    mapStudent["ZiLinMi"]=72;
10
    mapStudent["BoB"]=79;
11
    map<string, int>::iterator iter=mapStudent.begin();
12
    for(iter=mapStudent.begin();iter!=mapStudent.end();iter++)
13
    {
14
        cout<<iter->first<<" "<<iter->second<<endl;
15
    }
16
    return 0;
17
}

21. map插入数据#

插入数据 使用pair<>构造键值对对象

1
map<int, float> m;
2
m.insert(pair<int, float>(10,2.3));

使用make_pair()函数构建键值对对象

1
map<int,float> m;
2
m.insert(make_pair(10,2.3));

使用value_type标志

1
map<int, float> m;
2
m.insert(map<int,float>::value_type(10,2.3));
3
m[key] = value;   //m只能是map容器，不适用于multimap

unordered_map/unordered_multimap#

22. 特点#

与map、multimap区别（） 1 1 1 1 1 与map、multimap的区别之处：无序性，查找相对快，插入删除相对慢

23. 底层数据结构#

都是（），故查找效率（），适用于（） 1 1 1 1 1 都是哈希表，故查找效率相对高为O(n)，适用于查找多的场合。