C++ Primer Plus 学习笔记第十六章泛型编程迭代器，容器

Bertha 。 2022-10-02 10:46 187阅读 0赞

迭代器的意义

![20190618085510187.png][]

迭代器应该有的特征

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70][]

前i++和++i的操作符重写

![2019061809103865.png][]

建议

![20190618091049376.png][]

stl总结

![20190618091058316.png][]

STL的五种迭代器类型

1.输入迭代器（读取容器中的数据）

不修改容器中的值

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 1][]

上图说的情况可能是指类似链表一样的数据结构的迭代

2.输出迭代器（修改容器内的值，不读取）

![20190618104718515.png][]

3.正向迭代器

输入迭代器 + 输出迭代器

只能往前走（ + ）不能回头看( - )

4.双向迭代器

正向迭代器+ 可以回头看

![20190618110519101.png][]

5.随机访问迭代器

双向迭代器+ 随机访问

![20190618111602842.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 2][]

5个迭代器的层次结构

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 3][]

i为迭代器，n为整数

根据不同场景需求使用不同的迭代器，尽量使用要求最低的迭代器

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 4][]

STL的copy()默认不支持将数据copy到空对象中

概念

![20190618114009386.png][]

模型

![20190618114016391.png][]

指针其实就是一个随机访问迭代器模型

STL提供的预定义迭代器

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 5][]

1. ostream\_iterator模板

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 6][]

适配器。 输出迭代器

将一些其他接口转换为STL使用的接口

2.istream\_iterator模板

输入迭代器

跟ostream\_iterator相反

![20190619122322897.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 7][]

其他的预定义迭代器类型

reverse\_iterator

用来反向迭代

这里涉及到两个成员函数（vector类）

rbegin()和rend()

rbegin() 指向超尾的反向迭代器

rend() 指向第一个元素的反向迭代器

![20190619123244247.png][]

当使用rbegin()时不能解引用 因为是指向超威。 所以必须要往前走一个位置

rend()是在第一个位置。所以要提前一个位 因为 区间的结尾处不包括在区间中。

![2019061912352110.png][]

程序示例

#include <iostream>
    #include <iterator>
    #include <vector>
    #include <string>
    
    int main()
    {
      using namespace std;
    
      int casts[10] = {6, 7, 2, 9, 4, 11, 8, 7, 10, 5};
      vector<int> dice(10);
      copy(casts, casts + 10, dice.begin());
      cout <<"Let the dice be cast.\n";
      ostream_iterator<int, char> out_iter(cout, " ");
      copy(dice.begin(), dice.end(), out_iter);
      cout << endl;
    
      return 0;
    }

运行结果

![20190619125147659.png][]

尽量使用STL函数来处理内部问题

这是复制到out\_iter中

这样有两个问题 第一个是 要事先有固定长度，并且会覆盖掉原来的内容。

另外三种迭代器解决了这两个问题

back\_insert\_iterator, front\_insert\_iterator insert\_iterator

![20190619130119437.png][]

![20190619130239809.png][]

使用方法：

将容器作为模板参数传入

front\_insert\_iterator和 back\_insert\_iterator

back\_insert\_iterator<vector<int>> back\_iter(dice);

![20190619130656803.png][]

![20190619130703779.png][]

insert\_iterator

insert\_iterator必须要添加一个插入位置的构造函数参数

insert\_iterator<vector<int>> insert\_iter(dice, dice.begin())

程序示例

#include <iostream>
    #include <string>
    #include <iterator>
    #include <vector>
    #include <algorithm>
    
    void output(const std::string & s) {std::cout << s << " ";}
    
    int main()
    {
      using namespace std;
      string s1[4] = {"fine", "fish", "fashion", "fate"};
      string s2[2] = {"busy", "bats"};
      string s3[2] = {"silly", "singers"};
    
      vector<string> words(4);
      copy(s1, s1 + 4, words.begin());
      for_each(words.begin(), words.end(), output);
      cout << endl;
      
      copy(s2, s2 + 2, back_insert_iterator<vector<string> >(words));
      for_each(words.begin(), words.end(), output);
      cout <<endl;
    
      copy(s3, s3 + 2, insert_iterator<vector<string> > (words, words.begin()));
      for_each(words.begin(), words.end(), output);
      cout << endl;
    
      return 0;
    }

![20190619133523560.png][]

程序说明

![20190619133733626.png][]

容器种类

![20190619134008616.png][]

15种 嗯。。很多

容器概念

容器的实现没有继承 所以在理论上描述其通用特征 以便所有的容器遵循这些特征

概念1，容器中存储对象的要求

![20190619134249157.png][]

c++11增加了可复制插入和可移动插入

