浅谈STL

由于我刚开始学习系统的写博客,个人方面不管是能力还是经验都会有所欠缺,所以肯定会有很多不完善的地方,包括结构安排、要点遗漏、知识错误等等,还请各位批判着看,如有问题,恳请斧正,我将十分感激!

STL是一个标准规范,它只是为各种组件定义了一系列统一的访问接口及他们之间搭配使用的一般规则,而没有规定他们的底层实现。因此各开发商都提供自己的STL版本,比较著名的有P.J. Plauger,HP,SGI等。如无明确说明,本文所指的STL均为C++98标准下的SGI版本,下载地址

STL(Stardand Template Library),即标准模板库的简称。于1994年2月正式成为ANSI/ISO C++的一部分。

C++标准规定,STL的头文件都不用扩展名,所以一般STL的头文件名称是没有.h后缀的。同时,所有的STL组件都被纳入到std命名空间内,所以在include之后要声明STD命名空间:

<pre class="prettyprint linenums prettyprinted">

  1. `<span class="kwd">using</span><span class="pln"> </span><span class="kwd">namespace</span><span class="pln"> std</span><span class="pun">;</span>
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    STL是一套十分强大的库,基本将我们日常能使用的数据结构和算法封装为模板的形式,这样的好处是该套库有很强的通用性,可以说对任何类型都支持。
    而且使用STL的很方便,避免了在编码过程中重复造轮子的工作,使我们将精力集中在业务的实现逻辑上,而不必纠缠一些细枝末节的东西。比如要对一个整形数组iarr进行排序,只需要下面这句代码即可:
    <pre class="prettyprint linenums prettyprinted">
    1. `<span class="com">#include</span><span class="str">&lt;algorithm&gt;</span>`
    2. `<span class="kwd">using</span><span class="pln"> </span><span class="kwd">namespace</span><span class="pln"> std</span><span class="pun">;</span>`
    3. `<span class="pln">sort</span><span class="pun">(</span><span class="pln">iarr</span><span class="pun">,</span><span class="pln">iarr</span><span class="pun">+</span><span class="kwd">sizeof</span><span class="pun">(</span><span class="pln">iarr</span><span class="pun">)/</span><span class="kwd">sizeof</span><span class="pun">(</span><span class="pln">iarr</span><span class="pun">[</span><span class="lit">0</span><span class="pun">]));</span>

这样,我们便可以不用自己编写复杂的排序函数,大大地提高了开发效率。sort函数的原型到后面说算法的部分再说。

STL主要由六大组件组成,他们之间的关系如下:

可见,迭代器、存储分配器和函数对象都是为容器服务的。迭代器就像一个指针一样指向容器中某个元素,可以很方便地对其进行存取;存储分配器为容器分配内存空间;

容器

容器类定义在下表所示的头文件中:

<table> <thead> <tr> <th align="center">头文件</th> <th align="center">内容(元素类型均为T)</th> </tr> </thead> <tbody><tr> <td align="center">list</td> <td align="center">双向链表</td> </tr> <tr> <td align="center">vector</td> <td align="center">数组</td> </tr> <tr> <td align="center">queue</td> <td align="center">队列</td> </tr> <tr> <td align="center">deque</td> <td align="center">双向队列</td> </tr> <tr> <td align="center">stack</td> <td align="center">栈</td> </tr> <tr> <td align="center">set/multiset</td> <td align="center">集合</td> </tr> <tr> <td align="center">map/multimap</td> <td align="center">映射</td> </tr> <tr> <td align="center">bitset</td> <td align="center">位图</td> </tr> <tr> <td align="center">hash_map</td> <td align="center">hash映射</td> </tr> <tr> <td align="center">hash_set</td> <td align="center">hash集合</td> </tr> </tbody></table>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
```
容器按照其存储元素之间的关系又可以分为序列式容器和关联式容器。以上列表中set/multiset,map/multimap属于关联式容器,其他都属于序列式容器。
序列式容器和关联式容器的区别就是,序列式容器里面的元素之间都是有相对的位置关系的,不管是在逻辑上还是在底层实现上他们都有自己的相对位置。因而在序列式容器里面可以使用诸如push_back(),push_front(),pop_back(),pop_front()等函数;而关联式容器里面的元素在逻辑上总是无序的,如集合(无序性是数学概念上集合的特性之一)。但为了能在相应的数据结构中存储和附加在容器对象上算法的效率,关联式容器在物理实现上,其元素也是有相对的位置关系的,只不过对STL的使用者而言,这一切都是透明的,不会被其察觉。
要注意的是,STL里的容器都是可以动态增长的。所以为了支持这种特性,容器对象本身是创建在系统栈上,但容器所管理的空间创建在堆上。不过,一般来说,容器类自己会很好地管理这些空间,不会导致诸如内存泄露等问题。
下面说说最常用的几种容器:
##### list
list的内部被实现为一个双向循环链表,所以在其中进行insert,find等函数的时间复杂度是O(n),但erase函数为O(1)。其节点定义如下:
<pre class="prettyprint linenums prettyprinted">
1. `<span class="kwd">struct</span><span class="pln"> </span><span class="typ">_List_node_base</span><span class="pln"> </span><span class="pun">{</span>`
2. `<span class="pln"> </span><span class="typ">_List_node_base</span><span class="pun">*</span><span class="pln"> _M_next</span><span class="pun">;</span>`
3. `<span class="pln"> </span><span class="typ">_List_node_base</span><span class="pun">*</span><span class="pln"> _M_prev</span><span class="pun">;</span>`
4. `<span class="pun">};</span>`
5.6. `<span class="kwd">template</span><span class="pln"> </span><span class="pun">&lt;</span><span class="kwd">class</span><span class="pln"> </span><span class="typ">_Tp</span><span class="pun">&gt;</span>`
7. `<span class="kwd">struct</span><span class="pln"> </span><span class="typ">_List_node</span><span class="pln"> </span><span class="pun">:</span><span class="pln"> </span><span class="kwd">public</span><span class="pln"> </span><span class="typ">_List_node_base</span><span class="pln"> </span><span class="pun">{</span>`
8. `<span class="pln"> </span><span class="typ">_Tp</span><span class="pln"> _M_data</span><span class="pun">;</span>`
9. `<span class="pun">};</span>`

