SGI STL 标准库 vector和list 3

github源码分析仓库

容器的介绍

研究数据的特定排列方式,以便于搜寻或排序或其它特殊目的,这一专门学科称为数据结构。任何特定的数据结构都是为了实现某种特定的算法。STL容器将运用最广泛的的一些数据结构实现出来。常见数据结构:array(数组)、list(链表)、tree(树)、queue(队列)、hash table(散列表)、set(集合)、map(映射表)等。这些数据结构分为序列式和关联式两种。

序列式容器

  • array(build-in) C++内建
  • vector
    • heap 以算法形式呈现(xxx_heap) 内部用vector实现
      • priority-queue 内部用heap实现
  • list
  • slist 非标准
  • deque
    • stack 配接器 内部用deque实现
    • queue 配接器 内部用deque实现

关联式容器

  • RB-tree 非公开
    • set 内部用RB-tree实现
    • map 内部用RB-tree实现
    • multiset 内部用RB-tree实现
    • multimap 内部用RB-tree实现
  • hashtable 非标准
    • hash_set 非标准 内部用hashtable实现
    • hash_map 非标准 内部用hashtable实现
    • hash_multiset 非标准 内部用hashtable实现
    • hash_multimap 非标准 内部用hashtable实现

vector

vector是STL提供的一种序列式容器。vector是动态空间,在加入元素时,如果空间不足,内部机制会自行扩充空间容纳新元素。
vector在使用前需要包含<vector>,其内部实现位于<stl_vector.h>
vector使用一块连续线性空间存储元素,支持随机存储,提供Random Access Iterator。
vector缺省使用alloc作为空间配置器。
vector的容量永远大于等于其大小,如果容量等于大小,则满载,再新加元素,整个vector需要寻找一块更大的空间。
vector支持动态增加大小,但并不是在原有空间之后接续新空间,而是以原大小的两倍另外配置一块较大空间,然后将原空间内容拷贝过来,在原内容之后构建新元素,并释放原空间。因此,对vector的任何操作,如果引起空间重配置,指向vector的所有迭代器将失效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
vector<int> vec(4, 5); // 5, 5, 5, 5
vec.push_back(6); // 5, 5, 5, 5, 6
vec.push_back(6); // 5, 5, 5, 5, 6, 6
for(vecotor<int>::iterator it = vec.begin();
it!=vec.end();)
{
if(*it == 6)
{
vec.erase(it);
//++it; //错误 vector中删除一个元素,后面元素会整体前移一次,迭代器在删除当前元素后,实际已指向下一个元素了,如果再前移,则会少遍历一个元素。
}
else
{
++it;
}
}yiyiyyigels
return 0;
}

resize和reserve

resize改变vector大小,引起vector容量的变化,会调用默认拷贝构造函数,会导致vector的size会增加.
reserve改变vector容量,不改变size,只是配置空间,不调用拷贝构造函数.

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
32
33
34
35
36
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class A
{
public:
A() : m_i(0)
{
cout << "construct A" << endl;
}
A(const A& a)
{
cout << "copy construct A" << endl;
m_i = a.m_i;
}
private:
int m_i;
};

int main()
{
vector<A> va;
cout << string("va size:") << va.size() << " va capacity:" << va.capacity() << endl;
va.resize(10);
cout << string("va size:") << va.size() << " va capacity:" << va.capacity() << endl;

vector<A> vb;
cout << string("vb size:") << vb.size() << " vb capacity:" << vb.capacity() << endl;
vb.reserve(10);
cout << string("vb size:") << vb.size() << " vb capacity:" << vb.capacity() << endl;

return 0;
}

运行结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
va size:0 va capacity:0
construct A
copy construct A
copy construct A
copy construct A
copy construct A
copy construct A
copy construct A
copy construct A
copy construct A
copy construct A
copy construct A
va size:10 va capacity:10
vb size:0 vb capacity:0
vb size:0 vb capacity:10

list