基本的容器特征要求

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 8][]

X：容器类型

T： 存储在容器中的对象类型

a,b：类型为X的值

r：X&的值

u：类型为X的标识符

复杂度：表示事件复杂到 从快到慢为：编译时间->固定时间->线性时间

![2019061913474560.png][]

就是算法的时间复杂度

![20190619134822698.png][]

C++ 11新加的对容器的要求

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 9][]

rv：X的非常量右值，如函数的返回值

![20190619135338995.png][]

嗯。。。18章再说

序列：

基本容器的改进（类似继承）

7种STL容器： deque, forward\_list, list, queue, priority\_queue, stack, vector

array也算，但并不满足所有的序列所有的要求

![20190619135723310.png][]

序列的要求

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 10][]

X：容器类型

T： 存储在容器中的对象类型

a,b：类型为X的值

r：X&的值

u：类型为X的标识符

t：表示类型为T的值

n：整数

p,q,i,j：迭代器

序列可选的要求

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 11][]

a.at(t) 会检查边界，超出的话会抛out\_of\_range异常

push\_front(t)和pop\_front(t)中不包含vector的原因 如果让vector也有该功能的话 那时间复杂度是线性的

各序列容器说明

vector:

动态分配内存，自动内存管理。提供对元素的四季访问。

在尾部添加和删除：固定时间

头部、中间插入或删除元素：线性时间

也是反转容器 rbegin(), rend()

![20190619141502422.png][]

2.deque:

双端队列

vector + 开头位置的插入和删除的时间复杂度是固定的。

处理速度比vector慢

3.list:

双向链表

vector + 任意位置插入和删除的时间复杂度是固定的。

vector强调的是通过随机访问进行快速访问

list签掉的是快速插入和删除

（这其实就是线性表和链表的差别）

也是可翻转容器

不支持数组表示和随机访问

list独有的成员函数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 12][]

list程序示例：

#include <iostream>
    #include <list>
    #include <iterator>
    #include <algorithm>
    
    void outint(int n) {std::cout << n << " ";}
    
    int main()
    {
      using namespace std;
    // 建立元素为5个2的list容器one
      list<int> one(5, 2);
      int stuff[5] = {1, 2, 4, 8, 6};
      list<int> two;
    // 将stuff[0]到stuff[5]之间的元素拉到two头位置插入
      two.insert(two.begin(), stuff, stuff + 5);
      int more[6] = {6, 4, 2, 4, 6, 5};
      list<int> three(two);
      three.insert(three.end(), more, more + 6);
    
      cout << "List one: ";
      for_each(one.begin(), one.end(), outint);
      cout << endl << "List two: ";
      for_each(two.begin(), two.end(), outint);
      cout << endl << "List three: ";
      for_each(three.begin(), three.end(), outint);
    // 删除值为2的元素
      three.remove(2);
      cout << endl << "List three minus 2s: ";
      for_each(three.begin(), three.end(), outint);
    // 将one的元素追加到three的头位置，one清空
      three.splice(three.begin(), one);
      cout << endl << "List three after splice: ";
      for_each(three.begin(), three.end(), outint);
      cout << endl << "List one: ";
      for_each(one.begin(), one.end(), outint);
    // 删除three容器中连续相同的元素，注意 是连续相同
      three.unique();
      cout << endl << "List three after unique: ";
      for_each(three.begin(), three.end(), outint);
    // 排序
      three.sort();
      three.unique();
      cout << endl << "List three after sort & unique: ";
      for_each(three.begin(), three.end(), outint);
      two.sort();
    // 合并 合并前需要先排序，才能合并,合并完two清空
      three.merge(two);
      cout << endl << "Sorted two merged into three: ";
      for_each(three.begin(), three.end(), outint);
      cout << endl;
    
      cout << endl << "List two: ";
      for_each(two.begin(), two.end(), outint);
      cout << endl;
    
      return 0;
    }

运行结果

![2019061914490030.png][]

insert()是复制 splice()是移动

![20190619145207807.png][]

非成员sort()函数需要随机访问迭代器。但是list并不是 快速插入的代价是放弃随机访问功能。所以只能用成员函数版本的sort()

![20190619145330505.png][]

forward\_list(C++ 11)

单链表 正向迭代器

比list更简单，紧凑，功能更少

4.queue

头文件<queue>

ostream\_iterator的适配器类，让输出流能够使用迭代器接口

底层是deque

不让随机访问，不让遍历，

\+队尾，-队首，看队尾和队首的值，元素数目，队列是否为空

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 13][]

![20190619150026464.png][]

5.priority\_queue

<queue>

适配器。与queue区别在于 最大的元素放在队首 底层是vector

