提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

STL开发之迭代器（Iterator）

容器 迭代 代码
2023-03-20 14:44:28 时间

C++在操作容器时更加推荐使用迭代器进行操作，C++标准库为每一种标准容器都定义了一种迭代器类型同时也支持了对部分容器使用下标进行访问。

1 迭代器定义

C++标准委员会对迭代器的定义为：指向元素范围(如数组或容器)中的某个元素，并能够使用一组操作符(至少使用自增(++)和解引用(*)操作符)遍历该范围中的元素的任何对象。

指针是最常见的一种迭代器，指针可以指向数组中的元素并使用自增运算符遍进行遍历，除了数组外，也可以使用迭代器对向量、列表、集合的等容器进行遍历。需要注意的是虽然指针是迭代器的一种形式，但并非所有迭代器都具有指针的相同功能。

2 迭代器类型

迭代器按照实现功能可以划分为5种，主要包含：

  • 输入/输出迭代器：可以顺序执行单次输入或者输出
  • 前项迭代器：具备输入迭代器的所有功能，如果没有定义成常量其还具有输出迭代器的功能。
  • 双向迭代器：既具备前项迭代器的功能，也具备后项遍历的功能。
  • 随机访问迭代器：顾名思义，除了具备所有双向迭代器的功能外，还可以通过偏移随机访问指向的元素。

3 迭代器的使用方式

按照迭代器的使用方式，迭代器可以分为以下四种，如：

  • 正向迭代器：定义方式为：容器名::iterator,也是最常使用的迭代器类型，代码如下： 
#include <iostream>
#include <vector>
int main ()
{
  std::vector<int> myvector;
  for (int i=1; i<=5; i++) myvector.push_back(i);
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it = myvector.begin() ; it != myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '
';
  return 0;
}

上面的代码通过容器的begin和eng方法将容器开始和结束位置赋值给了迭代器变量，通过迭代器的自增运算达到遍历整个容器的目的。

  • 常量正向迭代器：定义方式为：容器名::const_iterator。不可改变指向的元素的值。
int main ()
{
  std::vector<int> myvector;
  for (int i=1; i<=5; i++) myvector.push_back(i);
  std::cout << "myvector contains:";
  for (std::vector<int>::const_iterator it = myvector.begin() ; it != myvector.end(); ++it)
  {
        *it = 12121;
        std::cout << ' ' << *it;
  }
  std::cout << '
';
  return 0;
}

对正向迭代器的代码略作修改就可以改成常量迭代器使用实例，如代码所示，定义时将迭代器类型定义成常量，这时如果在循环体中修改迭代器的值，编译时将会报错，如下所示：

In function 'int main()':
13:13: error: assignment of read-only location 'it.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator*<const int*, std::vector<int> >()'
  • 反向迭代器：定义方式为：容器名::reverse_iterator。使用反向迭代器可以反向遍历容器，如代码所示：
int main ()
{
  std::vector<int> myvector (5);
  int i=0;
  std::vector<int>::reverse_iterator rit = myvector.rbegin();
  for (; rit!= myvector.rend(); ++rit)
    *rit = ++i;
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '
';
  return 0;
}

上面的代码通过vector的反向迭代器向vector中插入了5个元素，然后又通过正向迭代器遍历容器元素并输出，运行结果如下： 

myvector contains: 5 4 3 2 1

从结果可知，通过反向迭代器向插入元素元素和插入顺序是方向的，当然也可以通过反向迭代器遍历容器元素。

  • 常量反向迭代器：定义方式为：容器名::const_reverse_iterator下面的例子就通过常量反向迭代器遍历容器中的元素。
int main ()
{
  std::vector<int> myvector (5);  // 5 default-constructed ints
  int i=0;
  std::vector<int>::reverse_iterator rit = myvector.rbegin();
  for (; rit!= myvector.rend(); ++rit)
    *rit = ++i;
  std::cout << "myvector contains:";
  for (std::vector<int>::const_reverse_iterator it = myvector.rbegin(); it != myvector.rend(); ++it)
    std::cout << ' ' << *it;
  std::cout << '
';
  return 0;
}

