技术: C++ 标准库 STL

技术

本文是当年我学习 stl 时的一些体会和总结, 如果你是初学者, 不妨参考一下我上传的 学习记录

STL模板中, 唯一比较难得熟悉的是算法部分; 容器, 迭代器部分则相对好一些.

引子

标准库的学习不需要认认真真地读书, 需要的是在了解概貌的情况下, 在实践中深入.
(需要泛型基础)
“通过使用算法和容器, 简化编程任务” 这才是重点.

正文

STL主要涉及: 容器, 迭代器, 算法, 仿函数, 适配器, 分配器.

在 C++标准中， STL 被组织为下面的 13 个头文件: (不用记忆, 用的久了就知道了)

1
2
<algorithm>,  <deque>, <functional>, <iterator>, <vector>, <list>,
<map>, <memory>, <numeric>, <queue>, <set>, <stack>, <utility>

除了 分配器 不常用, 其他5个组件都非常常用, 而且是配合使用.

  • STL是c++的一部分, 编译器支持.
  • STL在设计时就是算法和数据结构分离的(其实是得益于泛型).
  • 程序员可以不用思考 STL 具体的实现过程, 只要能够熟练使用 STL 就 OK 了, 这样他们就可以把精力放在程序开发的别的方面.
  • STL的实现也比较高效: 如 map 可以高效地从十万条记录里面查找出指定的记录, 因为 map 是采用红黑树的变体实现的(红黑树是平横二叉树的一种)
  • 什么情况下使用什么容器和算法, 这个很重要.

C++中10类标准库, 用的时候再去看吧.

我们更多的关注的是, 各种容器&算法的使用场景, 具体的用法;

具体的容器和算法的讲解, 可以参考一下我的github记录(string, vector, deque, stack, queue, list, priority_queue, set, map等)

但是有些容器是需要了解底层实现的数据结构的, 比如说 “为什么不可以修改set元素的值?” (因为set底层是用红黑树实现的, 因为该类容器是自动排序的(改变节点的值会打乱原有的顺序). 如果希望修改一个set元素值, 必须先删除原有的元素, 再插入新的元素)

容器

数据结构一般不会让你去实现, 但是会让你根据合适的场景选择和包装数据结构.
(必须知道每种容器的特点)
常用的容器如下 (注意下容器适配器)

1
<vector>, <list>, <deque>, <set>, <map>, <stack> 和 <queue>.

必须非常熟悉的容器有:

  • 序列式容器
    (有固定位置, 和插入时间和地点有关, 和元素本身无关)
    • vector: 向量 (顺序存储)
    • list: 双向链表 (链式存储)
    • deque: 双端队列 (顺序存储)
  • 关联式容器
    (元素位置取决于特定的排序准则, 和插入顺序无关)
    • set/multiset: 集合 (多重集合, 允许存在两个次序相等的元素的集合)由节点组成的红黑树, 每个节点都包含着一个元素
    • map/multimap: 键值对(映射)–多重映射允许键对有相等的次序(key可以不唯一); map默认按照key升序
      (这两种容器遍历的时候可能用到pair结构: 函数返回两个迭代器, 而这两个迭代器被封装在 “pair” 中, pair.first , pair.second)

其他不常用容器:
(操作受限的容器, 又可以称作序列容器适配器)

  • stack: 栈 (简单装饰deque而形成的一种容器)
  • queue: 队列(简单装饰deque而形成的一种容器)

  • priority_queue: 优先队列(最大值优先级队列, 最小值优先级队列)

    1
    2
    3
    4
    //priority_queue<int, vector<int>, less<int> > p1; //默认是 最大值优先级队列
    priority_queue<int> p1; //简化的写法

    priority_queue<int, vector<int>, greater<int>> p2; //最小值优先级队列

    这个元素没有iterator迭代器成员, 注意其遍历方式

    1
    2
    3
    4
    5
    6
    7
    priority_queue<int> p1; 
    p1.push(11);//...
    while (p2.size() > 0)
    {
        cout << p2.top() << " ";
        p2.pop();
    }

(当然各个容器还有各自的注意事项, 说起来比较多, 就没有必要详细展开了)

迭代器

迭代器部分主要由头文件 utility , iterator 和 memory 组成。

  • utility是一个很小的头文件, 它包括了贯穿使用在 STL 中的几个模板的声明
  • iterator提供了迭代器使用的许多方法
  • memory的描述则十分的困难, 它以不同寻常的方式为容器中的元素分配存储空间, 同时也为某些算法执行期间产生的临时对象提供机制. memory中的主要部分是模板类 allocator, 它负责产生所有容器中的默认分配器.

5种迭代器: 输入迭代器, 输出迭代器, 正向迭代器, 双向迭代器, 随机访问迭代器.
(后两种用的比较多)

