05 迭代器

5.1 概述

迭代器是一个类似指针的对象,主要用来访问容器中的元素。迭代器是算法和容器之间的桥梁。

从功能上可以把迭代器划分为5种(从上到下功能依次变小):

  • randon-access - 功能和指针类似,下面四个可以看做是功能受限制的指针

  • bidirectional

  • forward

  • input - 用于访问元素。只能用于singl-pass的算法,即该算法对容器中的元素只能顺序遍历一次。

  • output - 同input,不过用于指定元素

不同的容器支持不同类功能级别的迭代器

容器

支持的迭代器

vector

random-access

list

bidirectional

deque

random-access

map

bidirectional

multimap

bidirectional

set

bidirectional

multiset

bidirectional

stack

不支持迭代器

queue

不支持迭代器

priority-queue

不支持迭代器

下面五种迭代器支持的运算符

access

read

write

iterate

compare

input

->

= *i

++

==, !=

output

*i =

++

forward

->

= *i

*i =

++

==, !=

bidirectional

= *i

*i =

++, --

==, !=

random-access

->, []

= *i

*i =

++, --, +=, -=, +, -

==, !=, >, \<, >=, \<=

一个使用迭代器的例子

#include <iostream>
#include <vector>
using namespace std;
int main()
{
// Declaring a vector
vector<int> v = { 1, 2, 3 };
// 5 1 2 3
v.insert(v.begin(), 5);
// 5 2 3
v.erase(v.begin()+1);
// Accessing the elements using iterators
// Declaring an iterator
vector<int>::iterator i;
for (i = v.begin(); i != v.end(); ++i) {
cout << *i << " ";
}
cout << endl;
return 0;
}

5.2 迭代器的操作函数

begin()

返回容器的起始元素

end()

返回容器末尾元素的后一个元素

advance()

让迭代器增加自定位置。双向迭代器不支持+=, -=, +, -。用了advance()就可以一次增加多个位置

#include <iostream> // std::cout
#include <iterator> // std::advance
#include <list> // std::list
int main () {
std::list<int> mylist;
for (int i=0; i<10; i++) mylist.push_back (i*10);
std::list<int>::iterator it = mylist.begin();
std::advance (it,5);
std::cout << "The sixth element in mylist is: " << *it << '\n'; // 50
return 0;
}

next()

prev()

#include<iostream>
#include<iterator> // for iterators
#include<vector> // for vectors
using namespace std;
int main()
{
vector<int> ar = {0, 1, 2, 3, 4, 5};
vector<int>::iterator ptr = ar.begin() + 2;
cout << "ptr points to " << *ptr << endl;
auto it1 = next(ptr, 2);
auto it2 = prev(ptr, 2);
cout << "prev(ptr, 2) points to " << *it2 << endl; // 0
cout << "next(ptr, 2) points to " << *it1 << endl; // 4
return 0;
}

inserter()

inserter Constructs an insert iterator that inserts new elements into x in successive locations starting at the position pointed by it.

// copy [first, last) to result
template <class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);
template <class Container>
insert_iterator<Container> inserter (Container& x, typename Container::iterator it);
// inserter example
#include <iostream> // std::cout
#include <iterator> // std::front_inserter
#include <list> // std::list
#include <algorithm> // std::copy
int main () {
std::list<int> foo,bar;
for (int i=1; i<=5; i++)
{ foo.push_back(i); bar.push_back(i*10); }
std::list<int>::iterator it = foo.begin();
advance (it,3);
std::copy (bar.begin(),bar.end(),std::inserter(foo,it));
std::cout << "foo contains:";
for ( std::list<int>::iterator it = foo.begin(); it!= foo.end(); ++it )
std::cout << ' ' << *it;
std::cout << '\n';
// 1 2 3 10 20 30 40 50 4 5
return 0;
}

5.3 输入迭代器

用来顺序读取容器中的元素一次。