【C++学习】标准库：顺序容器（总结C++primer第九章）

标准库中的顺序容器

• 所有顺序容器都提供了快速顺序访问元素的能力，但在添加和删除元素，及非顺序访问元素时存在不同的性能折衷。

通常，使用vector是最好的选择，除非有更好的理由选择其他容器。

一般来说，每个容器都定义在一个与类型名相同的头文件中，容器均定义为模板类；

可以定义一个容器，其元素的类型是另一个容器；

容器操作

• 类型别名

  iterator	此容器类型的迭代器类型
  const_iterator	可以读取元素，但不能修改元素的迭代器类型
  size_type	无符号整型类型，足够保存此种容器类型最大可能容器的大小
  difference_type	有符号整型类型，足够保存两个迭代器之间的距离
  value_type	元素类型
  reference	元素的左值类型，与value_type&的含义相同
  const_reference	元素的const左值类型

• 构造函数

  C c	默认构造函数
  C c1(c2)	构造c2的拷贝c1
  C c(b, e)	构造c，将迭代器b和e指定的范围内的元素拷贝到c(array不支持)
  C c{a, b, c…}	列表初始化c

• 赋值与swap

  c1 = c2	将c1中的元素替换为c2中元素
  c1 = {a, b, c…}	将c1中的元素替换为列表中的元素(不适用于array)
  a.swap(b)	交换a和b的元素
  swap(a, b)	与a.swap(b)等价

• 大小

  c.size()	c中元素的数目(不支持forward_list)
  c.max_size()	c可保存的最大元素数目
  c.empty()	若c中存储了元素，返回false，否则返回true

• 添加/删除元素（不适用于array）

  c.insert(args)	将args中的元素拷贝进c
  c.emplace(inits)	使用inits构造c中一个元素
  c.erase(args)	删除args指定的元素
  c.clear()	删除c中的所有元素，返回void

• 关系运算符

  ==，!=	所有容器都支持相等（不等）运算符
  <，<=，>，>=	关系运算符（无序关联容器不支持）

• 获取迭代器

  c.begin()，c.end()	返回指向c的首元素和尾元素之后位置的迭代器
  c.cbegin()，c.cend()	返回const_iterator

• 反向容器的额外成员（不支持forward_list）

  reverse_iterator	按逆序寻址元素的迭代器
  const_reverse_iterator	不能修改元素的逆序迭代器
  c.rbegin()，c.rend()	返回指向c的尾元素和首元素之前位置的迭代器
  c.crbegin()，c.crend()	返回const_reverse_iterator

迭代器

• 迭代器运算符：***iter，iter->name，++iter，–iter，iter1 == iter2，iter1 != iter2；
• 迭代器算术运算：**iter + n，iter - n，iter1 += n，iter -= n，iter1 -iter2，>，>=，<，<=；
• forward_list迭代器不支持递减运算符；
• 这些迭代器算术运算只能应用于string、vector、deque和array。

容器定义和初始化

• 标准库array具有固定大小，定义时需指定元素类型和大小：

  array;
  

• 其他容器赋值运算：

  seq.assign(b, e)	将seq中的元素替换为迭代器b和e所表示范围中的元素。b和e不能指向seq中的元素
  seq.assign(i1)	将seq中的元素替换为初始化列表i1中的元素
  seq.assign(n, t)	将seq中的元素替换为n个t元素

• 赋值相关运算符会导致指向左边容器内部的迭代器、引用和指针失效；

• swap操作不会导致指向容器的迭代器、引用和指针失效，array和string除外；

• 应统一使用非成员版本的swap。

容器大小操作：只有当元素类型也定义了相应的比较运算符，才可以用关系运算符比较两个容器。

向容器添加元素

• 这些操作会改变容器的大小，array不支持这些操作；

• forward_list有自己专有版本的insert和emplace，forward_list不支持push_back和emplace，vector不支持push_front和emplace_front。

  添加操作	作用
  c.push_back(t)	在c的尾部创建一个值为t或由args创建的元素，返回void。
  c.emplace_back(args)
  c.push_front(t)	在c的头部创建一个值为t或由args创建的元素，返回void。
  c.emplace_front(args)
  c.insert(p, t)	在迭代器p指向的元素之前创建一个值为t或由args创建的元素，返回指向新添加的元素的迭代器。
  c.emplace(p, args)
  c.insert(p, n, t)	在迭代器p指向的元素之前插入n个值为t的元素。返回指向新添加的第一个元素的迭代器，若n为0，则返回p。
  c.insert(p, b, e)	在迭代器b和e指定的范围内的元素插入到迭代器p指向的元素之前。b和e不能指向c中的元素，返回指向新添加的第一个元素的迭代器，若范围为0，则返回p。
  c.insert(p, i1)	i1是一个花括号包围的元素值列表。将这些给定值插入到迭代器p指向的元素之前，返回指向新添加的第一个元素的迭代器，若列表为空，则返回p。

• 向一个vector、string或deque插入元素会使所有指向容器的迭代器、引用和指针失效。

• 用一个对象来初始化容器，或将一个对象插入到容器中时。实际上放入到容器中的是对象值的另一个拷贝，而不是对象本身。

访问元素

• at和下标操作只适用于string、vector、deque和array；

