C++容器和迭代器

C++

C++容器和迭代器

1. 容器

1.1 概述

  • 容器：一些特定类型对象的集合。定义在std命名空间中。

  • 顺序容器：提供控制元素存储和访问顺序的能力。这种顺序与元素的值无关，只与元素加入容器的顺序相关。按照元素在容器中的位置来顺序保存和访问。

    容器名称 容器特性
    vector 可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
    array 固定大小数组。支持快速随机访问。不能添加或者删除元素
    string 专门用于保存字符的可变大小数组。支持快速随机访问。在尾部插入删除速度很快
    deque 双端队列。支持快速随机访问。在头或者尾部插入或者删除速度很快
    list 双向链表。支持双向顺序访问。任何位置进行插入删除速度都很快
    froward_list 单向链表。支持单向顺序访问。任何位置进行插入删除速度都很快

  • 关联容器：容器中的元素按照关键字来保存和访问。

    容器名称 容器特性
    map，multimap 头文件map。元素为键值对，关键字进行索引，值存储数据,按顺序保存。mult表示允许重复关键字，下同。
    set，multiset 头文件set。元素为关键字，按顺序保存。不带mult则不允许重复关键字，下同。
    unordered_map，unordered_multimap 头文件unordered_map。性质同map。不按顺序保存，用哈希函数组织。
    unordered_set，unordered_multset 头文件unordered_set。性质同set。不按顺序保存，用哈希函数组织。

  • 注意

    • 标准库容器的性能几乎肯定与最精心优化过的同类数据结构一样好。所以建议使用标准库容器而不是原始的数据结构。
    • 一般情况下推荐使用vector。

1.2 容器通用操作

1.2.1 概述

  • 一般来说，每个容器定义在一个头文件中，文件名与容器名相同。容器类均为模板类，使用时必须提供特定的类型来生成特定的容器。

  • 容器保存的元素的限制

    • 可以保存任何类型的元素，甚至可以是另一个容器。

      1
      vector<vector<string>>lines;

    • 某些容器操作对元素类型有特定要求。因此要使用这些操作时，必须提供合法的元素类型。

1.2.2 定义和初始化

  • 容器的通用构造函数

    函数形式 作用
    C a 默认构造函数，array类型默认初始化，其他类型默认构造空容器
    C a(b)
    C a = b    		 a初始化为b的拷贝。二者必须是同类容器，且保存的元素类型相同。对于array两容器的大小必须相同
    C a{x,y,z,……}
    C a = {x,y,z,……}    		 初始化列表中的元素类型必须和a的元素类型相容。容器元素个数等于列表元素个数，array类型，列表中元素的数目小于等于array的大小
    C a(b,e) a初始化为任意容器的迭代器b和e指定范围内元素的拷贝，元素类型必须相容，容器类型可以不同。array不适用。拷贝范围[b,e)，新容器的大小等于此范围内的元素的个数。

  • 顺序容器特有构造函数

    • C c(n)：c包含n个元素并进行了值初始化。array，string不适用。有默认构造函数时才能使用此方法，否则应该使用下述方法。
    • C c(n,t)：c包含n个初始化为t的元素。array不适用。

  • array的定义和初始化

    • 标准库array的大小也是类型的一部分。定义时要指定元素的类型和容器的大小。不支持普通的容器构造函数。

      1
      array<int,42>a;		//此时类型为array<int,42>，意为保存42个int的数组

    • 初始化

      • 默认构造的array是非空的，它包含了与其大小一样多的元素。并且这些元素都被默认初始化了。
      • 列表初始化，初始值数目等于小于数组长度。剩余进行值初始化。
      • 值初始化。内置类型默认初始化为0，类类型使用默认构造函数初始化。
      • array类型可以相互赋值，但是必须满足元素类型相同，元素个数相同。
      • 因为大小是array类型的一部分，所以要求所有元素的类型和大小相同
1.2.3 赋值运算

  • a = b

    • 将a中的元素替换为b中的元素，二者必须具有相同的类型
    • 如果原有两个容器大小不等，则赋值之后二者的大小和右边容器的大小相等(array除外)

  • a = {b,c,d}

    • 将a中的元素替换为列表中元素的拷贝

    • 赋值运算之后，a的长度等于列表的长度

    • array不支持此种赋值形式。

      1
      2
      array<int,10>a = {0};		//正确，array可以进行列表初始化
      a = {0};					//错误，array不能用列表进行赋值

  • swap(a,b) a.swap(b)

    • 交换a b中的元素。
    • a b必须具有相同的类型
    • 一般速度比从b到a拷贝元素快的多
    • 除了应用于array类型，交换操作不会对任何元素进行拷贝、删除或者插入操作，只是交换容器内部数据结构，因此操作可以在常数时间内完成。并且交换之后指向容器内部的迭代器、指针、引用等依然有效，仍然指向交换操作之前所指向的元素。
    • 对于array类型，交换操作会真正交换二者的元素，所需时间与元素数目有关。并且交换之后指向容器内部的迭代器、指针、引用等依然有效，但是元素已经进行了交换。
    • 对于string类型，交换之后会导致引用、指针、迭代器等失效。

  • assign操作

    • 不适用于关联容器和array，可与构造函数相对应。
    • 允许使用不同但是相容的类型给左边的容器赋值。容器类型也不用相同。赋值之后左边容器的元素的个数等于赋予的元素个数。
    • seq.assign(b,e)，将seq中的元素替换为迭代器b和e所表示范围中的元素。两迭代器不能指向seq
    • seq.assign(il)，将seq中的元素替换为初始化列表il中的元素
    • seq.assign(n,t)，将seq中的元素替换为n个值为t的元素

  • 注意

    • 赋值操作会导致原来指向左边容器内部的迭代器、引用和指针失效，但是swap操作交换容器内容不会导致此种情况。

  • 参考资料

