C/C++编程：STL之迭代器Iterator

逃离我推掉我的手 2022-05-18 10:59 231阅读 0赞

# 1、引入 #

## 1.1、指针与数组：用指针遍历数组 ##

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    using namespace std;
    
    void main()
    {
    	const int arrsize = 10;
    	int a[arrsize]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    	int *begin = a;
    	int *end = a + arrsize;
    	for (int *p = begin; p != end; p++)
    	{
    		cout << *p << endl;
    	}
    	system("pause");
    }

*  但是在链表这种数据结构中，存储空间是非连续的。不能通过对指向这种数据结构的指针做累加来遍历
 *  能不能提供一个行为类似指针的类，来对非数组的数据结构进行遍历？这样我们就能够以同样的方式来遍历所有的数据结构\[所有容器

## 1.2、迭代器与容器：用迭代器遍历容器 ##

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    using namespace std;
    
    void main()
    {
    	const int arrsize = 10;
    	int a[arrsize]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    	vector<int>ivec(a, a+arrsize);
    	for (vector<int>::iterator iter = ivec.begin(); iter != ivec.end(); iter++)
    		cout << *iter << ends;
    	/*
    	每种容器都必须提供自己的迭代器
    	容器提供一些函数以获得迭代器并以之遍历所有的元素
    	*/
    	system("pause");
    }

*  通过迭代器，我们可以用相同的方式来访问，遍历\[泛型编程\]容器

![70][]

# 2、迭代器的概念 #

*  可遍历STL容器内全部或部分元素的**对象**
 *  一个迭代器**指出容器中的一个特定位置**
 *  所有容器都提供两种迭代器：container::iterator以“读/写”模式遍历元素， container::const\_iterator以“只读”模式遍历元素
 *  重载了\*，++，==，！=，=运算符，用以操作复杂的数据结构
 *  能够让迭代器与算法不干扰的相互发展，最后又能够无间隙的粘合起来。

![70 1][]

# 3、迭代器的基本操作 #

*  用法和指针一样，其实指针就是一种迭代器

<table> 
 <tbody> 
  <tr> 
   <td>操作</td> 
   <td>效果</td> 
  </tr> 
  <tr> 
   <td>*</td> 
   <td>返回当前位置上的元素值。如果该元素有成员，可以通过迭代器以operator -&gt;取用 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;</td> 
  </tr> 
  <tr> 
   <td>++</td> 
   <td>将迭代器前进至下一元素</td> 
  </tr> 
  <tr> 
   <td>==和!=</td> 
   <td>判断两个迭代器是否指向同一位置</td> 
  </tr> 
  <tr> 
   <td>=</td> 
   <td>为迭代器赋值（将所指元素的位置赋值过去）</td> 
  </tr> 
 </tbody> 
</table>

## 3.1、迭代器与序列式容器 ##

#include <list>
    #include <iostream>
    using namespace std;
    
    int main()
    {
        list<char> coll;      // list container for character elements
    
        // append elements from 'a' to 'z'
        for (char c = 'a'; c <= 'z'; ++c) {
            coll.push_back(c);
        }
    
    
        // -----任何一种元素都有两种迭代器类别
        list<char>::iterator pos1;   // 以读写模式便利元素
        for (pos1 = coll.begin(); pos1 != coll.end(); ++pos1) {
            *pos1 = toupper(*pos1);  // 可以更改元素
        }
    
        list<char>::const_iterator pos;  // 以只读模式遍历元素
        for (pos = coll.begin(); pos != coll.end(); ++pos) {
            cout << *pos << ' ';  // 以为pos为只读模式，所以不能修改这个元素
        }
    
       
        cout << endl;
    }

注意： ++pos比pos++效率高，因为pos++需要一个额外的临时对象，因为它必须存放迭代器的原本位置并将它返回，所以尽量用++pos而不是pos++

![20210131170712622.png][]

## 3.2、迭代器与关联式容器 ##

使用方法和序列式容器一样

#include <set>
    #include <iostream>
    
    int main()
    {
        // type of the collection
        typedef std::set<int> IntSet;
       // typedef std::set<int, std::greater<int>> IntSet; // 指定排序准则
       // typedef std::multiset<int> IntSet;     // 允许重复元素
    
        IntSet coll;        // set container for int values
    
        // insert elements from 1 to 6 in arbitrary order
        // - note that there are two calls of insert() with value 1
        // - 关联式容器会根据排序准则自动将元素插入到正确位置，因此它们没有push_back和push_front，因为不可以指定新元素的位置。
        coll.insert(3);
        coll.insert(1);
        coll.insert(5);
        coll.insert(4);
        coll.insert(1);
        coll.insert(6);
        coll.insert(2);
    
        // print all elements
        // - iterate over all elements
        IntSet::const_iterator pos;
        for (pos = coll.begin(); pos != coll.end(); ++pos) {
            std::cout << *pos << ' ';
        }
        std::cout << std::endl;
    }

所有元素（不论以任何次序）安插完毕之后，容器的状态如图：

*  元素以已序状态(sorted)存放在内部tree结果中，任何一个元素的左子树的所有元素，永远小于右子树的元素
 *  set不允许存在重复元素，所以容器里只有一个1

![20210131171456586.png][]

#include <map>
    #include <string>
    #include <iostream>
    using namespace std;
    
    int main()
    {
        typedef multimap<int, string> IntStringMMap;
        IntStringMMap coll;        // container for int/string values
    
        // assign some elements in arbitrary order
        // - a value with key 1 gets inserted twice
        coll.insert(make_pair(5, "tagged"));
        coll.insert(make_pair(2, "a"));
        coll.insert(make_pair(1, "this"));
        coll.insert(make_pair(4, "of"));
        coll.insert(make_pair(6, "strings"));   // make_pair(1, "is")为辅助函数，用于生成键值对
        coll.insert(make_pair(1, "is"));
        coll.insert(make_pair(3, "multimap"));
    
    
        IntStringMMap::iterator pos;
        for (pos = coll.begin(); pos != coll.end(); ++pos) {
            cout << pos->second << " ";
        }
    
       
        cout << endl;
    }

![20210131172940465.png][]

#include <map>
    #include <string>
    #include <iostream>
    using namespace std;
    
    int main()
    {
        typedef map< string, float> IntStringMap;
        IntStringMap coll;        // container for int/string values
    
        
        coll["VAY"] = 0.15;   //multimap没有[]操作符 
        coll["PI"] = 3.14;  
        coll["NULL"] = 0;
    
        IntStringMap::iterator pos;
        for (pos = coll.begin(); pos != coll.end(); ++pos) {
            cout << pos->first << "->" << pos->second << "\n";
        }
    
       
        cout << endl;
    }

*  存在multimap或者map的元素时，必须通过pair结构的first成员和second成员，才能取出key和value：

![20210131173530582.png][]

# 4、迭代器分类 #

不同容器提供自己的迭代器，所以不同迭代器具有不同的能力

![70 2][]

不同的算法根据需要不同的迭代器的能力，相同的算法需要根据迭代器的能力不同而做相应的优化

![70 3][]

迭代器可以分为两种类型

*  双向迭代器

迭代器可以双向行进：递增或者递减。比如list、set、multiset、map、multimap

*  随机存取迭代器

随机储存迭代器不但具备双向迭代器的所有属性，还可以随机访问。比如vector、deque、strings

备注：尽量不要使用随机存储迭代器的特有操作，这样就可以让代码类型无关了，比如下面：

for (pos = coll.begin(); pos != coll.end(); ++pos) {
            cout << pos->first << "->" << pos->second << "\n";
        }
    
       // 尽量写成上面那种
       for (pos = coll.begin(); pos < coll.end(); ++pos) {
            cout << pos->first << "->" << pos->second << "\n";
        }

#include <iostream>
    #include <list>
    #include <vector>
    #include <set>
    using namespace std;
    
    template<class InputIterator, class Distance>
    void advence_II(InputIterator &i, Distance n)
    {
    	for (; n > 0; --n;++i);  //单向，逐一前进
    }
    template<class BidirectionslIterator, class Distance>
    void advence_II(BidirectionslIterator &i, Distance n)
    {
    	if (n >= 0)  //双向，逐一前进
    		for (; n>0; --n, ++i);
    	else
    		for (; n<0; ++n, --i);
    }
    template<class RandomAccessIterator, class Distance>
    void advence_II(RandomAccessIterator &i, Distance n)
    {
    	i += n;  //随机，跳跃前进
    }
    void main()
    {
    	system("pause");  
    }

[70]: /images/20220518/4451c4b46dd14214ba7ba04e090d5277.png
[70 1]: /images/20220518/59cf09d0f05242a883707c03e2f94c2a.png
[20210131170712622.png]: /images/20220518/26ff504e42114a638b1a8dd5011ac546.png
[20210131171456586.png]: /images/20220518/d5c35837967b46ebab29ed70137a084c.png
[20210131172940465.png]: /images/20220518/47dca74f52eb460d9e4f9face060190c.png
[20210131173530582.png]: /images/20220518/c47355c8c323460a81f2d2ee90c780b4.png
[70 2]: /images/20220518/cb49afe2b8f04058846b4ec06be5505e.png
[70 3]: /images/20220518/f05a3797f3d3485dae12c9c1205a58b9.png