• back不适用于forward_list

  操作	含义
  c.back()	返回c中尾元素的引用。若c为空，函数行为未定义。
  c.front()	返回c中首元素的引用，若c为空，函数行为未定义。
  c[n]	返回c中下标为n的元素的引用，=若n>=c.size()，则函数行为未定义
  c.at(n)	返回下标为n的元素的运用，如果下标越界，则抛出一out_of_range异常

删除元素

• 这些操作会该表容器的大小，所以不适用于array；

• forward_list有特殊版本的erase。forward_list不支持pop_back；

• vector和string不支持pop_front。

  操作	含义
  c.pop_back()	删除c中尾元素，若c为空，则函数行为未定义吗，函数返回void
  c.pop_front()	删除c中首元素，若c为空，则函数行为未定义吗，函数返回void
  c.erase§	删除迭代器p所指向的元素，返回一个指向被删元素之后元素的迭代器，若p指向尾元素，则返回尾后迭代器，若p是尾后迭代器，则函数行为未定义。
  c.erase(b,e)	删除迭代器b和e所指向范围内的元素，返回一个指向最后一个被删元素之后元素的迭代器，若e本身就是尾后迭代器，则函数也返回尾后迭代器。
  c.clear()	删除c中所有元素，返回void

• 删除deque中除首尾位置之外的任何元素都会是所有迭代器、引用和指针失效，指向vector或string中删除点之后位置的迭代器，引用和指针都会失效。

改变容器大小

• resize不适用于array。

  操作	含义
  c.resize(n)	调整c的大小为n个元素，若n
  c.resize(n, t)	调整c的大小为n个元素，任何新添加的元素都初始化为值t

• 如果resize缩小容器，则指向被删除元素的迭代器、引用和指针都会失效；对vector。string或deque进行resize可能导致迭代器，指针和引用失效。

构造string的其他方法

substr操作

• s.substr(pos, n)：返回一个string，包含s中从pos开始的n个字符的拷贝。

改变string的其他方法

• args可以是下列形式之一；append和assign可以使用所有形式。
  • str不能与s相同，迭代器b和e不能指向s。
  • str：字符串str
  • str.pos, len：str中从pos开始最多len个字
  • cp.len：从cp指向的字符数组的前（最多）len个字符
  • cp：cp指向的以空字符结尾的字符数组
  • n, c：n个字符c
  • b, e：迭代器b和e指定的范围内的字符
  • 初始化列表：花括号包围的，以逗号分隔的字符列表
  • replace和insert所允许的args形式依赖于range和pos是如何指定的

string搜索操作

• args必须是以下形式之一
  • c, pos：从s中位置pos开始查找字符c。pos默认为0；
  • s2, pos：从s中位置pos开始查找字符串s2。pos默认为0；
  • cp, pos：从s中位置pos开始查找指针cp指向的以空字符结尾的c风格字符串。默认为0；
  • cp, pos, n：从s中位置pos开始查找指针cp指向的数组的前n个字符。pos和n无默认值；

compare函数

• s.compare的几种参数形式
  • s2：比较s和s2；
  • pos1, n1, s2：将s中从pos1开始的n1个字符与s2进行比较；
  • pos1, n1, s2, pos2, n2：将s中从pos1开始的n1个字符与s2中从pos2开始的n2个字符进行比较；
  • cp：比较s与cp指向的以空字符结尾的字符数组；
  • pos1, n1, cp：将s中从pos1开始的n1个字符与cp指向的以空字符结尾的字符数组进行比较；
  • pos1, n1, cp, n2：将s中从pos1开始的n1个字符与cp指向的地址开始的n2个字符进行比较。

数值转换

• to_string(val)：一组重载函数，返回数组val的string表示；
• stoi(s, p, b)、stol(s, p, b)、stoul(s, p, b)、stoll(s, p, b)、stoull(s, p, b)：
• 返回s的起始子串（表示整数的内容）的数值，返回值类型分别是int，long，unsigned long，long long，unsigned long long，b表示转换所用的基数。默认为10。p是size_t指针，用来保存s中第一个非数值字符的下标，p默认为0，即，函数不保存下标；
• stof(s, p)、stood(s, p)、stold(s, p)：返回s的起始子串（表示浮点数内容）的数值，返回值类型分别是float，double或long double，p是size_t指针，用来保存s中第一个非数值字符的下标，p默认为0。

适配器是标准库中的一个通用概念，容器、迭代器和函数都有适配器，本质上适配器是一种机制，能使某物的行为看起来向另外一种事物；

标准库定义了三个顺序容器的适配器：stack、queue和priority_queue；

默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上实现的。

所有容器适配器都支持的操作和类型：

栈适配器：定义在stack头文件中，先进后出

• 定义一个保存整形元素的栈：

  stack intStack;
  stack stk(deq);//从deq拷贝元素到stk
  

• 默认情况下，stack和queue是基于deque实现的，priority_queue实在vector之上实现的。可以在创建一个适配器时讲一个命名的顺序容器作为第二个类型参数，来重载默认容器类型：

• //在vector上实现的空栈
  stack> str_stk;
  stack> str_stk2(svec);
  

队列适配器：定义在queue头文件中，先进先出