6.stack

<stack>

提供了栈接口

对栈的操作

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 14][]

7.array

<array>非STL

长度固定

参考第四章

没有定义调整容器大小的操作

有遍历的操作。

可以使用copy()和for\_each()等STL算法

先完结。 其他的明天再写

[20190618085510187.png]: /images/20220112/b93b9943726e4b29aa00711452299524.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70]: /images/20220112/ac774b5c678c44eab087f874f39c426f.png
[2019061809103865.png]: /images/20220112/e0dc44da469f4c6f9ca4b915a52df599.png
[20190618091049376.png]: /images/20220112/0c0ca249023346f5a3dd03594320ac27.png
[20190618091058316.png]: /images/20220112/b3008b08ddb8495faf101bdbcfa40508.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 1]: /images/20220112/039b85fc951f4f579a269c8578b4976f.png
[20190618104718515.png]: /images/20220112/12887b100acd4f1788f413f137a65a4f.png
[20190618110519101.png]: /images/20220112/d7da77ce781b4bfc887532d6dcf49860.png
[20190618111602842.png]: /images/20220112/f7603a54f89b41d4974cd3d846eef651.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 2]: /images/20220112/0f2cd73279c44bee9a154bf553e65173.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 3]: /images/20220112/e08a98cc7d88422cb6dfeb03bb381de6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 4]: /images/20220112/30ba09a2a2984d598b557a2e5f81fa43.png
[20190618114009386.png]: /images/20220112/ebd4fef425cf479c9b748a72972f6cab.png
[20190618114016391.png]: /images/20220112/f45e6ea5e7a3438e94ff77b4de0e68ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 5]: /images/20220112/5d478894b07a4413899e86e105e90eee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 6]: /images/20220112/ce3c8c3337e64394bbfd195bf17e996e.png
[20190619122322897.png]: /images/20220112/b7b20d7081fa4954bf139c11c7a17e8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 7]: /images/20220112/477891f7e9124ef2a99e0eb711dda55a.png
[20190619123244247.png]: /images/20220112/709afbd36c6c4947aa3fe7ec78523fff.png
[2019061912352110.png]: /images/20220112/44cb80940c524bde99055194ab715310.png
[20190619125147659.png]: /images/20220112/efb6d9b26b8c4dd7ad6138f188364e09.png
[20190619130119437.png]: /images/20220112/04428aacb0f14534962ea44481f2e601.png
[20190619130239809.png]: /images/20220112/2bd3f3d61ba446169cc50a9bd5bca0b5.png
[20190619130656803.png]: /images/20220112/6bd1e3d109454804952e5a0f896d000a.png
[20190619130703779.png]: /images/20220112/6236560968544eb986783d56b4b484a2.png
[20190619133523560.png]: /images/20220112/a5eaea414c2c446998e4df440810a3ba.png
[20190619133733626.png]: /images/20220112/53e3fafa032240fdb3ec4e78e3147c3a.png
[20190619134008616.png]: /images/20220112/7453ab2ba93c48d9bf536ae44b87dcf3.png
[20190619134249157.png]: /images/20220112/b2efc643220c4eaea8ed799e7775010d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 8]: /images/20220112/32b2507257234605a704667855793d4a.png
[2019061913474560.png]: /images/20220112/ab7b93846dc446b29bda5901d1b31f1e.png
[20190619134822698.png]: /images/20220112/ca0408d840c445ecbbacaffe81ae872a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 9]: /images/20220112/d0a8287235e8447886c300b78193bbff.png
[20190619135338995.png]: /images/20220112/46747ea351674f5fa1559b5a67465ab8.png
[20190619135723310.png]: /images/20220112/25760775cbc34a41a16b5b6f991a6a40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 10]: /images/20220112/839c89650aa943f28aa4effaff01b2ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 11]: /images/20220112/aefe98c92ac049e69975dab031c20275.png
[20190619141502422.png]: /images/20220112/3378d01f15c24c1f9bbda262f48202ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 12]: /images/20220112/6d1125eec0084bea9349e7636ed102e8.png
[2019061914490030.png]: /images/20220112/d9a37d2a1f03463c8e8c21bdba3e08b9.png
[20190619145207807.png]: /images/20220112/f6f207d2c1024ca9b57dc9f8f60cec9b.png
[20190619145330505.png]: /images/20220112/43e050c2ca1a4ca09e060f002cd35706.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 13]: /images/20220112/e2ddbd1aef334a70937c1d4faf5a64ef.png
[20190619150026464.png]: /images/20220112/00b423e6bd6f46dc80eac2ac73236acb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 14]: /images/20220112/d8154b0ae1b543ac82f40774c6cee8cd.png