C++学习笔记1----STL容器知识简要小结

背景：打发时间，简要梳理一下容器的基本概念与特性。接口具体举例使用建议查看官方文档说明

一、string 容器

1、string基本概念
1）c，string其为char数组；c++中，string为一个类，不仅包含char数组结构，而且包含操作的方法
2）底层实现是字符数组，内存增长方式为指数级

2、c++的string的[]和at区别

1)[]不会抛出异常，而at会抛出异常

3、string容器的API

1)构造()
2)赋值=、assign
3)存取at 、[]
4)拼接+=
5)查找（find、rfind）替换(replace)
6)比较（compare）
7)子串（substr）
8)插入（insert）与删除(erase)
9)char与string转换关系：
char转string是默认支持的；string转char*需要使用c_str()函数

二、vector容器

1、vector容器特性

1）相比数组而言，其存储空间为动态的（动态内存空间增加，一般为原来的容量的2倍开辟）
2）单端动态数组，只能在一端操作。其头部进行插入或删除效率很差
3）线性连续空间
4）capacity()表示容量，size()表示大小
5）reserve(x),开辟容量为x
6）容器拷贝构造时，只会把拷贝对象的size拷贝过来，而不是capacity拷贝过来
7）底层实现是动态分配的数组，内存增长为指数（下一次为当前的两倍）

2、vector的自身操作方法

1)front() 指向容器第一个元素
2)back()指向最后一个元素
3)begin()指向容器开始的迭代器
4)end()指向容器最后的迭代器
5)rbegin()指向倒数第一个元素的迭代器
6)insert()插入
7)push_back()单端操作，从末端插入
8)pop_back()单端操作，从末端剔除

3、vector常用的API

1）构造()
2）赋值=、assign、swap(互换赋值)
3）大小操作:
size()大小
empty()判断是否为空
resize()指定容器大小，超过原有的则默认补0, 不会修改容量
capacity()打印容器容量
reserve()指定容器的容量，需要初始化后才能访问

4）存取操作
at(),越界会抛出异常
[],越界会直接报错
front(),返回容器第一个元素
back(),返回容器最后一个元素

5）插入与删除
insert()插入(迭代器插入)
push_bach() 尾部插入
pop_back() 尾部删除
erase() 删除
clear() 删除容器所有元素

6）swap()收缩空间

7)reserve() 预留空间

4、vector容器的技巧使用

1）vector::iterator it = v.begin() ,*it不是一个指针，而是表示该迭代器里面的内容
2）sort(v.begin(), v.end()) , 默认升序排序。可自定义排序规则

三、deque容器

1、deque基本概念

1）双向开口容器，头、尾操作都方便
2）deque没有容量概念，动态的分段空间组合链接而成。其比vector优点在于头部操作方便，其他操作性能较差。因此，能用vector，就不用deque。
3）动态的分段空间，缓冲区（分段空间）+中控器（维护分段空间）。将空间上不连续，维护成逻辑上连续
4）底层实现原理为动态数组，内存增长基于块的动态分配和链接

2、deque常用的API

1）构造()
2）赋值=、assign、swap
3）大小操作
size() 元素个数
empty() 判断容器为空
resize() 重新指定元素的个数
4）插入与删除
push_back() 尾插
push_front() 头插
pop_back() 尾删
pop_front() 头删

5）存取:at()、[]、front()、back()

6）插入insert()
7）删除
clear(), 清除容器所有元素
erase(), 清除指定位置元素

3、deque高级技巧
sort(),排序

四、stack容器

1、stack容器基本概念

1）先进后出结构
2）没有迭代器，因此不可遍历

2、stack常用的API

1）构造()
2）赋值=
3)读取操作
push(),给栈顶添加元素
pop(),将栈顶元素删除
top(),读取栈顶元素
4)大小操作
empty(),判断容器是否为空
size(),容器大小

五、queue容器

1、queue容器基本概念

1）先进先出结构
2）底层实现为其他容器，如deque和list,内存增长方式取决于其底层容器

2、queue常用的API