代码运行结果为：

myvector contains: 1 2 3 4 5

从结果可以看出，反向插入和反向遍历后输出结果和元素插入顺序一致。

4 迭代器失效

迭代器失效可以分成两种情况，如序列容器的迭代器失效和关联容器的迭代器失效。

  • 序列容器迭代器失效，以vector为例。看如下代码：
int main ()
{
  std::vector<int> myvector (5);  // 5 default-constructed ints
  int i=0;
  std::vector<int>::reverse_iterator rit = myvector.rbegin();
  for (; rit!= myvector.rend(); ++rit)
    *rit = ++i;

  std::cout << "myvector contains:";
  std::vector<int>::iterator it;
  for (it = myvector.begin(); it != myvector.end(); ++it)
  {
       if(*it>3) myvector.erase(it);
  }
  for (it = myvector.begin(); it != myvector.end(); ++it)
  {
       std::cout<<*it<<" ";
  }
  std::cout << '
';
  return 0;
}

这里继续沿用上面的代码，在遍历vector时，删除大于3的元素，我们期望的最后输出结果为：3 2 1。运行后代码输出结果见下图：

产生这种情况的原因是：vector第一次删除满足条件的元素后，迭代器失效导致，因为vector是序列容器，删除元素后后面的元素会向前移动，导致后续的迭代器失效。如果要解决这个问题只要在删除前先将迭代器进行自加或者获取erase返回的迭代器既可。如代码所示：

for (it = myvector.begin(); it != myvector.end();)
  {
       if(*it>3) it = myvector.erase(it);
       else  ++it;
  }

这样就可以得到我们想要的结果。

  • 关联式容器迭代器失效：以map容器为例，删除关联容器的迭代器指针时，当前迭代器将失效，如果要想继续遍历迭代器，只要删除时将迭代器自增。见如下代码：
int main ()
{
  std::map<int,int> mymap;
  std::map<int,int>::iterator it;
  // insert some values:
  mymap[1]=10;
  mymap[2]=20;
  mymap[3]=30;
  mymap[4]=40;
  mymap[5]=50;
  mymap[6]=60;
  // show content:
  for (it=mymap.begin(); it!=mymap.end();it++)
  {
      if(it->first % 2 == 0) 
      {
          mymap.erase(it++);
      } 
  }
  for (it=mymap.begin(); it!=mymap.end();it++)
  {
      std::cout << it->first << " => " << it->second << '
';
  }
  return 0;
}

如上代码所示，可以解决map迭代器失效的问问题。

5 C++11新增方法

  • std::begin()/end()返回容器中的首元素和末尾元素，此功能和容器的begin、end方法一致
int main () {
  int foo[] = {10,20,30,40,50};
  std::vector<int> bar;
  // iterate foo: inserting into bar
  for (auto it = std::begin(foo); it!=std::end(foo); ++it)
    bar.push_back(*it);
  // iterate bar: print contents:
  std::cout << "bar contains:";
  for (auto it = std::begin(bar); it!=std::end(bar); ++it)
    std::cout << ' ' << *it;
  std::cout << '
';
  return 0;
}
  • std::prev()/next()移动迭代器到指定的位置
int main () {
  std::list<int> mylist;
  for (int i=0; i<10; i++) mylist.push_back (i*10);
  std::list<int>::iterator it= mylist.end();
  std::cout << "The last element is " << *std::prev(it) << '
';
  std::cout << "The fifth element is " << *std::prev(it,-5) << '
';
  return 0;
}

输出结果为：

The last element is 90
The fifth element is 40

6 总结

本文只做抛转引用，如果书写有什么错误欢迎在下方留言，谢谢！

参考：http://www.cplusplus.com/reference/iterator/

- EOF -

相关文章