STL--迭代器（iterator）

指针与数组

指针与其它数据结构呢？比如说链表？

存储空间是非连续的。不能通过对指向这种数据结构的指针做累加来遍历。

能不能提供一个行为类似指针的类，来对非数组的数据结构进行遍历呢？这样我们就能够以同样的方式来遍历所有数据结构（容器）。

迭代器(Iterator)是指针(pointer)的泛化，它允许程序员以相同的方式处理不同的数据结构(容器)。STL中有五种类型的迭代器，它们分别满足一定的要求。不同的迭代器要求定义的操作不一样。

箭头表示左边的迭代器一定满足右边迭代器需要的条件。

下面的图表画出了这几种：

            input         output
              \            /
                 forward
                     |
                bidirectional
                     |
               random access

要注意，上面这图表并不是表明它们之间的继承关系：而只是描述了迭代器的种类和接口。处于图表下层的迭代器都是相对于处于图表上层迭代器的扩张集。例如：forward迭代器不但拥有input和output迭代器的所有功能，还拥有更多的功能。

比如某个算法需要一个双向迭代器(Bidirctional Iterator)，你可以把一个任意存取迭代器(Random Access Iterator)作为参数；但反之不行。

本文地址：http://www.cnblogs.com/archimedes/p/cpp-iterator.html，转载请注明源地址。

迭代器iterator 提供了一种一般化的方法对顺序或关联容器类型中的每个元素进行连续访问

例如，假设iter为任意容器类型的一个iterator，则++iter 表示向前移动迭代器使其指向容器的下一个元素，而*iter 返回iterator 指向元素的值，每种容器类型都提供一个begin()和一个end()成员函数。

begin()返回一个iterator 它指向容器的第一个元素

end()返回一个iterator 它指向容器的末元素的下一个位置

通过迭代器，我们可以用相同的方式来访问、遍历容器。

 

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

迭代器的作用：

  • 能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来。
  • 重载了*，++，＝＝，！＝，＝运算符。用以操作复杂的数据结构。
  • 容器提供迭代器，算法使用迭代器。

各个迭代器的功能如下：


迭代器类别
说明

输入
从容器中读取元素。输入迭代器只能一次读入一个元素向前移动，输入迭代器只支持一遍算法，同一个输入迭代器不能两遍遍历一个序列

输出
向容器中写入元素。输出迭代器只能一次一个元素向前移动。输出迭代器只支持一遍算法，统一输出迭代器不能两次遍历一个序列

正向
组合输入迭代器和输出迭代器的功能，并保留在容器中的位置

双向
组合正向迭代器和逆向迭代器的功能，支持多遍算法

随机访问
组合双向迭代器的功能与直接访问容器中任何元素的功能，即可向前向后跳过任意个元素

迭代器的操作：

每种迭代器均可进行包括表中前一种迭代器可进行的操作。


迭代器操作
说明

所有迭代器

p++
后置自增迭代器

++p
前置自增迭代器

输入迭代器

*p
复引用迭代器，作为右值

p=p1
将一个迭代器赋给另一个迭代器

p==p1
比较迭代器的相等性

p!=p1
比较迭代器的不等性

输出迭代器

*p
复引用迭代器，作为左值

p=p1
将一个迭代器赋给另一个迭代器

正向迭代器
提供输入输出迭代器的所有功能

双向迭代器

--p
前置自减迭代器

p--
后置自减迭代器

随机迭代器

p+=i
将迭代器递增i位

p-=i
将迭代器递减i位

p+i
在p位加i位后的迭代器

p-i
在p位减i位后的迭代器

p[i]
返回p位元素偏离i位的元素引用

p<p1
如果迭代器p的位置在p1前，返回true，否则返回false

p<=p1
p的位置在p1的前面或同一位置时返回true，否则返回false

p>p1
如果迭代器p的位置在p1后，返回true，否则返回false

p>=p1
p的位置在p1的后面或同一位置时返回true，否则返回false

只有顺序容器和关联容器支持迭代器遍历，各容器支持的迭代器的类别如下：