1）构造()
2）赋值=
3）push(), 往队尾添加元素
4）pop(),删除队头元素
5）back(),队尾元素
6）front(),队头元素
7）empty(),判断队列是否为空
8）size(),返回队列大小

六、list容器

1、list容器基本概念

1）非连续、非顺序的存储结构；元素的逻辑顺序，通过指针链接实现。其本质为一个双向链表
2）相比数组而言，插入或者删除节点，不需要移动大量数据
3）内存为动态分配，不会内存浪费和溢出；但是，空间（指针域）消耗会大一些
4）底层实现为双向链表，内存增长方式为基于节点的动态分配且为线性的

2、list常用的API

1）构造()
2）元素插入与删除
push_back(), 尾部插入元素
pop_back(), 尾部删除元素
push_front(), 头部插入元素
pop_front(), 头部删除元素
insert(), 插入元素（三种形式，其中一个迭代器）
clear(), 清空容器
erase(), 移除指定位置的元素（可迭代器形式）
remove(), 剔除容器中指定的元素
3）大小操作
size(), 大小操作
empty(), 判断容器是否为空
resize(), 重新指定容器大小（可操作添加与删除）
4）赋值操作
assign(),区间拷贝赋值、多个元素拷贝赋值
重载=, 直接赋值
swap(), 交换赋值

5）数据存取
front(), 第一个元素
back(), 最后一个元素

6）反转与排序
reverse(), 反转链表
sort(), 排序（注意，这里不是STL提供的sort, 因为STL要求容器是随机迭代器，list迭代器为双向迭代器；但是，list 容器本身提供了sort方法，调佣如 l.sort()）

3、list容器一些属性

1）迭代器是双向迭代器，不支持+2(对比一下，vector迭代器支持，因为其为随机迭代器)，但是支持++（pb = pb->next）

七、set、multiset容器

1、set、multiset容器基本概念

1)set容器，所有元素会根据key自动排序，set容器只有key
2)set容器，不允许两个元素有相同的key
3)multiset容器, 特性与用法基本和set容器一致，不同点在于，其允许key重复
4)其底层实现使用平衡二叉树
5)set容器迭代器为只读迭代器（const_iterator），不允许修改key值（若修改，会破坏其内存布局，因为其底层实现是平衡二叉树）
6)set容器可以指定排序规则，如set s,；rules为一个规则，其为仿函数，目的满足类型与方法需要。
7)set容器存放自定义数据类型，必须给自定义排序规则，否则无法通过编译
eg:

class Person{
friend class MyGreaterPerson;
private:
int num;
string name;
float score;
Person(){}
Person(int num, string name, float score)
{
this->num = num;
this->name = name;
this->score = score;
}
};

class MyGreaterPerson
{
public:
bool operater(Person ob1, Person ob2)
{
return ob1.num < ob2.num;
}
};

set<Person, MyGreaterPerson> s;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

8）底层实现原理为红黑树，内存增长方式为动态分配节点分配且为线性

2、set容器常用的API

1）构造()
2）赋值=、swap()
3）大小操作
size(), 容器大小
empty(), 判断容器
4）插入与删除
insert(), 插入元素
clear(), 清空所有元素
erase(), 清除指定位置元素, 或剔除容器中具体某一种值元素，或剔除迭代器区间元素
5）查找
find(key), 查找元素key，返回迭代器;找不到则返回.end()迭代器
count(), 查找元素key的个数
lower_bound(key_elem), 查找第一个key >= key_elem元素迭代器
upper_bound(key_elem), 查找第一个key > key_elem元素迭代器
equal_bound(key_elem), 查找key与key_elem相等的上下限的两个迭代器
equal_bound(),返回上下限迭代器，其使用pair方式返回。

eg:
pair<set<int>const_iterator, set<int>::const_iterator> pa;
pa = s.equal_range(50);
1
2
3

八、pair队组

1、pair队组基本概念

1）将一对值组合成一个值
2）公有属性，first、second
3）模版template struct pair

2、常用的API

1）构造()
2）赋值，make_pair(a, b)

