骗分过样例,暴力出奇迹

C++ 迭代器,了解一下?

2018-08-11 17:32:56


由于作者是个C++鶸,如果本文有任何错误,烦请不吝指出。(有的地方已知描述是不完整的,但是与指针行为一致,或鉴于多数看这篇文章的都是算法竞赛选手,抑或考虑实际,刻意忽略掉辣)

迭代器是个啥?

迭代器(Iterator):一种“能够迭代某序列内所有元素”的对象

指针都知道吧?不知道的先出门左转了解一下

迭代器:指针的抽象,指针是迭代器的子集

#include <iterator>

迭代器能干啥?

所有迭代器都能做的操作:

int main(){
    /*
    * suppose:
    * T t;
    * container<T> v1{t}, v2;
    * container<T>::iterator
    * container<T>::begin()
    * container<T>::end()
    * have been defined here
    */
    container<T>::iterator ita = v1.begin(), itb = v2.begin();
    *ita;
    using std::swap;
    swap(ita, itb);
    ++ita;
}

emmmm...这些跟指针没什么差别对吧。

思考熊真的没差别吗?

其实是有的...

指针不可能随便解引用或者交换一下,甚至你什么都没做,就非法化了对吧。但是就“迭代器”本身,不加任何限制的情况下,其只是一个可以做上述操作的类而已啦,随时有可能被非法化。

*it返回什么是未指定的,返回void也合fa♂ 三去法,意味着在这里你可能什么也做不了2333333

捂脸熊那我咬着要这迭代器有何用?

别急别急,迭代器还是有几个定义好的分类的,标准库内的迭代器何时会非法化也有严格限制。

在说这个之前,先提一嘴迭代器的一个辅助类型std::iterator_traits,其一般化定义是长这个样子滴:

template< class Iterator >
struct iterator_traits {
    typedef typename Iterator::difference_type difference_type;
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference reference;
    typedef typename Iterator::iterator_category iterator_category;
};

很简单对吧,直接从迭代器类型本身拿来了这几个成员,标准库提供了对于指针的特化,毕竟指针没有这些成员。

只有使std::iterator_traits<T>合法且含有上述五个成员,且能执行前面列出的那些迭代器操作的T类型才满足迭代器概念。

什么?你问我这五个鬼东西干啥用的?把他们翻译成中文就好了 ←真的如此,STL的命名还是挺清楚的哇

其中标准库自带了五个用于iterator_category的空类型,分别对应下方的前五种迭代器:

struct output_iterator_tag { };
struct input_iterator_tag { };
struct forward_iterator_tag : public input_iterator_tag { };
struct bidirectional_iterator_tag : public forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };

迭代器分类

  • 输出迭代器(OutputIterator)
  • 输入迭代器(InputIterator)
  • 向前迭代器(ForwardIterator)
  • 双向迭代器(BidirectionalIterator)
  • 随机访问迭代器(RandomAccessIterator)
  • 相接迭代器(ContiguousIterator)

  • 可变迭代器(MutableIterator)

迭代器分类的依据是其可以进行的操作

鼓掌熊由上至下越来越像指针,越来越正常

输出迭代器

typedef output_iterator_tag iterator_category;
可自增(前置/后置、无操作)
operator*解引用(空操作)

返回的还是这个迭代器本身,所以不要做出a = *it这种操作,伦家明明是输出迭代器不要把窝搞成输入嘛~

实际上这个不是输出迭代器标准定义,但是STL中输出迭代器的实例就是这样的

仅资瓷单趟算法

啥是单趟算法?只需要遍历这个序列一次的算法,不需要把当前位置迭代器记存一个副本,等以后再使用。

因为该序列上同一时间可能只有一个位置的迭代器是合法的

输出迭代器这个名字看起来就是用于输出内容的,STL有两个小玩意叫做std::ostream_iteratorstd::ostreambuf_iterator,把输出流包装了一下

