STL序列容器

发表于 |

本章主要介绍STL中序列容器相关内容

C++本身提供了一种序列容器array。STL中标准序列容器有四种：vector, string, list, deque。至于STL中的stack, queue,priority_queue等容器虽然也归于序列容器，但不属于标准序列容器，因为其本质是由基于deque实现的。

  • Array

概念

数组从概念上来理解就是若干顺序排列元素，且数组大小固定。Class array<>，由C++ TR1标准引入(因此需要支持C++11的编译器版本)。是对传统C语言风格的数组的一层封装。拥有更安全和较优的性能。

1
2
3
4
5
//type is defined as a class template inside namespace std
namespace std{
    template <typename T, size_t N>
    class array;
}

行为

  • 内部有序，支持随机访问
  • 提供随机访问迭代器，可以使用任何STL算法
  • 大小固定，内存分布在栈上，性能优

初始化

array在初始化方面有一些比较独特的表现。

  1. 默认构造函数并不创建一个空的容器，而是根据类模板中第二个参数N，返回一个固定大小的容器。
  2. 当不进行初始化时，对于基本类型的元素，其行为将是未定义的
    1
    2
    3
    4
    5
    //OOPS:elements of x have undefined value
    std::array<int, 4> x; 
    //OK:all elements of x have value 0
    std::array<int, 4> x = {};

swap和move语义

对于数组来说，可以将两个具有相同元素类型，相同元素个数的数组通过swap进行交换。由于内部并不是简单的交换指针，因此，swap具有线性时间复杂度。迭代器和引用在swap之后均会失效。

1
2
3
4
//implicitly provided for arrays
std::array<int , 10> a1, a2;
a1 = std::move(a2);
  • Vector

概念

vector可以看做是一个动态扩容的数组。

1
2
3
4
5
6
namespace std{
    template<typename T,
            typename Allocator = allocator<T>>
    
    class vector;
}

可选的第二个参数定义了内存分配模型，默认使用STL提供的allocator。

行为

vector将元素拷贝至内部的动态数组中，每个元素已确定顺序排列。提供了随机访问。
对于容器尾部的插入或删除，vector提供了良好的性能。如果在中间或者头部进行插入或删除，性能则急剧下降。这是因为需要将原有位置上的每个元素移动到新的位置，意味着需要进行频繁的赋值操作。

某种程度上来说，vector之所以性能表现不俗，是因为vector会申请比真实需要的更多的内存。

Size and Capacity

当元素插入个数超过当前vector.capacity()值时，vector会重新分配内存（一般是扩容一倍）。

重新分配会带来两种重要影响

  • 重新分配使得原有的引用，指针，迭代器都失效了
  • 重新分配耗时较久（需要将原有的元素拷贝至新的内存区域，释放原有的内存）

为了避免重新分配：

1.可以使用reserve()，在使用之前就分配足够的内存。这里有个前提就是使用者对vector大小事先知道。

2.传递参数给构造函数

1
2
3
4
//calls five times the default ctor of type T
//which means the type of the elements must provide
//a default constructor for this ability
std::vector<T> v(5);

需要注意的是，对于一些复杂类型的构造，往往是比较耗时的。因此如果仅仅是为了预留内存，使用者应该选择第一种方式，即reserve()。同时,调用reserve(),通过传入一个比当前capacity小的值，并不能达到收缩内存的目的。

C++11引入了一种方法，以达到收缩内存的目的。

1
v.shrink_to_fit();

C++11之前则只能通过交换操作来达到降低内存占用的目的。

1
2
3
4
5
6
template <typename T>
void shrinkCapacity(std::vector<T>& v)
{
    std::vector<T> tmp(v);
    v.swap(tmp);
}

以上两种方法，均会使引用，指针，和迭代器失效。原因是交换之后，引用，指针和迭代器均指向原来的入口处指向的元素。