九、map、multimap容器

1、map、multimap基本概念

1）容器内元素均为pair（具有公共属性，first、second）
2）容器内元素会根据key值自动排序
3）map不允许有相同的key值，而multimap可以
4）容器底层实现为红黑树
5）不能通过迭代器修改key值，但可以通过迭代器修改value值
6）容器的迭代器为只读迭代器
7）底层实现原理是红黑树，内存增长方式为基于节点的动态分配

2、map、multimap常用API

1）构造()
2）赋值操作=、swap()
3）大小操作
size(),容器内元素多少
empty(), 判断容器是否为空
4）插入操作
insert(),
pair(a, b)方式、
make_pair(a, b)方式、
map::value_type(a, b)方式

 m[x] = xx, 数组形式插入
1

5）map删除操作
clear(), 删除容器所有元素
erase(), 剔除指定位置的元素或者元素

6）map查找操作
find(), 查找元素，找到则返回迭代器，否则返回.end()
count(key_elem), 查找key为key_elem的元素个数，map容器只会返回0或1，multimap返回会大于1
lower_bound(key_elem), 查找第一个key >= key_elem元素迭代器
upper_bound(key_elem), 查找第一个key > key_elem元素迭代器
equal_bound(key_elem), 查找key与key_elem相等的上下限的两个迭代器

3、打印输出访问
注意不使用[],否则，一旦key写错，容器会自动新建元素（写错的key）

十、总结

1、std::string：

优点：std::string 是用于处理字符串的容器，提供了许多字符串操作函数，包括连接、查找、截取等。
适用场景：处理文本和字符串数据时非常有用，例如文件读写、文本搜索、字符串拼接等。

2、std::vector：

优点：std::vector 是动态数组，支持快速随机访问，提供高效的插入和删除操作，通常在元素数量可变但需要随机访问的情况下使用。
适用场景：用于需要高性能的元素存储和随机访问的情况，例如数组替代、列表、堆栈等。

3、std::deque：

优点：std::deque 是双端队列，支持高效的双端插入和删除操作，适用于需要在队列的两端进行操作的情况。
适用场景：用于需要在队列的前端和后端执行插入和删除操作的情况，例如双端队列、循环队列等。

4、std::stack：

优点：std::stack 是栈容器，提供了后进先出（LIFO）的元素访问方式，用于管理函数调用、回溯等场景。
适用场景：用于需要维护栈数据结构的情况，例如函数调用栈、表达式求值等。

5、std::queue：

优点：std::queue 是队列容器，提供了先进先出（FIFO）的元素访问方式，用于管理任务队列等。
适用场景：用于需要维护队列数据结构的情况，例如任务调度、广度优先搜索等。

6、std::list：

优点：std::list 是双向链表，支持高效的插入和删除操作，但随机访问性能较差，适用于频繁的插入和删除操作。
适用场景：用于需要频繁插入和删除元素的情况，例如链表、优先级队列等。

7、std::set：

优点：std::set 是有序关联容器，基于红黑树实现，提供高效的查找操作，确保元素唯一性，并按键的顺序存储。
适用场景：用于需要有序集合和高效查找的情况，例如字典、索引、去重等。

8、std::map：

优点：std::map 是有序关联容器，基于红黑树实现，提供键-值对映射，按键的顺序存储，支持高效的查找和插入操作。
适用场景：用于需要有序键值对映射和高效查找的情况，例如字典、索引、关联数组等。

选择容器应根据具体需求和性能要求进行。不同容器在不同情况下具有不同的优势。通常，可以根据以下一些关键因素来选择合适的容器：

访问模式：需要随机访问、顺序访问还是双端访问？
插入/删除频率：需要频繁插入和删除吗？
是否需要有序性质：需要元素按顺序存储吗？
是否需要唯一性：元素是否需要保持唯一性？
性能要求：需要快速查找、高效插入/删除吗？

根据这些因素，可以选择最适合代码需求的容器类型

#########################
不积硅步，无以至千里
好记性不如烂笔头

觉得不错的话，记得点赞收藏哈~