C++primer_容器

九.顺序容器

• 顺序容器的顺序表示元素插入的顺序
• C++标准库容器提供了顺序访问元素的能力，但是不同的容器在以下的操作有不同的性能折中
  • 向容器添加或从容器中删除元素的代价
  • 非顺序访问容器中元素的代价
    顺序容器有以下几类
• vector
  可变大小数组，支持快速随机访问，使用数组实现，在尾部之外插入删除很慢
• deque
  双端队列，支持快速随机访问，在头尾插入删除很快
• list
  双向链表，只支持双向顺序访问，在链表的任何位置插入删除都很快
• forward_list
  单向链表，支持单项顺序访问，在链表的任何位置插入和删除都很快
• array
  固定大小数组，支持快速随机访问，不能添加或删除元素
• string
  与vector相似的容器，随机访问快，在尾部插入删除快

容器选择基本原则

• 尽量使用vector
• 程序中占主导地位的操作决定容器选择的类型

9.3 容器库概览

容器类型的操作形成了一种层次

• 某些容器操作是所有容器都提供的
• 还有一些仅针对顺序容器
• 还有一些只适用于小部分容器
  对容器保存元素类型的限制

insert操作：
都是插在iter的前面。
iterator insert(iter,n); //n插入iter前面,返回新元素的迭代器
void insert(iter,begin,end); //begin end插入iter前面。
void insert(iter,n,t); n个t插入iter前。
c.size()
c.max_size();
c.empty();
c.resize(n);  //改变c的长度
c.resize(n,t);

c.at(n)==c[n];
c.clear();//清空
c.erase(iter); //返回iter后面的元素
c.erase(begin,end);//返回begin，end后面的元素
pop_front()和front()经常一起使用。
iterator  find(begin,end,value)；//找到value出现的第一个地方。
。。。。。

迭代器

• 所有迭代器都是通过解引用运算符实现元素的访问。
• 一个迭代器范围表示迭代器容器中元素范围，使用左闭区间[begin,end)
  容器类型成员
• 每个容器都定义了很多类型成员和一些类型别名；类型别名用于不了解容器元素的情况下使用它。

类型别名：
difference_type; #存储两个迭代器差值的有符号整型，可为负数
value_type; #元素类型
reference 元素左值类型 ;value_type&
const_reference ;元素常量左值类型，const value_type&
size_type 无符号整型
类型成员：
const_iterator  #一个类型成员，用于返回常量迭代器
reverse_iterator
const_reverse_iterator

容器定义和初始化

容器元素初始化：  构造
 C<T> c;     //默认构造函数
 C<T>c(n);   //n个值初始化，只适用于顺序容器，必须给出默认构造函数
 C<T>c(n,t);    //n个t  只适用于顺序容器，可以不给，但要给出 T(t)构造函数。
 C<T>c(begin,end);  //begin，end复制到c中
 C<T> c1(c2);//c1和c2是相同的容器类型，存放相同类型元素，c2拷贝给c1

• C++11可以对容器进行列表初始化
• 顺序容器会将容器提供一个值初始化器（在指定容器长度的情况下，把容器内容初始化
  容器赋值运算

//交换操作：
swap(c1, c2) #交换c1和c2中的元素，两者需为相同类型。swap通常比从c2向c1拷贝元素快得多
c1.swap(c2) #assign操作不适用于关联容器和array
替换操作：
seq.assign(b, e) #将seq中的元素替换为迭代器b和e所表示的范围中的元素。迭代器b和e不能指向seq中的元素
seq.assign(il) #将seq中的元素替换为初始化列表il中的元素
seq.assign(n, t) #将seq中的元素替换为n个值为t的元素

• assign仅适用与顺序容器，assign允许我们将不同但是相容的类型赋值。
  关系运算符

9.4 顺序容器的操作

添加
访问

• 如果容器中没有元素，访问的结果是不确定的
• at()函数会对下标越界进行检查。
• 在容器中访问成员返回的都是引用
  删除
  改变容器大小
• 如果我们在初始化容器的时候定义了容器的大小，可以使用resize()来改变容器大小
  容器操作可能会使迭代器失效，所以每次改变容器都要重新获取迭代器

9.4 vector是如何增长的

• vector存储在连续空间，当空间用完后会重新申请空间，并移动全部元素，但是依然很快
• C++提供了一些成员函数，允许我们与它内存分配的部分互动

capacity，reserve只适用于vector和string
c.shirk_to_fit() #请将capacity减少为与size()相同的大小
c.capacity() #不重新分配内存，c能保持多少个对象
c.reserve(n) #分配至多能容纳n个对象的内存空间

9.6容器适配器

• 适配器是一个标准库中的通用概念，容器，迭代器，和函数都有适配器
• 一个适配器是一种机制，能让一个事物看起来像另一个事物
• 栈适配器，可以让vector像栈一样。。。。。
• 队列适配器。。。。

十：泛型算法

• 泛型表示可以用于不同的数据类型，他们调用经典的算法接口来实现

10.1概述

• 算法定义在头文件aalgorithm
• 迭代器让算法不依赖于容器，但算法依赖于元素类型的操作，

十一：关联容器

• map和set是关联容器，但是set只保存key
• C++提供提供8个关联容器，但是容器的区别体现在3个不同的维度
  • 每个容器或者是map，或者是set
  • 或者关键字可重复，或者不可重复
  • 顺序或者无序
• 允许重复的关键字前都包含multi，不保持关键字顺序的都使用unordered，

