精华内容
下载资源
问答
  • 迭代器分类

    2020-11-30 16:08:44
    迭代器分类 迭代器 能力 提供 output迭代器 向前输出 Ostream、inserter input迭代器 向前输入 Istream forward迭代器 向前输入输出 forward list、unordered containers bidirectional迭代器 向前、...

    迭代器分类

    迭代器 能力 提供
    output迭代器 向前输出 Ostream、inserter
    input迭代器 向前输入 Istream
    forward迭代器 向前输入输出 forward list、unordered containers
    bidirectional迭代器 向前、向后输入输出 list、set、multiset、map、multimap
    random-access迭代器 随机输入输出 array、vector、deque、string

    纯粹的 output 迭代器只有 ostream 和 inserter,而纯粹的 input 迭代器只有 istream,其他迭代器既是 output 迭代器,也是 input 迭代器。output迭代器只能用于往迭代器指向的位置写入数据,input迭代器能用不读取迭代器指向位置的数据。

    1、output迭代器支持操作:

    操作 作用
    operator* 返回迭代器引用
    operator++ 返回迭代器引用
    operator= 输出数据
    ostream_iterator<string> writer(cout, "\n");
    // 使用方法1
    *writer = "hello";
    ++writer;
    *writer = "world";
    // 使用方法2
    writer = "hello";
    writer = "world";
    

    代码以ostream_iterator为例,代码中两种方法的效果一样,inster_iterator也可以得到相同结果。实际对于 output迭代器,operator* 和 operator++ 没有执行任何操作。

    2、input迭代器支持操作

    操作 作用
    operator* 读取元素
    operator-> 访问元素成员
    operator++ 向前移动迭代器
    operator==、!= 比较迭代器
    展开全文
  • 什么是 std::random_access_iterator_tag 还有哪些迭代器分类标签 stl中如何针对不同迭代器做算法选择


    不同编译器实现代码可能不完全一样,本文中代码均来自msvc.

    迭代器分类标签 std::random_access_iterator_tag

    随机存取标签,如下代码,这是一个空结构体,什么也不做,仅用来标识随机存取迭代器,除随机存取标识外还有其他类别的标识。

    struct random_access_iterator_tag : bidirectional_iterator_tag {};
    

    用途

    这个标签有什么用呢? 不用可不可以?
    迭代器分类标签用来进行编译期间的算法选择。这有两层意思:

    1. 这个标签用来做针对迭代器的算法选择
    2. 算法选择发生在编译阶段

    常用迭代器分类标签

    首先认识一下常用容器的迭代器的分类标签,

    vector struct std::random_access_iterator_tag
    list struct std::bidirectional_iterator_tag
    deque struct std::random_access_iterator_tag
    array struct std::random_access_iterator_tag
    map struct std::bidirectional_iterator_tag
    unordered_map struct std::bidirectional_iterator_tag
    set struct std::bidirectional_iterator_tag
    unordered_set struct std::bidirectional_iterator_tag

    获取代码如下,

    #include <iterator>
    #include <vector>
    #include <stdio.h>
    #include <list>
    #include <deque>
    #include <array>
    #include <map>
    #include <set>
    #include <unordered_map>
    #include <unordered_set>
    
    using namespace std;
    
    int main()
    {
       iterator_traits<vector<int>::iterator>::iterator_category cati;
       iterator_traits<list<char>::iterator>::iterator_category catlc;
       iterator_traits<deque<int>::iterator>::iterator_category catqi;
       iterator_traits<array<int,5>::iterator>::iterator_category catai;
       iterator_traits<map<int, int>::iterator>::iterator_category catmii;
       iterator_traits<unordered_map<int,int>::iterator>::iterator_category catumii;
       iterator_traits<set<int, int>::iterator>::iterator_category catsii;
       iterator_traits<unordered_set<int, int>::iterator>::iterator_category catusii;
    
       printf("vector|%s\n", typeid (cati).name());
       printf("list|%s\n", typeid (catlc).name());
       printf("deque|%s\n", typeid (catqi).name());
       printf("array|%s\n", typeid (catai).name());
       printf("map|%s\n", typeid (catmii).name());
       printf("unordered_map|%s\n", typeid (catumii).name());
       printf("set|%s\n", typeid (catsii).name());
       printf("unordered_set|%s\n", typeid (catusii).name());
      
       return 0;
    }
    

    算法选择

    然后我们看一下一个算法选择的例子,以std::distance为例子,distance用于获取从first到last的“行程”。

    template< class InputIt >
    typename std::iterator_traits<InputIt>::difference_type
        distance( InputIt first, InputIt last );
    

    我们知道对于vector或者数组这样的随机存取容器,获取两个位置之间的行程非常简单,且时间复杂度为常数,因为元素是
    连续存储的。而对于list和map等容器,行程的获取就略加复杂。因此我们希望针对不同容器可以有不同的求解算法,以下是代码实现:

    template <class _InIt>
    _NODISCARD _CONSTEXPR17 _Iter_diff_t<_InIt> distance(_InIt _First, _InIt _Last) {
        if constexpr (_Is_random_iter_v<_InIt>) {
            return _Last - _First; // assume the iterator will do debug checking
        } else {
            _Adl_verify_range(_First, _Last);
            auto _UFirst             = _Get_unwrapped(_First);
            const auto _ULast        = _Get_unwrapped(_Last);
            _Iter_diff_t<_InIt> _Off = 0;
            for (; _UFirst != _ULast; ++_UFirst) {
                ++_Off;
            }
    
            return _Off;
        }
    }
    

    从上边的代码可以看出,对于随机存取容器return _Last - _First;这一条表达式就可以了,而对于其他容器则需要一个一个的查找对比。

    怎么将选择实现在编译阶段

    编译阶段的算法选取通过if constexpr表达式实现,与普通的if else想比,后者的判断发生在程序执行阶段,而前者的判断发生在
    编译阶段。

    编译期间算法选择的另外一种方式

    if constexpr语句是c++17之后出现的新特性,在此之前使用如下方式实现同样功能。

    template <class _InIt>
    _CONSTEXPR17 _Iter_diff_t<_InIt> _Distance1(_InIt _First, _InIt _Last, input_iterator_tag) {
        // return distance between iterators; input
        _Adl_verify_range(_First, _Last);
        auto _UFirst             = _Get_unwrapped(_First);
        const auto _ULast        = _Get_unwrapped(_Last);
        _Iter_diff_t<_InIt> _Off = 0;
        for (; _UFirst != _ULast; ++_UFirst) {
            ++_Off;
        }
    
        return _Off;
    }
    
    template <class _RanIt>
    _CONSTEXPR17 _Iter_diff_t<_RanIt> _Distance1(_RanIt _First, _RanIt _Last, random_access_iterator_tag) {
        // return distance between iterators; random-access
        return _Last - _First;
    }
    
    template <class _InIt>
    _NODISCARD _CONSTEXPR17 _Iter_diff_t<_InIt> distance(_InIt _First, _InIt _Last) {
        return _Distance1(_First, _Last, _Iter_cat_t<_InIt>());
    }
    

    另外可以看到,msvc中通过宏_HAS_IF_CONSTEXPR来分割了两种方法

    // FUNCTION TEMPLATE distance
    #if _HAS_IF_CONSTEXPR
    #else // ^^^ _HAS_IF_CONSTEXPR / !_HAS_IF_CONSTEXPR vvv
    
    #endif // _HAS_IF_CONSTEXPR
    
    
    展开全文
  • C++迭代器分类

    2011-11-27 22:07:54
    C++按照提供的操作集分为5类: 1. 输入迭代器 顾名思义,只能读取此迭代器指向的元素,却不能给这种迭代器...用于读写容器,这类迭代器只会以一个方向遍历序列,前向迭代器支持输入迭代器和输出迭代器提供的所有操作

    C++按照提供的操作集分为5类:

    1. 输入迭代器

    顾名思义,只能读取此迭代器指向的元素,却不能给这种迭代器赋予新的值

    支持的操作符:

     ++,-> ==  != *

    2.输出迭代器

    顾名思义,向容器写入元素,但是不保证能支持读取容器内容,

    支持操作符:

    ++ *

    3.前向迭代器

    用于读写容器,这类迭代器只会以一个方向遍历序列,前向迭代器支持输入迭代器和输出迭代器提供的所有操作,除此之外,还支持对同一个元素的多次读写

    支持的操作符,++,*  -> . ==  !=

    4.双向迭代器

    双下迭代器顾名思义,与前向迭代器功能相似,只是比前向多了一个向后遍历的功能,即提供 --操作符

    5.随机访问迭代器

    随机访问支持更多的操作符,使得迭代器功能更加丰富,

    支持的操作符,除了双向迭代器中支持的操作符外,还支持

     

    < <= > >= + += - -=

    还有最重要的下标操作符
    展开全文
  • 五类迭代器如下: 1、输入迭代器:只读,一次传送 为输入迭代器预定义完成只要istream_iterator和istreambuf_iterator,用于从一个输入流istream中读取。一个输入迭代器仅能对它所选择的每个元素停止一次解析,它们...

    五类迭代器如下:

    1、输入迭代器:只读,一次传送
    为输入迭代器预定义完成只要istream_iterator和istreambuf_iterator,用于从一个输入流istream中读取。一个输入迭代器仅能对它所选择的每个元素停止一次解析,它们只能向前挪动。一个特地的结构函数定义了超越末尾的值。总是,输入迭代器能够对读操作的结果停止解析(对每个值仅解析一次),然后向前挪动。
    2、输出迭代器:只写,一次传送
    这是对输入迭代器的补充,不过是写操作而不是读操作。为输出迭代器的预定义完成只要ostream_iterator和ostreambuf_iterator,用于向一个输出流ostream写数据,还有一个普通较少运用的raw_storage_iterator。他们只能对每个写出的值停止一次解析,并且只能向前挪动。关于输出迭代器来说,没有运用超越末尾的值来完毕的概念。总之,输出迭代器能够对写操作的值停止解析(对每一个值仅解析一次),然后向前挪动。
    3、前向迭代器:屡次读/写
    前向迭代器包含了输入和输出迭代器两者的功用,加上还能够屡次解析一个迭代器指定的位置,因而能够对一个值停止屡次读/写。望文生义,前向迭代器只能向前挪动。没有为前向迭代器预定义迭代器。
    4、双向迭代器:operator–
    双向迭代用具有前向迭代器的全部功用。另外它还能够应用自减操作符operator–向后一次挪动一个位置。由list容器中返回的迭代器都是双向的。
    5、随机访问迭代器:相似于一个指针
    随机访问迭代用具有双向迭代器的一切功用,再加上一个指针一切的功用(一个指针就是一个随机访问迭代器),除了没有一种“空(null)”迭代器和空指针对应。根本上能够这样说,一个随机访问迭代器就像一个指针那样能够停止任何操作,包括运用操作符operator[]停止索引,加某个数值到一个指针就能够向前或者向后挪动若干个位置,或者运用比拟运算符在迭代器之间停止比拟。

    迭代器类别

    阐明

    输入迭代器

    沉着器中读取元素。输入迭代器只能一次读入一个元素向前挪动,输入迭代器只支持一遍算法,同一个输入迭代器不能两遍遍历一个序列

    输出迭代器

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

    正向迭代器

    组合输入迭代器和输出迭代器的功用,并保存在容器中的位置

    双向迭代器

    组合正向迭代器和逆向迭代器的功用,支持多遍算法

    随机访问迭代器

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

    迭代器的操作:

    每种迭代器均可停止包括表中前一种迭代器可停止的操作。迭代器的操作实质上是经过重载运算符来完成的,迭代器支持何种操作和可以执行什么运算是由迭代器所重载的运算符来决议的。

    迭代器类型 操作类型 阐明
    一切迭代器

    p++

    ++p

    后置自增迭代器

    前置自增迭代器s’s

    输入迭代器

    *p

    p=p1

    p==p1

    p!=p1

    复援用迭代器,作为右值

    将一个迭代器赋给另一个迭代器

    比拟迭代器的相等性

    比拟迭代器的不等性

    输出迭代器

    *p

    p=p1

    复援用迭代器,作为左值

    将一个迭代器赋给另一个迭代器

    正向迭代器

    提供输入输出迭代器的一切功用

    双向迭代器

    –p

    p–

    前置自减迭代器

    后置自减迭代器

    随机访问迭代器

    p+=i

    p-=i

    p+i

    p-i

    p[i]

    p<p1

    p<=p1

    p>p1

    p>=p1

    将迭代器递增i位

    将迭代器递加i位

    在p位加i位后的迭代器

    在p位减i位后的迭代器

    返回p位元素偏离i位的元素援用

    假如迭代器p的位置在p1前,返回true,否则返回false

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

    假如迭代器p的位置在p1后,返回true,否则返回false

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

    只要次第容器和关联容器支持迭代器遍历,各容器支持的迭代器的类别如下:

    容器

    支持的迭代器类别

    vector

    随机访问

    deque

    随机访问

    list

    双向

    set

    双向

    multiset

    双向

    map

    双向

    multimap

    双向

    stack

    不支持

    queue

    不支持

    priority_queue

    不支持

    展开全文
  • STL::iterator迭代器分类

    2019-03-17 09:03:00
    1. 输入迭代器:只读,一次传递 为输入迭代器预定义实现只有istream_iterator和istreambuf_iterator,用于从一个输入流istream中读取。一个输入迭代器仅能对它所选择的每个元素进行一次解析,它们只能向前移动。一个...
  • C++标准库算法入门 概念:STL六大部件,算法就是模版函数,很独特,标准库的样子如下图右下角那两框...迭代器分类 迭代器移动规则:array/vector(双端队列)/链表:list(双向)、forward_list(单向)/红黑树:s...
  • STL中的算法是独立于容器的,但是它可以通过迭代器iterators对容器进行操作,当容器的迭代器能回答算法的提问时,该容器才能搭配算法的所有操作。而从语言层面上说,算法Algorithm,是一个函数模板function template...
  • input迭代器:只能向前移动,一次一步,用户只能读取,不能修改它们所指向的东西,而且只能读取一次。 output迭代器情况类似,但一切只为输出:它们只能向前移动,一次一步,用户只可以修改它们所指向的东西,而且...
  • c++ STL提供了多种迭代器种类,并且居然有继承关系,它用于告诉算法对于指定容器作指定的迭代器操作。 一、cppreference中对Iterator category的描述 二、迭代器支持的操作以及各容器所含迭代器种类 ...
  • C++ 迭代器Iterator 和指针类似,可以用来遍历容器, 例如: #include #include using namespace std; int main() { // Declaring a vector vector<int> v = { 1, 2, 3 }; // Declaring an iterator vector<int>::...
  • 文章目录0 - 前言1 - 迭代器定义2 - 迭代器分类3 - 迭代器使用 0 - 前言 参考:http://c.biancheng.net/view/6675.html 1 - 迭代器定义 每一种容器都有对应类型的迭代器,也就是,不同容器的迭代器也不同,其功能...
  • 迭代器

    2017-12-17 17:02:53
    迭代器 分类 输入迭代器input iterator 输出迭代器output iterator 前向迭代器forward iterator 双向迭代器bidirectional iterator 随机存取迭代器random iterator 迭代器的适配器 分类 插入迭代器 反向遍历迭代器...
  • 迭代器概述与迭代器分类 ) 迭代器概述与迭代器分类 #include<iostream> #include<cstdlib> #include<string> #include<vector> #include <memory> #include <set> #include <...
  • 迭代器分类

    2017-04-17 21:12:07
    不同的迭代器适用于不同的容器在c++中有两种不同的迭代器分法:按操作分五类:输入迭代器:(相当于读取)取出其指向的值,访问下一个元素,判断是否到达下一个元素,可以复制:*p(读取), ++p, p++; p != q, p == ...
  • c++迭代器功能分类

    2019-10-03 16:16:10
    迭代器的功能分类 不同容器的迭代器,其功能强弱有所不同。容器的迭代器的功能强弱,决定了该容器是否支持 STL 中的某种算法。例如,排序算法需要通过随机访问迭代器来访问容器中的元素,因此有的容器就不支持排序...
  • 005迭代器概述与迭代器分类 #include<iostream> #include<cstdlib> #include<string> #include<vector> #include <memory> #include <set> #include <map> #include <...
  • C++中迭代器分类

    千次阅读 2018-09-11 15:53:04
    迭代器定义了常用的操作集,但有些迭代器具有比其他迭代器更强大的功能。例如ostream_iterator只支持自曾、解引用和复制运算,而...因此,迭代器可根据所提供的操作集进行分类。类似地,还可根据算法要求它的迭代器...
  • STL迭代器

    2018-07-27 20:14:33
    STL迭代器分类(5类) 输入迭代器(input):只能向前移动,一次一步,只可读取(不能涂写)迭代器所指的东西,而且只能读取一次。 输出迭代器(output):只能向前移动,一次一步,只可涂写迭代器所指的东西,...
  • STL 迭代器的操作分类

    2020-09-25 14:58:54
    不同容器的迭代器,其功能强弱有所不同。容器的迭代器的功能强弱,决定了该容器是否支持 STL 中的某种算法。例如,排序算法需要通过随机访问迭代器来访问容器中的元素,因此有的容器就不支持排序算法。 常用的迭代器...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,912
精华内容 1,164
关键字:

迭代器分类