双向迭代器支持: ++, –, *, =, !=, ==操作 (list,set,multiset,map,multimap)
随机迭代器在此基础上支 +=n, >, >=, <, <=操作 (一般是顺序存储的序列容器支持, vector, deque)

注意end()总是指向容器最后的下一个位置, rend()指向开头的前一个位置;

下面是迭代器的简单使用:

1
2
3
4
5
6
7
8
9
for(vector<int>::iterator it=vecInt.begin(); it!=vecInt.end(); ++it)
{
    int iItem = *it;
    cout << iItem; //或直接使用 cout << *it;
}
//或者反向
for(vector<int>::reverse_iterator rit=vecInt.rbegin(); rit!=vecInt.rend(); ++rit){
    cout << *it;
}

其他迭代器

1
2
//不修改元素的值
vector<int>::const_iterator 与 vector<int>::const_reverse_iterator

建议: 

《Effective STL 》 建议我们尽量使用 iterator 取 代 const_iterator , reverse_iterator 和 const_reverse_iterator.

(迭代器的使用也有一些技巧, 用好了也是事半功倍, 本文就不再展开讨论了)

算法

怎么样让模板参数支持不同类型的呢? (模板特化, 延迟类型选择)
只需要通过调用一两个算法模板, 就可以完成所需要的功能, 并大大地提升效率.

算法部分主要由头文件 algorithm , numeric 和 functional 组成.

  • algorithm是所有STL头文件中最大的一个(尽管它很好理解), 它是由一大堆模版函数组成的, 可以认为每个函数在很大程度上都是独立的, 其中常用到的功能范围涉及到比较、 交换、 查找、 遍历操作、 复制、 修改、 移除、 反转、 排序、 合并等等 (最常用的算法: 置换, 排序, 合并, 搜索)
  • numeric体积很小, 只包括几个在序列上面进行简单数学运算的模板函数, 包括加法和乘法在序列上的一些操作
  • functional中则定义了一些模板类, 用以声明函数对象(functor)

这个部分内容比较多(非常多, 差不多将近80个常用算法).

比如for_each()函数和 transform函数 的区别?

1
2
3
vector<int> v(5,2); //2, 2, 2, 2, 2
for_each(v.begin(), v.end(), mycompare);
transform(v.begin(), v.end(), v.begin(), mycompare2);

一般情况下:
for_each所使用的的函数对象, 参数是引用, 没有返回值;
transform所使用的函数对象, 参数不使用引用, 而且有返回值.

函数对象和谓词

函数对象和谓词函数时比较重要的概念, 取代之前C中的回调或者函数指针.

  • 函数对象(functor)
    重载 函数调用操作符 的类, 其对象常称为函数对象(function object), 即它们是行为类似函数的对象. 一个类对象, 表现出一个函数的特征, 就是通过”对象名+(参数列表)”的方式使用一个类对象. 如果没有上下文, 完全可以把它看作一个函数对待. 这是通过重载类或者struct的 operator()来实现的. “在标准库中, 函数对象被广泛地使用以获得弹性”, 标准库中的很多算法都可以使用函数对象或者函数来作为自定的回调行为(就相当于函数指针).
    下面举出 greater的简易实现原理:

    1
    2
    3
    4
    5
    6
    7
    8
    struct greater
    {
        bool operator() (const int& iLeft, const int& iRight)
        {
            //如果是实现 less<int>的话， 这边是写 return (iLeft<iRight);
            return (iLeft>iRight);
        }
    }

    容器就是调用函数对象的 operator()方法去比较两个值的大小.
    并且关联容器如果想使用sort, merge, less, greater等算法, 那么放入其中的元素就要提供operator<()或者operator>()运算重载.

  • 谓词

    • n元函数对象: 函数参数 n 个
    • n元谓词函数: 函数参数 n 个, 函数返回值是 bool 类型, 可以作为一个判断表达式
  • 算数函数对象
    主要有 plus , minus , multiplies , divides 等.
  • 特殊函数对象
    主要是指 约束器, 适配器, 否定器 (绑定适配器, 组合适配器, 指针函数适配器, 成员函数适配器)
    • bind1st(x), bind2nd(y)
    • not1(), not2()
    • ptr_fun()等

尾巴

参考资料

  1. 《C++标准库(自学教程与参考手册) 2e》 上下两册 (经过改版的加入了很多C++11的特性)
  2. 《大道至简C++STL精解》 机械工业出版社

本文标题:技术: C++ 标准库 STL

文章作者:Merlin

发布时间:2016-06-21, 22:53:14

最后更新:2018-04-12, 14:55:17

原始链接:http://www.merlinblog.site/posts/e53c44b8/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 引子
  2. 2. 正文
    1. 2.1. 容器
    2. 2.2. 迭代器
    3. 2.3. 算法
    4. 2.4. 函数对象和谓词
  3. 3. 尾巴
  4. 4. 参考资料
|