写点什么

迭代器的一些简单理解

  • 2024-05-23
    福建
  • 本文字数:5269 字

    阅读完需:约 17 分钟

使用迭代器最方便的地方就是和算法库结合,对于实现只需要聚焦于算法,而不用过多考虑数据结构的实现。


举一个常见的的例子,std::copy_n 用作于范围元素的复制,适配于各个容器类型,并且演化出了 back_inserter/front_inserter/inserter 这类更上层的迭代器。

// std::vector 的复制std::vector<int> v1{2, 1, 3, 4};
std::vector<int> v2(v1.size() / 2); // 初始化大小为 2std::copy_n(v1.cbegin(), v1.size() / 2, v2.begin()); // 2 1
std::vector<int> v3; // 初始化大小为 0std::copy_n(v1.cbegin(), v1.size() / 2, std::back_inserter(v3)); // 2 1
// std::liststd::list<int> l1{12, 11, 13, 14};std::list<int> l2;std::copy_n(l1.cbegin(), l1.size() / 2, std::back_inserter(l2)); // 12 11
// std::vector -> std::liststd::list<int> l3;std::copy_n(v1.cbegin(), v1.size() / 2, std::back_inserter(l3)); // 2 1
// std::list -> std::vectorstd::vector<int> v4;std::copy_n(l1.cbegin(), l1.size() / 2, std::back_inserter(v4)); // 12 11
复制代码


元素的复制可能不是简单的 memcpy,需要考虑深拷贝的情况,在一些其他的语言中,由于标准库的算法实现的不多,对这种统一接口的约束不强。


比如在 Go 中,几乎都是通过接口进行约束。由于 golang 里面只有类似 memcpy 的 copy,换一个 container/heap 的例子,通过定义了三个接口来实现。