// 构造一个输出T类型的输出迭代器
// 第一个参数为绑定到的流
// 第二个参数为每次输出后输出的字符串,可省
std::ostream_iterator<T> it(std::cout, " ");
T t;
it = t; //这些都等同于 std::cout << t << " "
*it = t;
it++ = t;
++it = t;
*it++ = t;

// 跟上面那个一样,不过变成输出字符类型,也没有第二个参数了
std::ostreambuf_iterator<char> it(std::cout);

it = 'A'; // 等同于 std::cout << 'A'
*it = 'A';
...

STL还有几个用于插入序列的迭代器适配器,以及配套的为了方便的函数模板

std::deque<int> q;

std::back_insert_iterator< std::deque<int> > it1(q);
// 等同于 auto it1 = std::back_inserter(q);
it1 = 1; // 等同于 q.push_back(1)
*it1 = 1;
...

std::front_insert_iterator< std::deque<int> > it2(q);
// 等同于 auto it2 = std::front_inserter(q);
it2 = 1; // 等同于 q.push_front(1)
*it2 = 1;
...

std::insert_iterator< std::deque<int> > it3(q, q.begin());
// 等同于 auto it3 = std::inserter(q);
it3 = 1; // 等同于 q.insert(q.begin(), 1)
*it3 = 1;
...

输入迭代器

这玩意从名字看上去就与上面那个有许多相似之处,实际上也是

typedef input_iterator_tag iterator_category;
可后置自增
可默认构造

实际上输入迭代器标准定义不可默认构造,向前迭代器才可以,但是STL中输入迭代器的实例都是可以的

operator*返回reference,为可转换为value_type的引用

可以读取啦,但是不一定可以写入,因为返回的引用可能是const的(下面的输入流迭代器就如此)

为什么是“可转换为value_type的引用”呢?

std::vector<bool>为了节约空间,每一个 $01$ 位占一个bit而非一个byte,但是没有办法返回一个bit的对象,只能返回一个包装好的代理类辣,所以std::vector<bool>::iterator::reference是代理类的引用而非位引用或bool&

PS:std::vector<bool>不是容器,不满足容器的要求,下文提到std::vector时均不包含std::vector<bool>

C++真是一门难学的语言

可比较相等和不等
operator*返回当前元素
可使用operator->访问成员
仅资瓷单趟算法

把输出迭代器的栗子的输出改成输入就好了

emmmmm...等等,那EOF咋判断?思考熊

默认构造的输入流迭代器就代表EOF,判一下相等/不等就好了

std::vector<int> v;
std::istream_iterator<int> i1(std::cin), i2;
while(i1 != i2) v.push_back(*i1++);

同一个位置的元素可以读多次,不过不能倒回来读

std::istream_iterator<int> i1(std::cin);
int a = *i1, b = *i1, c = *++i1, d = *i1++; // 前提未EOF

std::istreambuf_iterator同理,只不过读入的变成了字符

那这个输入/输出迭代器比直接用std::cin/cout还麻烦啊!!!有啥用啊!!!

别急着骂我,主要是配合各种STL函数食用的

众所周知,std::vector有这样一个构造函数,接收一对迭代器,将 $[begin,end)$ 范围内元素拷贝入容器(std::vector<>::assign()也是)

所以上面的代码可以改写成这样

std::vector<int> v{std::istream_iterator<int>(std::cin), std::istream_iterator<int>()};

一行结束,简单多了对吧。输出的也同理

别问我这个在算法竞赛中的应用是什么,我知道你们都不会在比赛中用流式输入输出的,但是这些都是C++这门语言的重要组成部分,毕竟C++不是只用来算法竞赛的对吧


向前迭代器

终于到比较正常的用的比较多的了

typedef forward_iterator_tag iterator_category;
是输入迭代器
reference为引用
提供多趟保证

可以放心地把迭代器存起来辣

不会因为解引用并赋值导致迭代器非法化

自增it的副本不改变解引用it得到的值

保证若ita == itb

  • 要么二者都不可解引用,要么指向同一对象
  • ++ita == ++itb

可以看成不可自减和随机访问的指针

std::forward_list和无序关联容器(哈希容器)的iterator