容器
支持的迭代器类别
说明

vector
随机访问
一种随机访问的数组类型，提供了对数组元素进行快速随机访问以及在序列尾部进行快速的插入和删除操作的功能。可以再需要的时候修改其自身的大小

deque
随机访问
一种随机访问的数组类型，提供了序列两端快速进行插入和删除操作的功能。可以再需要的时候修改其自身的大小

list
双向
一种不支持随机访问的数组类型，插入和删除所花费的时间是固定的，与位置无关。

set
双向
一种随机存取的容器，其关键字和数据元素是同一个值。所有元素都必须具有惟一值。

multiset
双向
一种随机存取的容器，其关键字和数据元素是同一个值。可以包含重复的元素。

map
双向
一种包含成对数值的容器，一个值是实际数据值，另一个是用来寻找数据的关键字。一个特定的关键字只能与一个元素关联。

multimap
双向
一种包含成对数值的容器，一个值是实际数据值，另一个是用来寻找数据的关键字。一个关键字可以与多个数据元素关联。

stack
不支持
适配器容器类型，用vector，deque或list对象创建了一个先进后出容器

queue
不支持
适配器容器类型，用deque或list对象创建了一个先进先出容器

priority_queue
不支持
适配器容器类型，用vector或deque对象创建了一个排序队列

 

下面列举了些例子说明各个容器的用法：

1、vector

#include <iostream>
#include <vector>

int main()
{
    std::vector<char> charVector;

    int x;
    for (x=0; x<10; ++x)
        charVector.push_back(65 + x);

    int size = charVector.size();
    for (x=0; x<size; ++x)
    {
        std::vector<char>::iterator start =
            charVector.begin();
        charVector.erase(start);
        std::vector<char>::iterator iter;
        for (iter = charVector.begin();
                iter != charVector.end(); iter++)
        {
            std::cout << *iter;
        }
        std::cout << std::endl;
    }

    return 0;
}

2、deque

#include <iostream>
#include <deque>

int main()
{
    std::deque<char> charDeque;
    int x;
    for (x=0; x<10; ++x)
        charDeque.push_front(65 + x);

    int size = charDeque.size();
    for (x=0; x<size; ++x)
    {
        std::deque<char>::iterator start =
            charDeque.begin();
        charDeque.erase(start);
        std::deque<char>::iterator iter;
        for (iter = charDeque.begin();
                iter != charDeque.end(); iter++)
        {
            std::cout << *iter;
        }
        std::cout << std::endl;
    }

    return 0;
}

3、list

#include <iostream>
#include <list>

int main()
{
    // Create and populate the list.
    int x;
    std::list<char> charList;
    for (x=0; x<10; ++x)
        charList.push_front(65 + x);

    // Display contents of list.
    std::cout << "Original list: ";
    std::list<char>::iterator iter;
    for (iter = charList.begin();
            iter != charList.end(); iter++)
    {
        std::cout << *iter;
        //char ch = *iter;
        //std::cout << ch;
    }
    std::cout << std::endl;

    // Insert five Xs into the list.
    std::list<char>::iterator start = charList.begin();
    charList.insert(++start, 5, 'X');

    // Display the result.
    std::cout << "Resultant list: ";
    for (iter = charList.begin();
    iter != charList.end(); iter++)
    {
        std::cout << *iter;
        //char ch = *iter;
        //std::cout << ch;
    }

    return 0;
}

4、set

#include <iostream>
#include <set>

int main()
{
    // Create the set object.
    std::set<char> charSet;

    // Populate the set with values.
    charSet.insert('E');
    charSet.insert('D');
    charSet.insert('C');
    charSet.insert('B');
    charSet.insert('A');

    // Display the contents of the set.
    std::cout << "Contents of set: " << std::endl;
    std::set<char>::iterator iter;
    for (iter = charSet.begin(); iter != charSet.end(); iter++)
        std::cout << *iter << std::endl;
    std::cout << std::endl;

    // Find the D.
    iter = charSet.find('D');
    if (iter == charSet.end())
        std::cout << "Element not found.";
    else
        std::cout << "Element found: " << *iter;

    return 0;
}