测试用例

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
26
27
28
29
30
31
int main(){
    std::vector<int> v1, v2;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    
    v2.push_back(10);
    v2.push_back(20);
    v2.push_back(30);
    
    //references
    int& rv1 = v1[0];
    int& rv2 = v2[0];
    
    //pointers
    int* pv1,* pv2;
    pv1 = &v1[1];
    pv2 = &v2[2];
    
    //iterators
    std::vector<int>::iterator it = v1.begin();
    
    printf("before swap rv1 = %d, rv2 = %d, pv1 = %d, pv2 = %d, it = %d\n", rv1, rv2, *pv1, *pv2, *it);
    
    v1.swap(v2);
    printf("after swap rv1 = %d, rv2 = %d, pv1 = %d, pv2 = %d, it = %d\n", rv1, rv2, *pv1, *pv2, *it);
}
result:
before swap rv1 = 1, rv2 = 10, pv1 = 2, pv2 = 30 it = 1
after swap rv1 = 1, rv2 = 10, pv1 = 2, pv2 = 30 it = 1

Class vector

针对bool类型的容器，C++标准为了节省内存而进行了特殊优化。有别于常规的vector实现，vector内部使用1bit来存放一个元素。使得空间利用率提升8倍以上。在C++中，可以访问的最小地址空间为1个字节，因此上述特殊的vector在references和iterators上的处理也会特殊一些。

  • Deques

发音同”deck”.与vector非常相似。以动态扩容的数组形式管理内部元素，支持随机访问，支持的接口与vector相近。不同的是，deque内部的动态数组可以在头尾两个方向增长。 因此deque的头尾位置的插入和删除速度是很快的。
Deque的内部结构可以概括为由若干分段的数组组成，容器中的元素（数据）存放在这样的大小固定（512字节）的数组中，此外还有一个存放这些数组首地址的索引数组。

行为

  • 头尾位置的插入和删除操作性能较快(vector只有在尾部)，时间复杂度为O(1)
  • 由于内部数据的访问是间接的（先访问索引数组获取地址，然后根据索引获取数据），因此在deque中数据访问和迭代器移动相对会更耗时一些
  • 迭代器必须是智能指针而不是传统指针类型，因此它们必须在跨越两块内存来访问数据。
  • 不支持对容器的capacity和内存reallocation的时机的管理。reallocation表现优于vector,因为deque内部的结构导致其不需要进行全量拷贝操作。
  • 块内存会被释放当它们不在被使用时，所以deque所占用的内存大小会自动进行收缩（是否进行内存的释放以及何时进行，取决于deque的具体实现）
  • 中间位置的插入和删除耗时比较久，因为需要移动在操作位置之后的元素来腾出插入需要的空间或填补删除产生的空间。

什么时候使用deque而不是vector?

  1. 头尾都需要插入或删除元素
  2. 及时回收内存显得尤为重要（然而，标准并不保证这一定会发生）

shrink_to_fit

由于deque内存会被自动释放，这里指的是存放元素所占用的内存，但是对于存储这些数组首地址的索引数组，其占用的内存不会被释放，此时就可以借助shrink_to_fit。

  • List

内部以双向链表组织数据。C++标准并不会规定其具体实现。list内部结构与array,vector,deque存在较大不同。list提供了两个指针，被称为anchors,指向了list中头，尾元素。

行为

  • 随机访问性能较差，需要遍历之前的元素
  • 任意位置的插入和删除操作性能较优，时间复杂度为O(1)
  • 插入和删除元素并不会使得references, pointers, iterators失效
  • 关于list的绝大部分操作均有异常检测机制，因此可以捕获异常，从而不会使得程序中断

forward_list(Since C++11)

较list来说，内存占用更少且运行时表现略胜一筹。限制如下：

  • 仅提供单向迭代器，不提供reverse_iterator,同时rbegin(), rend(), crbegin(), crend()也不被支持
  • 不提供size()方法
  • anchor不包含指向最后一个元素的指针，因此不支持back(), push_back(), pop_back()
  • 提供了特殊的插入或删除操作的方法，通常增加了_after后缀，入insert_after()

对于第二点，不提供size()可能会令人惊讶，因为size()函数是标准要求的所有STL容器都需要支持的。但是出于时间和空间上的考虑，最终还是去掉了这个函数，由调用者来维护或者直接使用list.