本文共 4977 字，大约阅读时间需要 16 分钟。

迭代器的意义

迭代器应该有的特征

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

建议

stl总结

STL的五种迭代器类型

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

不修改容器中的值

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

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

3.正向迭代器

 输入迭代器 + 输出迭代器

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

4.双向迭代器

正向迭代器+ 可以回头看 

5.随机访问迭代器

双向迭代器+ 随机访问

5个迭代器的层次结构

i为迭代器，n为整数

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

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

概念

模型

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

 

STL提供的预定义迭代器

1. ostream_iterator模板

适配器。 输出迭代器

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

 

2.istream_iterator模板

输入迭代器

跟ostream_iterator相反

 

其他的预定义迭代器类型

reverse_iterator

用来反向迭代

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

rbegin()和rend() 

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

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

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

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

程序示例

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

运行结果

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

这是复制到out_iter中

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

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

back_insert_iterator, front_insert_iterator insert_iterator

使用方法：

将容器作为模板参数传入

front_insert_iterator和 back_insert_iterator

back_insert_iterator<vector<int>> back_iter(dice);

 

insert_iterator

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

insert_iterator<vector<int>> insert_iter(dice, dice.begin())

程序示例

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        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
        
          words(4); copy(s1, s1 + 4, words.begin()); for_each(words.begin(), words.end(), output); cout << endl; copy(s2, s2 + 2, back_insert_iterator
         
          
            >(words)); for_each(words.begin(), words.end(), output); cout <
           
             > (words, words.begin())); for_each(words.begin(), words.end(), output); cout << endl; return 0;}
           
          
         
        
       
      
     
    
   

程序说明

 

容器种类

15种 嗯。。很多

容器概念

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

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

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

基本的容器特征要求

X：容器类型

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

a,b：类型为X的值

r：X&的值

u：类型为X的标识符

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

就是算法的时间复杂度

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

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

嗯。。。18章再说

 

序列：

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

7种STL容器： deque, forward_list, list, queue, priority_queue, stack, vector

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

序列的要求

X：容器类型

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

a,b：类型为X的值

r：X&的值

u：类型为X的标识符

t：表示类型为T的值

n：整数

p,q,i,j：迭代器

序列可选的要求

a.at(t) 会检查边界，超出的话会抛out_of_range异常

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

各序列容器说明

vector:

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

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

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

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

2.deque:

双端队列

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

处理速度比vector慢

3.list:

双向链表

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

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

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

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

也是可翻转容器

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

list独有的成员函数

list程序示例：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       void outint(int n) {std::cout << n << " ";}int main(){  using namespace std;// 建立元素为5个2的list容器one  list
       
         one(5, 2);  int stuff[5] = {1, 2, 4, 8, 6};  list
        
          two;// 将stuff[0]到stuff[5]之间的元素拉到two头位置插入 two.insert(two.begin(), stuff, stuff + 5); int more[6] = {6, 4, 2, 4, 6, 5}; list
         
           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;}
         
        
       
      
     
    
   

运行结果

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

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

 

forward_list(C++ 11)

单链表 正向迭代器 

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

4.queue

头文件<queue>

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

底层是deque

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

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

5.priority_queue

<queue>

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

6.stack

<stack>

提供了栈接口

对栈的操作

7.array

<array>非STL

长度固定

参考第四章

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

有遍历的操作。 

可以使用copy()和for_each()等STL算法

先完结。 其他的明天再写 

 

转载地址：http://qiepi.baihongyu.com/