11.1使用关联容器

 map：关联数组，保存关键字-值对。
 set：关键字即值，即只保存关键字的容器。
 multimap：关键字可重复出现的map。
 multiset：关键字可重复出现的set。
    无序集合：
 unodered_map：用哈希函数组织的map。
 unodered_set：用哈希函数组织的set。
 unodered_multimap：哈希函数组织的map，关键字可重复出现。
 unodered_multiset：哈希函数组织的set，关键字可重复出现。

11.2关联容器概述

定义关联容器

• 每个关联容器都定义一个默认的构造函数，它创建一个指定容器的空容器。
• 关键字类型必须定义严肃比较方法，默认情况下，标准库使用<运算符来进行关键字比较。
• 提供自己的比较操作创建有序关联容器，如compareIsbn为自己定义的一个比较两个Sales_data的函数，则可以如下创建Sales_data的multiset：

# 表示当我们向bookstore添加元素的时候，通过调用compareIsbn方法为为这些元素排序，
# decltype指出要自定义操作的类型
multiset<Sale_data, decltype(compareIsbn)*> bookstore(compareIsbn);

这样就可以为没有重载<运算符的Sales_data类型支持关联容器操作。该函数指名了关键字
pair类型

• pair是一个二元组的绑定，map是一个映射
• pair标准库类型定义在头文件utility中。pair系类模板，创建一个pair时需要提供两个类型名。因此，一个pair元素包含两个成员，分别命名为first和second，均为public访问属性。pair提供的操作有：

 pair<T1, T2> p：p是一个pair，两个类型分别为T1和T2的成员都进行了值初始化。
 pair<T1, T2> p(v1, v2)：p是一个成员类型为T1和T2的pair，first和second成员分别用v1和v2进行初始化。
 pair<T1, T2> p = {v1, v2}：等价于pair<T1, T2> p(v1, v2)，此处也可省略=号。
 make_pair(v1, v2)：返回一个用v1和v2初始化的pair，类型从v1和v2的类型推断出来。可以用{v1, v2}的形式来替代。
 p.first：返回p的名为first的公有数据成员。
 p.second：返回p的名为second的公有数据成员。
 p1 *relop* p2：关系运算符按字典序定义，如当p1.first < p2.first或!(p2.first < p1.first) && p1.second < p2.second成立时，p1 < p2为true。关系运算利用元素的<运算符来实现。
 p1 ==p2和p1 != p2：当first和second成员分别相等时，两个pair相等。相等性利用元素的==运算符实现。

11.3 关联容器操作

• 关联容器定义了一些与普通容器不同的成员类型

key_type：此容器类型的关键字类型。
mapped_type：每个关键字关联的类型，只适用于map类关联容器。
value_type：对于set，与key_type相同，对于map，为pair<const key_type, mapped_type>。

• set 类型的key_type和value_type一样
• 使用作用域运算符取得关键字容器的成员
• 由于不能改变map的key，所以他的value_type返回的pair中键的部分是const的
  关联容器迭代器
• 当解引用一个迭代器的时候，我们会得到一个类型为容器的value_type的容器的值的引用
• map的value_type是一个pair
• 常用操作：

begin()、end() #分别返回容器的首迭代器和尾后迭代器，由于set只有关键字，而关键字不能被改变，所以set的迭代器无论是否是const_iterator，均只能用于读取。
c.insert(v)和c.emplace(args)：#v是value_type类型的对象；args用来构造一个元素。对于map和set，只有当元素的关键字不在c中时才插入（或构造）元素。函数返回一个pair，包含一个迭代器，指向具有指定关键字的元素，以及一个指示插入是否成功的bool值。对于multimap和multiset，总会插入（或构造）给定元素，并返回一个指向新元素的迭代器。
c.insert(b, e)和c.insert(il)：#b和e是迭代器，表示一个c::value_type类型值的范围；il是这种值的花括号列表。函数返回void。对于map和set，只插入关键字不在c中的元素。对于multimap和multiset，则会插入范围中的每个元素。
c.insert(p, v)和c.emplace(p, args)：#类似insert(v)（或emplace(args)），但将迭代器p作为一个提示，指出从哪里开始搜索新元素应该存储的位置。返回一个迭代器，指向具有给定关键字的元素。
c.erase(k)：#从c中删除每个关键字为k的元素。返回一个size_type值，指出删除的元素的数量。
c.erase(p)：#从c中删除迭代器p指定的元素。p必须指向c中一个真实的元素，不能等于c.end()。返回一个指向p之后元素的迭代器，若p指向c中的尾元素，则返回c.end()。
c.erase(b, e)：#删除迭代器b和e所表示的范围中的元素，返回e。
c.find(k)：#返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，则返回尾后迭代器。
c.count(k)：#返回关键字等于k的元素的数量。对于不允许重复关键字的容器，返回值永远是0或1。

关联容器和算法
通常不对关联容器使用算法，因为set的他们都有const的部分，但是可以使用只读的算法

• 对map使用find替代下标操作

c[k]：返回关键字为k的元素。如果k不在c中，添加一个关键字为k的元素，对其进行值初始化。
c.at(k)：访问关键字为k的元素，带参数检查。若k不在c中，抛出一个out_of_range异常。该操作，只使用于非const的map和unodered_map。
    **只适用于有序关联容器的操作**
c.lower_bound(k)：返回一个迭代器，指向第一个关键字不小于k的元素。
c.upper_bound(k)：返回一个迭代器，指向第一个关键字大于k的元素。
c.equal_range(k)：返回一个迭代器pair，表示关键字等于k的元素的范围，其first成员即相当于c.lower_bound(k)的返回值，其second成员相当于c.upper_bound(k)的返回值。

    以上操作，若容器中无关键字为k的元素，则相关返回的迭代器均为c.end()。

无序容器