list是STl提供的一种序列式容器,每次插入或删除一个元素,就会配置或释放一个元素空间。list对任何位置元素的插入和删除都是常数时间。
list是一种双向链表,迭代器具备前移和后移能力,提供Bidirectional Iterator(双向迭代器)。
list插入一个元素不会导致迭代器失效,而vector则可能引起空间重新配置,导致迭代器全部失效。
list元素删除只是指向被删除元素的迭代器失效,其它迭代器不受影响。
SGI STL是环状双向链表,只需要一个指针就可以完整表现整个链表。让该指针指向刻意安排在尾端的一个空白节点,便能符合STL“前闭后开”区间的要求。
list缺省使用alloc作为空间配置器。
由于list不是RandomAccessIterator,无法使用STL算法sort(),所以list自己实现了sort方法。使用了归并排序,时间复杂度为n*log(n)

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
//排序 归并排序
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::sort()
{
// Do nothing if the list has length 0 or 1.
// 如果是空链表或者只有一个元素,不需要排序。
if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
//新的lists,作为中介数据存储区
list<_Tp, _Alloc> __carry;
list<_Tp, _Alloc> __counter[64];
int __fill = 0;
while (!empty()) { //直到当前list为空
__carry.splice(__carry.begin(), *this, begin()); //先将begin()节点移动到__carry中,放在__carry.begin()之前
int __i = 0;
while(__i < __fill && !__counter[__i].empty()) { //如果___i小于__fill 而且 __counter[__i]不为空 合并下
__counter[__i].merge(__carry); //合并__carry到__counter[__i] __carry变为空
__carry.swap(__counter[__i++]); //交换__counter[__i] 和 __carry __carry不为空 __counter[__i]为空 i自加1
}
__carry.swap(__counter[__i]); //交换__counter[__i] 和 __carry __carry置为空,而__counter[__i]不为空
if (__i == __fill) ++__fill; //如果__i已经和__fill相等 就将__fill自加1
}

//数据已经全部排序,并放在了__counter数组中,遍历数组,合并它们
for (int __i = 1; __i < __fill; ++__i)
__counter[__i].merge(__counter[__i-1]);
//和排好序的新链表__counter[__fill-1]交换下
swap(__counter[__fill-1]);
}
}

如果需要排序21, 45, 1, 30, 52, 3, 58, 47, 22, 59, 0, 58。
具体过程如下:
取第1个数21,放入__carry中,没有需要合并的counter,交换``carrycounter[0]fill``自加1等于1

  • __counter[0]:21
  • __counter[1]:NULL

取第2个数45,放入__carry中,和__counter[0]合并,合并后交换__counter[0]__carry__i自加1等于1,没有可合并的啦,交换__counter[1]__carry

  • __counter[0]:NULL
  • __counter[1]:21, 45

取第3个数1,放入__carry中,没有需要合并的counter,交换``carry__counter[0]``

  • __counter[0]:1
  • __counter[1]:21, 45

取第4个数30,放入__carry中,和__counter[0]合并,合并后交换__counter[0]__carry__i自加1等于1,发现还可以和__counter[1]合并,合并,__i自加1等于2了,交换__counter[2]__carry__fill自加1等于2

  • __counter[0]:NULL
  • __counter[1]:NULL
  • __counter[2]:1, 21, 30, 45

通过上面其实可以发现,__counter存放的节点数目按指数增长__counter[0]存放2个节点,__counter[1]存放4个节点,__counter[2]存放8个节点,… ,__counter[64]存放2^(64)个节点。当节点数目超过其存储的最大数时,便会和更高层的合并。再看下面的的排序情况:

取第5个数52,放入__counter[0]

  • __counter[0]:52
  • __counter[1]:NULL
  • __counter[2]:1, 21, 30, 45

取第6个数3,放入__counter[0], __counter[0]满了,转移到__counter[1]

  • __counter[0]:NULL
  • __counter[1]:3, 52
  • __counter[2]:1, 21, 30, 45

取第7个数58,放入__counter[0]

  • __counter[0]:58
  • __counter[1]:3, 52
  • __counter[2]:1, 21, 30, 45

取第8个数47,放入__counter[0], __counter[0]满了,和__counter[1]合并,发现__counter[1]满了,然后再和__counter[2]合并,发现__counter[2]满了,最后转移到__counter[3]

  • __counter[0]:NULL
  • __counter[1]:NULL
  • __counter[2]:NULL
  • __counter[3]:1, 3, 21, 30, 45, 47, 52, 58

取第9个数22,放入__counter[0]

  • __counter[0]:22
  • __counter[1]:NULL
  • __counter[2]:NULL
  • __counter[3]:1, 3, 21, 30, 45, 47, 52, 58

取第10个数59,放入__counter[0], 转移到__counter[1]

  • __counter[0]:NULL
  • __counter[1]:22, 59
  • __counter[2]:NULL
  • __counter[3]:1, 3, 21, 30, 45, 47, 52, 58

取第11个数0,放入__counter[0]

  • __counter[0]:0
  • __counter[1]:22, 59
  • __counter[2]:NULL
  • __counter[3]:1, 3, 21, 30, 45, 47, 52, 58

取第12个数58,放入__counter[0],__counter[0]满了,和__counter[1]合并,__counter[1]满了,转移到__counter[2]

  • __counter[0]:NULL
  • __counter[1]:NULL
  • __counter[2]:0, 22, 58, 59
  • __counter[3]:1, 3, 21, 30, 45, 47, 52, 58

现在所有的节点都加入了__counter,遍历__counter,合并它们,最后__counter[__fill-1]就是排序后的目标链表

参考资料

  1. STL源码剖析(侯捷)
  2. http://blog.csdn.net/qq276592716/article/details/7932483
  3. http://blog.csdn.net/lijun5635/article/details/23963707