不得不说,STL真是博大精深。list将节点的前后指针和其包含的元素分离开来了,这样会使list更具有通用性。以上代码中,_List_node_base中的_M_next和_M_prev分别指向节点的后继和前趋节点,将其作为一个struct封装,而后被_List_node继承。

  • list支持的构造方法为

<pre class="prettyprint linenums prettyprinted">

  1. <span class="kwd">explicit</span><span class="pln"> list </span><span class="pun">(</span><span class="kwd">const</span><span class="pln"> allocator_type</span><span class="pun">&amp;</span><span class="pln"> alloc </span><span class="pun">=</span><span class="pln"> allocator_type</span><span class="pun">());</span><span class="com">// (1)</span>
  2. <span class="kwd">explicit</span><span class="pln"> list </span><span class="pun">(</span><span class="pln">size_type n</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">const</span><span class="pln"> value_type</span><span class="pun">&amp;</span><span class="pln"> val </span><span class="pun">=</span><span class="pln"> value_type</span><span class="pun">(),</span><span class="kwd">const</span><span class="pln"> allocator_type</span><span class="pun">&amp;</span><span class="pln"> alloc </span><span class="pun">=</span><span class="pln"> allocator_type</span><span class="pun">());</span><span class="com">//(2)</span>
  3. <span class="kwd">template</span><span class="pln"> </span><span class="pun">&lt;</span><span class="kwd">class</span><span class="pln"> </span><span class="typ">InputIterator</span><span class="pun">&gt;</span>
  4. <span class="pln">list </span><span class="pun">(</span><span class="typ">InputIterator</span><span class="pln"> first</span><span class="pun">,</span><span class="pln"> </span><span class="typ">InputIterator</span><span class="pln"> </span><span class="kwd">last</span><span class="pun">,</span><span class="kwd">const</span><span class="pln"> allocator_type</span><span class="pun">&amp;</span><span class="pln"> alloc </span><span class="pun">=</span><span class="pln"> allocator_type</span><span class="pun">());</span><span class="com">//(3)</span>
  5. `<span class="pln">list </span><span class="pun">(</span><span class="kwd">const</span><span class="pln"> list</span><span class="pun">&</span><span class="pln"> x</span><span class="pun">);</span><span class="com">//(4)</span>
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    下面分别介绍:
    (1). 即默认的构造函数,使用`list&lt;int&gt; mylist;`便会调用此构造函数。当然你也可以把int换成其他的类型。该函数构造一个空的list容器,其中没有任何元素。称为default constructor。
    (2). 构造一个含有n个元素的list容器,每个元素都是val值的拷贝。称为fill constructor。即构造出来的list是满的。
    (3). 用尽可能多的first和last区间之间的元素构造一个list容器,每个元素对应于元区间的一个元素,并且元素的相对顺序和原来相同。也称为range constructor。
    (4). 用另一个list构造该容器,这两个容器中的元素的值,数量及相对顺序都完全相同。因此这是拷贝构造函数(copy constructor)。
    * 析构函数很简单,只有一个:
    <pre class="prettyprint linenums prettyprinted">
    1. `<span class="pun">~</span><span class="pln">list</span><span class="pun">();</span>

该函数析构容器中的所有元素,并释放他们的空间。

  • 重载赋值运算符

<pre class="prettyprint linenums prettyprinted">

  1. `<span class="pln">list</span><span class="pun">&</span><span class="pln"> </span><span class="kwd">operator</span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">const</span><span class="pln"> list</span><span class="pun">&</span><span class="pln"> x</span><span class="pun">);</span>
    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
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    作用是拷贝x中的所有元素到当前链表中。需要注意的是,operator=函数不是释放掉当前链表的所有节点后再将x中的元素插入其中的,而是保留了当前空间,直接覆盖其元素值以减少分配空间的开销。
    以上就是C++类里的四大金刚函数。list类支持的其他成员函数还有:
    * 返回迭代器:
    <table>
    <thead>
    <tr>
    <th align="left">函数</th>
    <th align="left">功能</th>
    </tr>
    </thead>
    <tbody><tr>
    <td align="left">**begin**</td>
    <td align="left">返回指向链表头的迭代器(public)</td>
    </tr>
    <tr>
    <td align="left">**end**</td>
    <td align="left">返回指向链表尾的迭代器(public)</td>
    </tr>
    <tr>
    <td align="left">**rbegin**</td>
    <td align="left">返回一个反向迭代器,该迭代器指向反向链表的头部(public)</td>
    </tr>
    <tr>
    <td align="left">**rend**</td>
    <td align="left">返回一个反向迭代器,该迭代器指向反向链表的尾部(public)</td>
    </tr>
    </tbody></table>
    * 返回容量:
    <table>
    <thead>
    <tr>
    <th align="left">函数</th>
    <th align="left">功能</th>
    </tr>
    </thead>
    <tbody><tr>
    <td align="left">**empty**</td>
    <td align="left">测试list是否为空(public)</td>
    </tr>
    <tr>
    <td align="left">**size**</td>
    <td align="left">测试list的大小(public)</td>
    </tr>
    <tr>
    <td align="left">**max_size**</td>
    <td align="left">返回list的最大容量(public)</td>
    </tr>
    </tbody></table>
    * 存取元素:
    <table>
    <thead>
    <tr>
    <th align="left">函数</th>
    <th align="left">功能</th>
    </tr>
    </thead>
    <tbody><tr>
    <td align="left">**front**</td>
    <td align="left">获取第一个元素(public)</td>
    </tr>
    <tr>
    <td align="left">**back**</td>
    <td align="left">获取最后一个元素(public)</td>
    </tr>
    </tbody></table>
    * 修改
    <table>
    <thead>
    <tr>
    <th align="left">函数</th>
    <th align="left">功能</th>
    </tr>
    </thead>
    <tbody><tr>
    <td align="left">**assign**</td>
    <td align="left">修改list容器中的元素(public)</td>
    </tr>
    <tr>
    <td align="left">**push_front**</td>
    <td align="left">在list首部插入元素(public)</td>
    </tr>
    <tr>
    <td align="left">**pop_front**</td>
    <td align="left">删除第一个元素(public)</td>
    </tr>
    <tr>
    <td align="left">**push_back**</td>
    <td align="left">在list尾部插入元素(public)</td>
    </tr>
    <tr>
    <td align="left">**pop_back**</td>
    <td align="left">删除最后一个元素(public)</td>
    </tr>
    <tr>
    <td align="left">**insert**</td>
    <td align="left">插入元素(public)</td>
    </tr>
    <tr>
    <td align="left">**erase**</td>
    <td align="left">删除元素(public)</td>
    </tr>
    <tr>
    <td align="left">**swap**</td>
    <td align="left">交换两个元素(public)</td>
    </tr>
    <tr>
    <td align="left">**resize**</td>
    <td align="left">改变list的大小(public)</td>
    </tr>
    <tr>
    <td align="left">**clear**</td>
    <td align="left">清空该list容器(public)</td>
    </tr>
    </tbody></table>
    * 操作方法
    <table>
    <thead>
    <tr>
    <th align="left">函数</th>
    <th align="left">功能</th>
    </tr>
    </thead>
    <tbody><tr>
    <td align="left">**splice**</td>
    <td align="left">在容器间转移元素(public)</td>
    </tr>
    <tr>
    <td align="left">**remove**</td>
    <td align="left">移除特定的元素(public)</td>
    </tr>
    <tr>
    <td align="left">**remove_if**</td>
    <td align="left">移除满足条件的元素(public)</td>
    </tr>
    <tr>
    <td align="left">**unique**</td>
    <td align="left">移除重复的元素(public)</td>
    </tr>
    <tr>
    <td align="left">**merge**</td>
    <td align="left">合并两个list容器(public)</td>
    </tr>
    <tr>
    <td align="left">**sort**</td>
    <td align="left">对元素进行排序(public)</td>
    </tr>
    <tr>
    <td align="left">**reverse**</td>
    <td align="left">反转list容器中的元素(public)</td>
    </tr>
    </tbody></table>
    * 分配空间
    <table>
    <thead>
    <tr>
    <th align="left">函数</th>
    <th align="left">功能</th>
    </tr>
    </thead>
    <tbody><tr>
    <td align="left">**get_allocator**</td>
    <td align="left">分配空间</td>
    </tr>
    </tbody></table>
    list的内存映像如下:
    ![](/images/2016/06/fc7fb3597f01565434aa0c2422a20c8b_list_2.png)
    由此可以看出,list只支持顺序存取,而不支持随机存取,因为其底层实现上各元素不是连续存放的。
    以上只是对list中的成员函数进行了简单的介绍,其中很多函数都是有重载版本的,在此不再一一列举,具有好奇心的读者可移步:[www.cplusplus.com]() ,然后在最上方的搜索栏搜索”list”即可。其实不止是list,C/C++标准库里面的最多内容这里都介绍得非常全面,本文以下即将介绍的各种东东也可以在上面查到。只不过该网站是英文的,英文和我一样挫的读者就多花点时间读一读,还是很值得的!
    ##### vector
    vector和list一样,也属于序列式容器。vector既可以随机存取又可以顺序存取,因为它内部被实现为一个可变长数组,所有元素都被集中放在一块内存空间中。
    vector内部实现如下:
    <pre class="prettyprint linenums prettyprinted">
    1. `<span class="kwd">template</span><span class="pln"> </span><span class="pun">&lt;</span><span class="kwd">class</span><span class="pln"> </span><span class="typ">_Tp</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">_Alloc</span><span class="pun">&gt;</span><span class="pln"> </span>`
    2. `<span class="kwd">class</span><span class="pln"> </span><span class="typ">_Vector_base</span><span class="pln"> </span><span class="pun">{</span>`
    3. `<span class="kwd">public</span><span class="pun">:</span>`
    4. `<span class="pln"> </span><span class="kwd">typedef</span><span class="pln"> </span><span class="typ">_Alloc</span><span class="pln"> allocator_type</span><span class="pun">;</span>`
    5. `<span class="pln"> allocator_type get_allocator</span><span class="pun">()</span><span class="pln"> </span><span class="kwd">const</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> allocator_type</span><span class="pun">();</span><span class="pln"> </span><span class="pun">}</span>`
    6.7. `<span class="pln"> </span><span class="typ">_Vector_base</span><span class="pun">(</span><span class="kwd">const</span><span class="pln"> </span><span class="typ">_Alloc</span><span class="pun">&amp;)</span>`
    8. `<span class="pln"> </span><span class="pun">:</span><span class="pln"> _M_start</span><span class="pun">(</span><span class="lit">0</span><span class="pun">),</span><span class="pln"> _M_finish</span><span class="pun">(</span><span class="lit">0</span><span class="pun">),</span><span class="pln"> _M_end_of_storage</span><span class="pun">(</span><span class="lit">0</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{}</span>`
    9. `<span class="pln"> </span><span class="typ">_Vector_base</span><span class="pun">(</span><span class="typ">size_t</span><span class="pln"> __n</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">const</span><span class="pln"> </span><span class="typ">_Alloc</span><span class="pun">&amp;)</span>`
    10. `<span class="pln"> </span><span class="pun">:</span><span class="pln"> _M_start</span><span class="pun">(</span><span class="lit">0</span><span class="pun">),</span><span class="pln"> _M_finish</span><span class="pun">(</span><span class="lit">0</span><span class="pun">),</span><span class="pln"> _M_end_of_storage</span><span class="pun">(</span><span class="lit">0</span><span class="pun">)</span><span class="pln"> </span>`
    11. `<span class="pln"> </span><span class="pun">{</span>`
    12. `<span class="pln"> _M_start </span><span class="pun">=</span><span class="pln"> _M_allocate</span><span class="pun">(</span><span class="pln">__n</span><span class="pun">);</span>`
    13. `<span class="pln"> _M_finish </span><span class="pun">=</span><span class="pln"> _M_start</span><span class="pun">;</span>`
    14. `<span class="pln"> _M_end_of_storage </span><span class="pun">=</span><span class="pln"> _M_start </span><span class="pun">+</span><span class="pln"> __n</span><span class="pun">;</span>`
    15. `<span class="pln"> </span><span class="pun">}</span>`
    16.17. `<span class="pln"> </span><span class="pun">~</span><span class="typ">_Vector_base</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> _M_deallocate</span><span class="pun">(</span><span class="pln">_M_start</span><span class="pun">,</span><span class="pln"> _M_end_of_storage </span><span class="pun">-</span><span class="pln"> _M_start</span><span class="pun">);</span><span class="pln"> </span><span class="pun">}</span>`
    18.19. `<span class="kwd">protected</span><span class="pun">:</span>`
    20. `<span class="pln"> </span><span class="typ">_Tp</span><span class="pun">*</span><span class="pln"> _M_start</span><span class="pun">;</span>`
    21. `<span class="pln"> </span><span class="typ">_Tp</span><span class="pun">*</span><span class="pln"> _M_finish</span><span class="pun">;</span>`
    22. `<span class="pln"> </span><span class="typ">_Tp</span><span class="pun">*</span><span class="pln"> _M_end_of_storage</span><span class="pun">;</span>`
    23.24. `<span class="pln"> </span><span class="kwd">typedef</span><span class="pln"> simple_alloc</span><span class="pun">&lt;</span><span class="typ">_Tp</span><span class="pun">,</span><span class="pln"> </span><span class="typ">_Alloc</span><span class="pun">&gt;</span><span class="pln"> _M_data_allocator</span><span class="pun">;</span>`
    25. `<span class="pln"> </span><span class="typ">_Tp</span><span class="pun">*</span><span class="pln"> _M_allocate</span><span class="pun">(</span><span class="typ">size_t</span><span class="pln"> __n</span><span class="pun">)</span>`
    26. `<span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="kwd">return</span><span class="pln"> _M_data_allocator</span><span class="pun">::</span><span class="pln">allocate</span><span class="pun">(</span><span class="pln">__n</span><span class="pun">);</span><span class="pln"> </span><span class="pun">}</span>`
    27. `<span class="pln"> </span><span class="kwd">void</span><span class="pln"> _M_deallocate</span><span class="pun">(</span><span class="typ">_Tp</span><span class="pun">*</span><span class="pln"> __p</span><span class="pun">,</span><span class="pln"> </span><span class="typ">size_t</span><span class="pln"> __n</span><span class="pun">)</span><span class="pln"> </span>`
    28. `<span class="pln"> </span><span class="pun">{</span><span class="pln"> _M_data_allocator</span><span class="pun">::</span><span class="pln">deallocate</span><span class="pun">(</span><span class="pln">__p</span><span class="pun">,</span><span class="pln"> __n</span><span class="pun">);</span><span class="pln"> </span><span class="pun">}</span>`
    29. `<span class="pun">};</span>

可以看出,vector内部有三个protected属性的成员变量:_M_start,_M_finish和_M_end_of_storage。分别指向所管理有效元素的开始,结束和所管理空间的尾部(第20~22行)。

既然是数组,在插入元素时就有可能没有空余空间。vector的管理策略是:如果有足够空余空间,就将待插入元素放入。否则开辟一块更大的空间(原来容量的2倍)并将现有元素拷贝过去,然后释放原来的空间并令以上三个指针指向新的空间。

vector支持的很多操作和list一样,对外表现出来的接口也是一样的,只是内部实现不同。

相比于list,新增的操作有

<table> <thead> <tr> <th align="left">函数</th> <th align="left">功能</th> </tr> </thead> <tbody><tr> <td align="left">capacity</td> <td align="left">改变容器大小,修改的是实际容量(public)</td> </tr> <tr> <td align="left">reserve</td> <td align="left">做出所要求的改变(public)</td> </tr> <tr> <td align="left">operator[]</td> <td align="left">存取元素(public)</td> </tr> <tr> <td align="left">at</td> <td align="left">存取元素(public)</td> </tr> </tbody></table>

出于节省空间的考虑,vector内部对bool类型进行了特化vector&lt;bool&gt;,但它与bitset支持的很多操作是不同的。

vector内存映像如图:

<!—

queue/deque
stack
set/multiset
map/multimap

—>

迭代器

迭代器可以看成一种“通用指针”,即它可以作用于任何容器上面。而且即便是不同的容器,通过迭代器所表现出来的访问接口都是一样的,这就为我们提供了很大的方便,使得我们不必了解各种容器的底层实现,也不用去记住那些繁杂的各种容器访问接口,就可以访问他们内部的元素而且使得我们可以编写更具通用性的代码。比如需要遍历list中的元素,可以这样写:

<pre class="prettyprint linenums prettyprinted">

  1. <span class="kwd">typedef</span><span class="pln"> my_type list</span><span class="str">&lt;int&gt;</span><span class="pun">;</span>
  2. <span class="pln">my_type obj</span><span class="pun">;</span>
  3. <span class="pln">my_type</span><span class="pun">:</span><span class="pln">iterator iter</span><span class="pun">=</span><span class="pln">obj</span><span class="pun">.</span><span class="kwd">begin</span><span class="pun">();</span>
  4. <span class="kwd">for</span><span class="pun">(;</span><span class="pln">iter</span><span class="pun">!=</span><span class="pln">obj</span><span class="pun">.</span><span class="kwd">end</span><span class="pun">();++</span><span class="pln">iter</span><span class="pun">)</span>
  5. <span class="pun">{</span>
  6. <span class="pln"> cout</span><span class="pun">&lt;&lt;*</span><span class="pln">iter</span><span class="pun">&lt;&lt;</span><span class="str">" "</span><span class="pun">;</span>
  7. <span class="pun">}</span>
  8. `<span class="pln">cout</span><span class="pun"><<</span><span class="pln">endl</span><span class="pun">;</span>````

现在我不想访问list了,要改成vector。只需要将typedef my_type list&lt;int&gt;改为typedef my_type vector&lt;int&gt;就可以了,后面代码完全不需要改动。

但迭代器本身是为了降低容器和泛型算法之间的耦合性而设计的。使得一些通用算法可以作用于各种容器上。具体例子在算法部分再讲。

虽然迭代器对外表现出统一的接口,但STL中每个容器都有自己专属的迭代器定义。这是因为各种容器的内部实现不同,而迭代器需要准确地定位到容器中,所以就需要不同的方法来实现。

泛型算法

我个人觉得STL中算法是除过容器之外最重要的模块。在algorithm头文件中实现了很多通用算法,如排序,查找,交换,拷贝等等。

常用算法如下:

<table> <thead> <tr> <th align="left">函数</th> <th align="left">功能</th> </tr> </thead> <tbody><tr> <td align="left">for_each</td> <td align="left">对一个区间内的所有元素使用同一个函数</td> </tr> <tr> <td align="left">find find_if find_end find_first_of</td> <td align="left">查找</td> </tr> <tr> <td align="left">adjacent_find</td> <td align="left">查找值相等的相邻元素</td> </tr> <tr> <td align="left">count count_if</td> <td align="left">统计元素个数</td> </tr> <tr> <td align="left">mismatch</td> <td align="left">返回两个区间第一个不匹配的元素位置</td> </tr> <tr> <td align="left">equal</td> <td align="left">两个区间元素是否相等</td> </tr> <tr> <td align="left">search search_n</td> <td align="left">在区间内搜索</td> </tr> <tr> <td align="left">copy</td> <td align="left">拷贝元素</td> </tr> <tr> <td align="left">copy_backward</td> <td align="left">反向拷贝</td> </tr> <tr> <td align="left">swap</td> <td align="left">交换元素</td> </tr> <tr> <td align="left">swap_ranges</td> <td align="left">交换区间</td> </tr> <tr> <td align="left">iter_swap</td> <td align="left">交换两个迭代器指向的元素</td> </tr> <tr> <td align="left">transform</td> <td align="left">对每个元素执行某种操作</td> </tr> <tr> <td align="left">replace replace_if replace_copy replace_copy_if</td> <td align="left">替换元素</td> </tr> <tr> <td align="left">fill fill_n</td> <td align="left">填充</td> </tr> <tr> <td align="left">generate generate_n</td> <td align="left">填充</td> </tr> <tr> <td align="left">remove remove_if remove_copy remove_copy_if</td> <td align="left">移除</td> </tr> <tr> <td align="left">unique unique_copy</td> <td align="left">移除重复的元素</td> </tr> <tr> <td align="left">reverse reverse_copy</td> <td align="left">反转</td> </tr> <tr> <td align="left">rotate rotate_copy</td> <td align="left">旋转</td> </tr> <tr> <td align="left">random_shuffle</td> <td align="left">将序列中元素随机排列</td> </tr> <tr> <td align="left">partition stable_partition</td> <td align="left">将区间分为两部分</td> </tr> <tr> <td align="left">sort stable_sort partial_sort partitl_sort_coy</td> <td align="left">排序</td> </tr> <tr> <td align="left">nth_element</td> <td align="left">排序元素</td> </tr> <tr> <td align="left">lower_bound upper_bound</td> <td align="left">二分查找返回第一个等于给定值的元素位置</td> </tr> <tr> <td align="left">upper_bound upper_bound</td> <td align="left">二分查找返回最后一个等于给定值的元素位置</td> </tr> <tr> <td align="left">equal_range upper_bound</td> <td align="left">二分查找返回等于给定值元素的范围</td> </tr> <tr> <td align="left">binary_search</td> <td align="left">二分查找</td> </tr> <tr> <td align="left">merge</td> <td align="left">归并排序</td> </tr> <tr> <td align="left">inplace_merge</td> <td align="left">原地归并</td> </tr> <tr> <td align="left">includes</td> <td align="left">测试一个已排序的区间是否已经包含了另一个已排序的区间</td> </tr> <tr> <td align="left">set_union</td> <td align="left">连接两个已排序的区间</td> </tr> <tr> <td align="left">set_intersection</td> <td align="left">两个区间的交集</td> </tr> <tr> <td align="left">set_difference set_symmetric_difference</td> <td align="left">两个区间不同的元素</td> </tr> <tr> <td align="left">push_heap</td> <td align="left">往堆中插入元素</td> </tr> <tr> <td align="left">pop_heap</td> <td align="left">从堆中弹出元素</td> </tr> <tr> <td align="left">make_heap</td> <td align="left">建堆</td> </tr> <tr> <td align="left">sort_heap</td> <td align="left">堆排序</td> </tr> <tr> <td align="left">min</td> <td align="left">返回最小值</td> </tr> <tr> <td align="left">max</td> <td align="left">返回最大值</td> </tr> <tr> <td align="left">min_element</td> <td align="left">返回指向最小值的迭代器</td> </tr> <tr> <td align="left">max_element</td> <td align="left">返回指向最大值的迭代器</td> </tr> <tr> <td align="left">lexicographical_compare</td> <td align="left">字典序比较</td> </tr> <tr> <td align="left">next_permutation prev_permutation</td> <td align="left">全排列</td> </tr> </tbody></table>

存储分配器

留坑,以后填。

适配器

函数对象

通用工具