cpp笔记与思考-STL容器库

C/C++笔记
c plus plus programing language note

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

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

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

我学习和补充自己cpp知识的主要地方为cppreference.comConcurrency-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