type Interface interface {	// Len is the number of elements in the collection.	Len() int
// Less reports whether the element with index i // must sort before the element with index j. // // If both Less(i, j) and Less(j, i) are false, // then the elements at index i and j are considered equal. // Sort may place equal elements in any order in the final result, // while Stable preserves the original input order of equal elements. // // Less must describe a transitive ordering: // - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well. // - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well. // // Note that floating-point comparison (the < operator on float32 or float64 values) // is not a transitive ordering when not-a-number (NaN) values are involved. // See Float64Slice.Less for a correct implementation for floating-point values. Less(i, j int) bool
// Swap swaps the elements with indexes i and j. Swap(i, j int)}
复制代码


不讨论接口性能,heap 只针对其本身来说这个定义是够用的,足够简单只要实现了三个接口,那么就可以实现一个堆。


Go 的一个问题是在实现这类基础设施上,通用型做的还不够好,一些相同的语义没有抽取出来形成一个接口规范:比如一个简单的 Copy 操作必须通过手动 for 进行赋值。


设计


通过观察 std::copy 的实现(gcc12)来看看迭代器的设计

template <bool _IsMove, bool _IsSimple, typename _Category>struct __copy_move{    template <typename _II, typename _OI>    _GLIBCXX20_CONSTEXPR    static _OI __copy_m(_II __first, _II __last, _OI __result)    {        for (; __first != __last; ++__result, (void)++__first)            *__result = *__first;        return __result;    }};
复制代码


std::copy 的通用实现中,出现的运算符有


  • != 同语义还有 == < <= > >=

  • ++ 同语义还有 -- ++(int) -- --(int)有自增自减说明能够支持算术操作,该语义有 + -结合赋值重载函数再衍生出 += -=

  • * 同语义还有 ->


对于可以随机访问的容器(vector/array)来说,还有 [] 运算符。


迭代器设计为一个类,这样可以通过模版参数来区分不同的类型,见 std::vector 的迭代器 (__normal_iterator) 注释说明

// This iterator adapter is @a normal in the sense that it does not// change the semantics of any of the operators of its iterator// parameter.  Its primary purpose is to convert an iterator that is// not a class, e.g. a pointer, into an iterator that is a class.// The _Container parameter exists solely so that different containers// using this template can instantiate different types, even if the// _Iterator parameter is the same.
复制代码


尽管使用起来和指针非常类似,但是都是这个类提供的重载运算符,所以并不能简单的说成是指针。


对于要广泛使用的迭代器而言,统一其接口是一个很有必要的实现,对于 C++ 而言,**_trait* 是一种通用做法。


在 trait 限定各种类型,包括值,指针,引用等。对于各种容器,内部定义好一个迭代器别名 iterator,这个迭代器需要符合 trait 的语义。

class vector {    typedef T value_type;     // 符合 trait 的别名    typedef XXX xxx_iterator; // 支持的迭代器适配器,比如 reverse_iterator/iterator
iterator begin() {} reverse_iterator rbegin() {}};
复制代码


这样在一些模版类的地方直接使用这些类型别名:

std::iterator_traits<std::vector<char>::iterator>::value_type x = 'x';decltype(v1.begin())::value_type y = 'y';
复制代码


容器都支持迭代器,但是容器类型就有不相同的,std::vector 和 std::map 的最大区别就是连续性。故迭代器同样有类型。有了类型可以通过 SFINAE 来选择不同的实现。


通过统一迭代器的语义,在 C++20 以前,对内部变量封装为 begin/end, 就可以通过 for (auto it = x.begin(); it != x.end; ++it) 来完成遍历的功能。对于算法实现,取值可以通过 *,迭代可以通过 ++/--,配合类似 std::less 提高算法实现的抽象程度了。


实现


iterator_traits 的通用实现如下,只定义了通用别名。

template <typename _Iterator>struct __iterator_traits<    _Iterator, __void_t<typename _Iterator::iterator_category,                        typename _Iterator::value_type,                        typename _Iterator::difference_type,                        typename _Iterator::pointer,                        typename _Iterator::reference>> {    typedef typename _Iterator::iterator_category iterator_category;    typedef typename _Iterator::value_type value_type;    typedef typename _Iterator::difference_type difference_type;    typedef typename _Iterator::pointer pointer;    typedef typename _Iterator::reference reference;};
template <typename _Iterator>struct iterator_traits : public __iterator_traits<_Iterator> {};
复制代码


迭代器的类型在 C++20 之前有 5 种,通过一些高层次的封装来观察其设计

  • reverse_iterator 反转的迭代器适配器

  • back_insert_iterator 容器实现有 push_back 方法的迭代器适配器

  • front_insert_iterator 容器实现有 push_front 方法的迭代器适配器

  • insert_iterator 容器实现有 insert 方法的迭代器适配器


reverse_iterator 顾名思义,对比一般的迭代器操作时反过来的

__normal_iterator &operator++() {    ++_M_current;    return *this;}
reverse_iterator &operator++() { --current; return *this;}
复制代码


后面三个迭代器,观察 = 运算符重载函数的实现,通过调用容器成员函数来新增元素。

back_insert_iterator &operator=(const typename _Container::value_type &__value){    container->push_back(__value);    return *this;}
front_insert_iterator &operator=(const typename _Container::value_type &__value) { container->push_front(__value); return *this;}
insert_iterator &operator=(const typename _Container::value_type &__value) { iter = container->insert(iter, __value); ++iter; return *this;}
复制代码


在容器为空的情况下,可以调用这些辅助迭代器适配器。


容器的迭代器


每个容器都有自身实现的迭代器,不看 const_iterator 这类变种的迭代器,容器实现分别是


  • std::vector 的迭代器类型为 __gnu_cxx::__normal_iterator<pointer, vector>

  • std::list 的迭代器类型为 _List_iterator<_Tp>

  • std::map 的迭代器类型为 _Rb_tree_iterator<value_type>


std::vector


__normal_iterator 是一个比较通用的迭代器实现,包含顺序容器(包括 char*),内部实现为对指针的操作。

reference operator*() const noexcept { return *_M_current; }
__normal_iterator &operator++() noexcept { ++_M_current; return *this;}
复制代码


std::list


list 的特化迭代器实现,运算符可能涉及到链表的遍历动作

reference operator*() const noexcept { return *static_cast<_Node *>(_M_node)->_M_valptr(); }
_Self &operator++() noexcept { _M_node = _M_node->_M_next; return *this;}
复制代码


std::map 迭代器


map 的特化迭代器实现,++ 运算符涉及到红黑树的遍历动作

reference operator*() const noexcept {    return *static_cast<_Link_type>(_M_node)->_M_valptr();}
_Self &operator++() noexcept { _M_node = _Rb_tree_increment(_M_node); return *this;}
复制代码


std::map<std::string, in> 的迭代器类型展开为 _Rb_tree_iterator<pair<const __cxx11::basic_string, int>>,pair 的 first 类型为 const std::string


对于 std::copy 来说,内部的赋值实现为

*__result = *__first;
复制代码


等效于 pair 操作

std::pair<const std::string, int> p1{"lebron", 6};std::pair<const std::string, int> p2 = p1;
// 出现编译错误/usr/include/c++/12/bits/stl_algobase.h:353:23: error: use of deleted function ‘std::pair<const std::__cxx11::basic_string<char>, int>& std::pair<const std::__cxx11::basic_string<char>, int>::operator=(const std::pair<const std::__cxx11::basic_string<char>, int>&)’ 353 | *__result = *__first; | ~~~~~~~~~~^~~~~~~~~~In file included from /usr/include/c++/12/bits/stl_algobase.h:64:/usr/include/c++/12/bits/stl_pair.h:185:12: note: ‘std::pair<const std::__cxx11::basic_string<char>, int>& std::pair<const std::__cxx11::basic_string<char>, int>::operator=(const std::pair<const std::__cxx11::basic_string<char>, int>&)’ is implicitly declared as deleted because ‘std::pair<const std::__cxx11::basic_string<char>, int>’ declares a move constructor or move assignment operator
复制代码


那是因为 std::pair 只实现了两个复制函数,只支持 key/value 的可复制/移动进行限制,默认的复制赋值函数被删除

__pair_base &operator=(const __pair_base &) = delete;
pair &operator=( __conditional_t< __and_<is_copy_assignable<_T1>, is_copy_assignable<_T2>>::value, const pair &, const __nonesuch &> __p) { first = __p.first; second = __p.second; return *this;}
pair &operator=( __conditional_t< __and_<is_move_assignable<_T1>, is_move_assignable<_T2>>::value, pair &&, __nonesuch &&> __p) noexcept(__and_<is_nothrow_move_assignable<_T1>, is_nothrow_move_assignable<_T2>>::value) { first = std::forward<first_type>(__p.first); second = std::forward<second_type>(__p.second); return *this;}
复制代码


要实现 std::map 的复制也很简单,只需要对迭代器使用 std::inserter 进行一下包装即可使用,在 inserter 内部调用 insert 来完成插入。

std::map<std::string, int> m1{{"lebron", 6}, {"tom", 2}};std::map<std::string, int> m2;
// 错误的,first 类型为 const,不可复制// std::copy(m1.begin(), m1.end(), m2.begin());
// 正确操作std::copy(m1.begin(), m1.end(), std::inserter(m2, m2.begin()));
复制代码


总结一下


  1. 在 range 之前,迭代器是 STL 中非常重要的一环,善用基于这些迭代器实现算法/辅助函数可以有效的压缩代码行数。

  2. 多种迭代器可供选择使用 back_inserter 调用 push_back,尾部插入 front_inserter 调用 push_front,首部插入 inserter 调用 insert,关联容器的插入 reverse_iterator 一般容器都实现了 rbegin/rend,实现反转功能

  3. 对于自定义容器,可以实现 iterator_trait 来增强通用性(代码也会增多,所谓软件工程没有银弹)


文章转载自:小胖西瓜

原文链接:https://www.cnblogs.com/shuqin/p/18208138

体验地址:http://www.jnpfsoft.com/?from=infoq

用户头像

还未添加个人签名 2023-06-19 加入

还未添加个人简介

评论

发布
暂无评论
迭代器的一些简单理解_迭代_不在线第一只蜗牛_InfoQ写作社区