1.2.4 大小操作
  • size函数
    • 成员函数
    • 返回容器中元素的个数
    • forward_list不支持
  • empty函数
    • 成员函数
    • 判断容器是否为空，为空时，返回true，否则返回false
  • max_size函数
    • 成员函数
    • 返回一个大于或者等于该容器所能容纳的最大元素数的值。
1.2.5 关系运算符
  • 所有容器都支持==和!=运算符
  • 除了无序关联容器之外所有容器都支持关系运算符>、<、>=、<=。
  • 运算方式
    • 两个容器的比较实际上是进行元素的逐对比较。
    • 如果两个容器的大小相等，并且对应位置的元素相等，则两个容器相等
    • 如果两个容器的大小不等，但是较小容器中的每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
    • 如果两个容器都不是另一个容器的前缀子序列，则比较结果取决于第一个不相等的元素的比较结果。
  • 注意事项
    • 要求左右两个运算对象容器类型相同并且保存的元素类型相同
    • 容器的关系运算符使用元素的关系运算符进行比较，只有当元素类型定义了相应的比较运算符时，才能使用关系运算符比较两个容器。
    • 容器的相等运算符使用元素的==运算符进行比较，容器的其他运算符使用元素的<运算符进行比较。
    • 可以使用运算符重载的方式改变容器比较的结果。

2. 迭代器

  • 为访问容器提供统一的接口，迭代器即为访问容器中元素的统一的接口
  • 迭代器在接口上尽可能的模仿指针的行为。

2.1 迭代器定义和初始化

  • 迭代器类型

    • 拥有迭代器的标准类型库使用iterator和const_iterator表示迭代器的类型。
    • iterator相当于普通指针，指向的对象可读可写；const_iterator相当于指向常量的指针，指向的对象只能读但是不能修改。

  • 迭代器定义

    1
    2
    vector<int>::iterator iter;
    //容器名<元素类型>::迭代器类型  迭代器名;

  • 使用begin和end

    • 有迭代器的容器同时拥有返回迭代器的成员方法。
    • begin返回指向第一个元素的迭代器。
    • end返回指向容器最后一个元素的下一位置的迭代器，称为尾后迭代器。
    • 容器为空时，二者返回同一个迭代器，即为尾后迭代器。
    • 如果容器元素是常量，返回const_iterator类型的迭代器；如果容器元素不是常量，返回iterator类型的迭代器。
    • cbegin和cend方法，基本同begin和end。只是二者返回的一定是const_iterator类型的迭代器。

  • 迭代器初始化

    1
    2
    3
    4
    5
    6
    vector<int>::iterator iter;
    vector<int> iver;
    iter = iver.begin();
    iter = iver.end();
    iter = iver.cbegin();
    iter = iver.cend();

2.2 迭代器操作

  • 解引用*
    • 通过解引用运算符，可以获取迭代器所指向的元素，*iter。
    • 解引用运算符必须用于确实指向某个元素的迭代器，否则会出错。
  • 访问元素的成员->
    • 使用->运算符可以像指针一样访问迭代器所指向元素的成员，iter->a，相当于(*iter).a
  • 指向下一个元素++
    • 使用++iter操作可以使得迭代器指向下一个容器元素。
    • 不能对尾后迭代器使用此运算符，因为其后没有任何元素。
  • 指向上一个元素--
    • 使用方式同++运算符
    • forward_list迭代器不支持此操作。
  • 判断是否相等==、!=
    • 用于判断两个迭代器是否相等，iter1 == iter2，iter1 != iter2
    • 如果两个迭代器指向同一个元素或者是同一个容器的尾后迭代器，则二者相等；反之，则不相等。

2.3 迭代器运算

  • string、vector、deque、array的迭代器具有更多的运算。其他的迭代器不支持以下运算。
  • iter+n
    • 迭代器向后移动n个位置，指向新的元素或者是尾后迭代器，超出容器范围则会出错
  • iter-n
    • 迭代器向前移动n个位置，指向新的元素或者是尾后迭代器，超出容器范围则会出错
  • iter+=n和iter-=n
    • 同上+-操作
  • iter2-iter1
    • 二者相减得到的是二者之间的距离。即为右侧迭代器向前移动多少可以追上左侧迭代器。两个迭代器必须是同一个容器的迭代器。
    • 返回类型是带符号整数difference_type，可正可负。
  • <,<=,>,>=
    • 关系运算符，两个迭代器必须是同一个容器的迭代器。比较的是位置的先后。