5、multiset

#include <iostream>
#include <set>

int main()
{
    // Create the first set object.
    std::multiset<char> charMultiset1;

    // Populate the multiset with values.
    charMultiset1.insert('E');
    charMultiset1.insert('D');
    charMultiset1.insert('C');
    charMultiset1.insert('B');
    charMultiset1.insert('A');
    charMultiset1.insert('B');
    charMultiset1.insert('D');

    // Display the contents of the first multiset.
    std::cout << "Contents of first multiset: " << std::endl;
    std::multiset<char>::iterator iter;
    for (iter = charMultiset1.begin();
            iter != charMultiset1.end(); iter++)
        std::cout << *iter << std::endl;
    std::cout << std::endl;

    // Create the second multiset object.
    std::multiset<char> charMultiset2;

    // Populate the multiset with values.
    charMultiset2.insert('J');
    charMultiset2.insert('I');
    charMultiset2.insert('H');
    charMultiset2.insert('G');
    charMultiset2.insert('F');
    charMultiset2.insert('G');
    charMultiset2.insert('I');

    // Display the contents of the second multiset.
    std::cout << "Contents of second multiset: "
        << std::endl;
    for (iter = charMultiset2.begin();
    iter != charMultiset2.end(); iter++)
        std::cout << *iter << std::endl;
    std::cout << std::endl;

    // Compare the sets.
    if (charMultiset1 == charMultiset2)
        std::cout << "set1 == set2";
    else if (charMultiset1 < charMultiset2)
        std::cout << "set1 < set2";
    else if (charMultiset1 > charMultiset2)
        std::cout << "set1 > set2";

    return 0;
}

6、map

#include <iostream>
#include <map>

typedef std::map<int, char> MYMAP;

int main()
{
    // Create the first map object.
    MYMAP charMap1;

    // Populate the first map with values.
    charMap1[1] = 'A';
    charMap1[4] = 'D';
    charMap1[2] = 'B';
    charMap1[5] = 'E';
    charMap1[3] = 'C';

    // Display the contents of the first map.
    std::cout << "Contents of first map: " << std::endl;
    MYMAP::iterator iter;
    for (iter = charMap1.begin();
            iter != charMap1.end(); iter++)
    {
        std::cout << (*iter).first << " --> ";
        std::cout << (*iter).second << std::endl;
    }
    std::cout << std::endl;

    // Create the second map object.
    MYMAP charMap2;

    // Populate the first map with values.
    charMap2[1] = 'F';
    charMap2[4] = 'I';
    charMap2[2] = 'G';
    charMap2[5] = 'J';
    charMap2[3] = 'H';

    // Display the contents of the second map.
    std::cout << "Contents of second map: " << std::endl;
    for (iter = charMap2.begin();
            iter != charMap2.end(); iter++)
    {
        std::cout << (*iter).first << " --> ";
        std::cout << (*iter).second << std::endl;
    }
    std::cout << std::endl;

    // Compare the maps.
    if (charMap1 == charMap2)
        std::cout << "map1 == map2";
    else if (charMap1 < charMap2)
        std::cout << "map1 < map2";
    else if (charMap1 > charMap2)
        std::cout << "map1 > map2";

    return 0;
}

7、multimap

#include <iostream>
#include <map>

typedef std::multimap<int, char> MYMAP;

