Code×Life
0%

C++ STL

发表于 更新于 分类于
介绍STL各种容器，还有迭代器的用法

综述

  1. 全称：Standard Template Library,标准模板库

  2. image-20230409145131333

    迭代器是沟通算法和容器的桥梁，容器相当于数据结构，算法根据容器提供的迭代器进行操作 -> 数据结构有了配套的操作

容器

image-20230409145354236

容器更像一个类

Vector

  1. 特点：

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

  2. 操作：

    1.push_back 在数组的最后添加一个数据

    2.pop_back 去掉数组的最后一个数据

    3.at 得到编号位置的数据

    4.begin 得到数组头的指针

    5.end 得到数组的最后一个单元+1的指针

    6.front 得到数组头的引用

    7.back 得到数组的最后一个单元的引用

    8.max_size 得到vector最大可以是多大

    9.capacity 当前vector分配的大小

    10.size 当前使用数据的大小

    11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值

    12.reserve 改变当前vecotr所分配空间的大小

    13.erase 删除指针指向的数据项

    14.clear 清空当前的vector

    15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)

    16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)

    17.empty 判断vector是否为空

    18.swap 与另一个vector交换数据

  3. 特性：

    1. 在动态扩容上，vector动态增加大小时，并不是在原空间之后持续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此， 对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。

deque

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

  2. 特点

    • 一旦要在 deque 的头部和尾部增加新空间，便配置一段定量连续空间，串在整个 deque 的头部或尾部，因此不论在头部或尾部插入元素都十分迅速。 (优点）

    • 在中间部分安插元素则比较费时，因为必须移动其它元素。（缺点）

    • deque 是 list 和 vector 的折中方案。兼有 list 的优点，也有 vector 随机访问效率高的优点。

    • 总结：支持随机访问，但效率没有 vector 高，在头部和尾部插入或删除效率高，但在中间插入或删除效率低。

set

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

list

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

特点

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

map

map 由红黑树实现，其元素都是 “键值/实值”所形成的一个对组（key/value pairs)。

map 主要用于资料一对一映射的情况，map 内部自建一颗红黑树，这颗树具有对数据自动排序的功能，所以在 map 内部所有的数据都是有序的。比如一个班级中，每个学生的学号跟他的姓名就存在着一对一映射的关系。

特点

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

适用场景

适用于需要存储一个数据字典，并要求方便地根据key找value的场景。

iterator

  1. 迭代器类似指针，指向容器中的某个元素，用->(如果容器中的元素是pair，可以用it->first与it->second访问第一个和第二个值)或者*(元素为一个值)访问指向的元素

  2. 容器适配器 stack、queue 和 priority_queue 没有迭代器。容器适配器有一些成员函数，可以用来对元素进行访问。

  3. 分类：

    1. 正向：容器类名<>::iterator 迭代器名;
    2. 反向：容器类名<>::reverse_iterator 迭代器名;
    3. 常量正向：容器类名<>::const_iterator 迭代器名;
    4. 常量反向：容器类名<>::const_reverse_iterator 迭代器名;

  4. 迭代器都可以进行++操作。反向迭代器和正向迭代器的区别在于：

    • 对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素；

    • 而对反向迭代器进行++操作时，迭代器会指向容器中的前一个元素。

      使用正向/反向迭代器写for循环迭代时，要写it != container.end()/rend()而不是<=，因为反向迭代器的++是反向的，都这么写美观整齐