双向迭代器

typedef bidirectional_iterator_tag iterator_category;
是向前迭代器
可自减

行为与自增都类似

可以看成不可随机访问的指针

std::list和有序关联容器的iterator


随机访问迭代器

typedef random_access_iterator_tag iterator_category;
是向前迭代器
可以在常量时间内移动任意位置
可以做加减法
可以比较大小
可以使用operator[]

指向数组元素的指针会用吧?一样的

std::vector, std::array, std::deque, std::stringiterator、指向数组元素的指针


相接迭代器

是迭代器
其所指向的逻辑相邻元素也在内存中物理上相邻

任意合法的*(a + n)等价于*(std::addressof(*a) + n)


顺便提一句,为什么是std::addressof(*a)而不是&(*a)

因为operator&是可以重载的...它可以返回任何奇怪的东西

所以C++11引入了std::addressof函数,专门用于返回一个对象的地址,其实现用了一些小trick,C++11及之后所有的标准库实现取地址用的都是这个函数而不是operator&

那么问题来了,如何在C++11之前将一个重载了operator&的类放入标准库容器呢?

C++真是一门难学的语言


std::vector, std::array, std::basic_string_viewiterator、指向数组元素的指针


可变迭代器

是输入迭代器
是输出迭代器

也就是可以读也可以写的

所有STL容器的iteratorconst_iterator除外)、指针(常量指针除外)

类型总结

来源cppreference

相对用的比较多的迭代器适配器

std::reverse_iterator

反向迭代器,原迭代器+变-、-变+,提供原迭代器提供的所有功能

STL容器的rbegin(), rend()返回的就是这个

std::move_iterator

原迭代器需至少为输入迭代器,其reference为右值引用

关于std::move和右值引用...那应该是另一篇文章的内容了

迭代器非法化

See https://zh.cppreference.com/w/cpp/container#.E8.BF.AD.E4.BB.A3.E5.99.A8.E9.9D.9E.E6.B3.95.E5.8C.96

适配器均取决于其底层容器

(溜了溜了)

emmmm...还是说几个常见的吧

所有只读操作无


std::vector扩大重分配、std::deque插入+扩大重分配+非首尾擦除:全部

std::vector插入/擦除(无重分配):插入位置及其后

std::deque首尾擦除(无重分配):首尾


链表+有序关联容器:插入无,擦除仅被擦除元素

(毕竟它们是节点形式出现的)


哈希容器:

插入导致重哈希:全部

插入未导致重哈希:无

擦除:仅被擦除元素

一点废话

在不需要返回值的情况下尽可能使用前置递增/递减,而非后置

后置比前置慢

这个对于内置类型是假的,开不开优化都一样

但是对于非内置类型就不一定了

像迭代器这种实现相对比较简单的类(绝大部分容器的迭代器底层都只是一个或几个指针),开了优化可能会被优化成一样

但是如果是复杂一点的就不一定了2333333

小建议:(求不喜勿喷)干脆全改成前置好了,反正不会慢对吧,要不然写的时候还要想一下是不是内置类型,也挺麻烦的

使用std::array而非原生数组

窝个人觉得,OOP的封装性的优势在这体现地淋漓尽致,不用管底层怎么搞的,用就好辣

其成员函数什么的都是STL的命名格式,会用一个STL容器就会用其他的_(:з」∠)_

一维数组还好办,二维及以上的话指针、sizeof什么的比封装好的麻烦多了(表喷窝TAT,再熟练也改变不了它麻烦的事实呀)

常数这个无需担心,std::array只是把原生数组封装了一下,效率没有任何差别,成员函数都是内联的鼓掌熊

然鹅...这个东西是C++11才有的,C++98的话也可以自己封装一下嘛,几分钟就写完了(逃)

参考资料

ISO/IEC 14882:2017 Programming languages -- C++:952-986.

cppreference.com.

(德)约祖蒂斯(Josuttis,N.M.)著;侯捷译.C++标准库:第2版[M].北京:电子工业出版社,2015.6:433-474.