int main()
{
    // Create the first multimap object.
    MYMAP charMultimap;

    // Populate the multimap with values.
    charMultimap.insert(MYMAP::value_type(1,'A'));
    charMultimap.insert(MYMAP::value_type(4,'C'));
    charMultimap.insert(MYMAP::value_type(2,'B'));
    charMultimap.insert(MYMAP::value_type(7,'E'));
    charMultimap.insert(MYMAP::value_type(5,'D'));
    charMultimap.insert(MYMAP::value_type(3,'B'));
    charMultimap.insert(MYMAP::value_type(6,'D'));

    // Display the contents of the first multimap.
    std::cout << "Contents of first multimap: " << std::endl;
    MYMAP::iterator iter;
    for (iter = charMultimap.begin();
            iter != charMultimap.end(); iter++)
    {
        std::cout << (*iter).first << " --> ";
        std::cout << (*iter).second << std::endl;
    }
    std::cout << std::endl;

    // Create the second multimap object.
    MYMAP charMultimap2;

    // Populate the second multimap with values.
    charMultimap2.insert(MYMAP::value_type(1,'C'));
    charMultimap2.insert(MYMAP::value_type(4,'F'));
    charMultimap2.insert(MYMAP::value_type(2,'D'));
    charMultimap2.insert(MYMAP::value_type(7,'E'));
    charMultimap2.insert(MYMAP::value_type(5,'F'));
    charMultimap2.insert(MYMAP::value_type(3,'E'));
    charMultimap2.insert(MYMAP::value_type(6,'G'));

    // Display the contents of the second multimap.
    std::cout << "Contents of second multimap: " << std::endl;
    for (iter = charMultimap2.begin();
            iter != charMultimap2.end(); iter++)
    {
        std::cout << (*iter).first << " --> ";
        std::cout << (*iter).second << std::endl;
    }
    std::cout << std::endl;

    // Compare the multimaps.
    if (charMultimap == charMultimap2)
        std::cout << "multimap1 == multimap2";
    else if (charMultimap < charMultimap2)
        std::cout << "multimap1 < multimap2";
    else if (charMultimap > charMultimap2)
        std::cout << "multimap1 > multimap2";

    return 0;
}

8、stack

#include <iostream>
#include <list>
#include <stack>

int main()
{
    std::stack<int, std::list<int> > intStack;

    int x;
    std::cout << "Values pushed onto stack:"
              << std::endl;
    for (x=1; x<11; ++x)
    {
        intStack.push(x*100);
        std::cout << x*100 << std::endl;
    }

    std::cout << "Values popped from stack:"
              << std::endl;
    int size = intStack.size();
    for (x=0; x<size; ++x)
    {
        std::cout << intStack.top() << std::endl;
        intStack.pop();
    }

    return 0;
}

9、queue

#include <iostream>
#include <list>
#include <queue>

int main()
{
    std::queue<int, std::list<int> > intQueue;

    int x;
    std::cout << "Values pushed onto queue:"
              << std::endl;
    for (x=1; x<11; ++x)
    {
        intQueue.push(x*100);
        std::cout << x*100 << std::endl;
    }

    std::cout << "Values removed from queue:"
              << std::endl;
    int size = intQueue.size();
    for (x=0; x<size; ++x)
    {
        std::cout << intQueue.front() << std::endl;
        intQueue.pop();
    }

    return 0;
}

10、priority_queue

#include <iostream>
#include <list>
#include <queue>

int main()
{
    std::priority_queue<int, std::vector<int>,std::greater<int> > intPQueue;
    int x;
    intPQueue.push(400);
    intPQueue.push(100);
    intPQueue.push(500);
    intPQueue.push(300);
    intPQueue.push(200);

    std::cout << "Values removed from priority queue:"
              << std::endl;
    int size = intPQueue.size();
    for (x=0; x<size; ++x)
    {
        std::cout << intPQueue.top() << std::endl;
        intPQueue.pop();
    }

    return 0;
}
时间： 2024-09-15 03:45:02

STL--迭代器（iterator）的相关文章

设计模式之iterator模式到STL中iterator迭代器

设计模式之iterator模式到STL中iterator迭代器 近日看<设计模式:可复用面向对象软件的基础>一书中23种模式中就有iterator迭代模式,且篇幅颇大.机缘巧合.我在分析STL代码结构的时候,同样发现iterator迭代器,且占据相当大的地位. 从设计模式的角度来看iterator模式 ü     意图 提供一种方法顺序访问一个聚合对象中各个元素,而又不需要暴露对象的内部表示.我想GOF 的意图这次说的很明白了,就是我想遍历一个聚合对象.但又隐藏内部实现.该怎么办呢?本模式主要

