cpp笔记与思考-STL容器库

cpp笔记与思考-STL容器库

February 9, 2021
C/C++, 笔记

追根溯源，剖析STL是个享受的过程。

本文主要写std中容器库，打了很久ACM，之前一直没有写写常用的cpp的笔记，现在就来补一下。

用cpp编写算法时，使用stl和不使用stl完全是两种体验，stl中有许多可以提高效率的工具函数和类函数。

我学习和补充自己cpp知识的主要地方为 cppreference.com和 Concurrency-with-Modern-Cpp，分别对应cpp基础和cpp多线程编程，当然cpp博大精深，需要学习的地方还有许多。

STL #

STL的实现有很多的版本，GNU C++标准中使用的是SGI STL，MacOS中的Clion使用的是LLVM，其他的版本还有Clang等，各自的性能和特点都有所不同。

本文分析源码中使用的是SGI STL。

容器库 #

顺序容器 #

顺序容器(sequence container) 可以实现数据的顺序访问，类似访问数组的形式。

vector #

在内存中，vector实例化的对象一般是在连续的内存空间上动态进行分配的（这点和内置的静态空间的array很不同），所以可以通过如a[i]的方式进行访问。

vector的常见操作的复杂度：

  • 随机访问 $O(1)$
  • 末尾插入或者移除 $O(1)$
  • 插入或者移除元素，与vector结尾成线性 $O(n)$

vector 空间管理 #

vector是属于按需要动态增加空间的容器，在实例化的时候会预分配存储空间，也可以手动进行存储空间的预分配，如果空间不够了就会在堆中新开辟当前空间的两倍的空间，并将当前空间中的值拷贝到新空间，因此如果对vector的操作引起了空间重新配置，那么就会导致指向原来vector的迭代器失效，同时需要一定的运算时间来进行数据迁移。

动态增加步骤：

  • 配置一块原空间2倍大小的新空间
  • 将原空间内容拷贝到新空间
  • 释放原空间
// 简化版vector类定义
template <class T, class Alloc = alloc>
class vector
{
public:
    typedef T value_type;
    typedef value_type* iterator; // vector 的迭代器是普通指针
protected:
    iterator start;  // 表示目前使用空间的头
    iterator finish; // 表示目前使用空间的尾
    iterator end_of_storage; // 表示目前可用空间的尾
};

通过上述简化版的vector定义，可以看到vecotr对象的内存空间通过三个迭代器（行为类似指针，重载了部分运算符）进行区分，分成了2个空间，分别是已用空间和未使用空间。b表示起来如下：

|-- -- -- used-- -- --|-- -- unused -- --|
^start                ^finish            ^end_of_storage

deque #

deque为双端队列，同时具有栈和队列的属性，是一种双向开口的连续线性空间，头和尾均可以进行元素的插入和删除操作。

list #

list是一个双向链表。

array #

cpp基础类，静态分配存储空间的连续数组。

其他 #

还有用的不多的，就简单列下，详情看 文档。

  • forward_list

关联容器 #

关联容器(associative container)是可以实现快速查找($O(log_n n)$)的数据结构

set #

set 唯一键的集合，按照键排序。

map #

map 键值对的集合，按照键排序，键是唯一的。

其他 #

还有许多其他的容器，日后有机会再补充，这里先列着。

  • stack - 典型的栈（LIFO）
  • queue - 典型的队列（FIFO）
  • priority_queue 优先队列,可以自定义优先定义方式

Reference #