浅谈c++ stl迭代器失效的问题_C 语言

之前看<C++ Primier>的时候,也解到在顺序型窗口里insert/erase会涉及到迭代器失效的问题,并没有深究.今天写程序的时候遇到了这个问题. 1 莫名其妙的Erase 最初我的程序是酱紫的,别说话,我知道这样是有问题的,可这样是最直观的想法 int arr[]={0,1,2,3,4,5,6,7,8,9,10}; vector<int> a(arr,arr+sizeof(arr)/sizeof(*arr));for (auto it = a.begin(); it !=

C++中const 与 迭代器(iterator) 使用 详解

迭代器(iterator) 是一种指针类型, 也分const指针本身(地址) 和 const指针所指的值, 两种情况; 但是写法和const内置指针有所不同; char * const 相当于 const container<>::iterator; 可以修改指针所指的值, 但不能修改指针的地址; const char * 相当于 container<>::const_iterator; 可以修改指针地址, 但不能修改指针所指的值; 注意代码示例, 两种const和迭代器; 代码:

stl-迭代器模式和STL迭代器

问题描述 迭代器模式和STL迭代器 请问STL迭代器和设计模式中的迭代器之间的异同点,stl迭代器是否使用了迭代器模式? 解决方案 stl迭代器就是设计模式中外部迭代器的一个经典案例.

有关迭代器iterator的java实现的问题

问题描述 有关迭代器iterator的java实现的问题 public Iterator<Item> iterator(){ return new ArrayIterator(); } private class ArrayIterator implements Iterator<Item>{ private int[] random; private int current = 0; //line: 47 random = new int[N]; for(int i = 0; i

迭代器 iterator

迭代器 iterator 反向迭代器 对于反向迭代器it,++it会移动到上一个元素:--it会移动到下一个元素. 虽然颠倒递增和递减运算符的含义可能看起来令人混淆,但这样做可以用算法透明地向前或向后处理容器. const_iterator 迭代器失效 一些删除操作会导致某些迭代器对象失效. 可参见vector的erase()函数. http://blog.csdn.net/chuchus/article/details/23037107

JAVA之旅（十八）——基本数据类型的对象包装类，集合框架，数据结构，Collection，ArrayList,迭代器Iterator，List的使用

JAVA之旅(十八)--基本数据类型的对象包装类,集合框架,数据结构,Collection,ArrayList,迭代器Iterator,List的使用 JAVA把完事万物都定义为对象,而我们想使用数据类型也是可以引用的 一.基本数据类型的对象包装类 左为基本数据类型,又为引用数据类型 byte Byte int Integer long Long boolean Booleab float Float double Double char Character 我们拿Integer来举例子 //整

STL迭代器学习

    STL里面迭代器就像指针一样,有了迭代器我们可以更加方便的进行访问集合里面的元素     下面分别对各个容器进行分析    1 list #include<list> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int main(){ list<int>ls; list<int

STL——迭代器的概念

迭代器是一种抽象的设计概念,现实程序语言中并没有直接对应于这个概念的实物. 1 迭代器设计思维--STL关键所在 不论是泛型思维或STL的实际运用,迭代器都扮演这重要的角色.STL的中心思想在于:将数据容器和算法分开,彼此独立设计,最后再以一贴胶着剂将它们撮合在一起.容器和算法的泛型化,从技术的角度来看是并不困难,C++的class template和function templates可分别达成目标. 以下是容器.算法.迭代器的合作展示,以算法find()为例,它接受两个迭代器和一个"搜索目标

C++中正则表达式(regex) 迭代器(iterator) 详解

正则表达式(regex), 使用boost的regex头文件, 是C++11的新标准, 但是gcc4.8.1并未完全支持, 所以使用boost库; 具体安装: http://blog.csdn.net/caroline_wendy/article/details/17282187 正则表达式的书写规范, 以ECMAScript为例, 使用迭代器可以遍历原字符串, 输出符合要求的所有字符串; 使用prefix()和suffix()方法, 可以输出前一个未匹配的字符串和后一个未匹配的字符串; 正则表