c++-容器使用

概述及共同操作

• 容器分类

  容器特性	容器
  序列式容器(有序)	array、vector、deque、list、forward_list
  关联式容器(有序)	set、multiset、map、multimap
  无序关联容器	unordered_set、unordered_multiset unordered_map、unordered_multimap

• 所有容器提供value语义，而非reference语义，即容易进行元素的插入时内部实施的是copy或move动作，而不是管理元素的reference

• 无论有序或无序，元素在容器内有特定顺序(无序容器内元素特定顺序的前提是没有插入或删除操作等)

• 共同操作(标准库7.1.2)

  操作	描述
  ConType c | c(c2) | c=c2 | c(rv) |c(begin,end) | c(initllist) | c=initlist	各种构造或初始化方法
  c.~ConType	删除元素，释放内存
  c.empty()	判断是否为空，等同于size()==0，但更快点
  c.size()	返回容器内元素个数
  c.max_size()	返回容器的最大可能容量
  c1 == c2 | c1 != c2	判断是否相等
  c1 < c2 | c <= c2	判断是否小于等于(不适用unordered容器)
  c = c2 | c = rv	赋值和move assign方式赋予c(不适用array容器)
  c1.swap(c2) | swap(c1, c2)	置换元素，一个成员函数，一个全局函数
  c.begin() | c.end()	返回iterator，指向第一个、最后一个元素
  c.cbegin() | c.cend()	返回const iterator，指向第一个、最后一个元素
  c.clear()	移除所有元素，令容易为空(不适用array容器)

序列容器

只有array不提供rezise(),因为大小固定

std::array(于<array>)

固定大小的数组(建立时必须指明大小)，不能改变元素的个数,只能改变元素的值
元素的个数是array类型的一部分，std::array<int, 5>和std::array<int,10>是2个不同的类型

std::array<std::string, 5> coll;//contain 5 string elements
//print each element with its index on a line
for(int i = 0; i < 5; ++i){
  std::cout<<i<<":"<<coll[i]<<std::endl;
}

std::vector(于<vector>)

类似数组，尾部插入元素快，插入位置越靠前代价越大(没有push_front)

vector默认或预定内存不够时需要重新分配内存，并将现有元素拷贝到新位置

string类似vector,但元素都为字符

std::vector<int> test = {{4}};//1个元素
std::vector<int> test2 = {4}; //1个元素

std::vector<int> test = {{}}; //1个元素,值为0
std::vector<int> test2 = {};  //0个元素

test.push_back(1); //vector只有push_back,不能push_front

std::deque(于<deque>)

double-ended queue的缩写，是一个dynamic array,可以向两端发展。
在尾部和头部出入元素都很迅速。中间插入需要移动其他元素，比较费时

std::deque<int> coll;
for (int i = 0; i < 9; ++i>){}
   coll.push_front(i); //insert at the front
   coll.push_back(i);  //insert at the back
   std::cout<<coll[i]<<std::endl; //输出元素
}

std::list(于<list>)-std::forward_list(于<forward_list>)

list由双向链表(doubly linked list)实现而成，其中每个元素都以一部分内存指示其前导元素和后继元素

优点:任何位置插入和删除元素快，只需改变链接(link)即可，而vector和deque需移动很多元素

缺点:随机访问的效率和vector和deque相比差很多。

list<char> coll; //list container for charactre elements
for(char c = 'a'; c <='z'; ++c){
    coll.push_back(c);  //添加元素
    std::cout<<coll[c]; //Error,list不提供操作符[]
}
//-1.print elem
for(auto elem : coll){ std::cout<<elem<<",";} //使用range-based for循环
//-2.print elem
while(!coll.empty()){
    cout<<coll.front()<<","; //输出第一个
    coll.pop_front();        //删除第一个(删除但不会返回)
}

forward_list只不过是收到更多限制的list,和list差异较小

forward_list是一个由元素构成的单向(singly)linked list，每个元素都有自己的一段内存只指向后继元素

不支持puch_back()和size()

---

关联容器

根据特定的排序规则，自动为元素排序。

关联容器主要由二叉树(binary tree)实现。对于每个元素(节点)其左子数所有元素比自己小，右子数所有元素比自己大，关联容器差别主要在于元素种类及处理重复元素的方式

优点：可快速找出一个特定value的元素，具备对数复杂度(logarighmic complexity),而一般的顺序容器是线性复杂度.(如1000个元素，平均有10次而不是500次比较动作)

缺点：不能直接改动元素的value(会破坏元素的自动排序)

std::set和std::multiset(于<set>)

set的元素根据其value自动排序，每个元素只能出现一次，不能重复

multiset则可以出现重复的元素。

multiset<string> cities;
//插入后自动排序，所以set内元素顺序和插入顺序无关
cities.insert({"beijing","munich","basel"});
for(const auto& elem : cities) {cout<<elem<<",";} 

std::map和std::multimap

map的每个元素(key/value),key是排序准则的基准，每个key只能出现一次，不能重复

multimap则允许出现相同的key

每个元素的类型其实为pair<const key, value>,key为const是因为如果内容被改动将破坏元素次序

map支持操作符[]

multimap<int, string> coll;
coll = {{5,"taggged"},{1,"a"},
        {3,"this"},{2,"of"},{1，"b"}};
for(const auto& elem : coll) {cout<<elem.second<<",";}

std::map的lower_bound和upper_bound
仅仅是不小于（lower_bound）和大于（upper_bound）这么简单

map::lower_bound(key):返回map中第一个大于或等于key的迭代器指针

map::upper_bound(key):返回map中第一个大于key的迭代器指针

---

无序容器(unordered container)

元素的次序不可预期，可比喻为一个装各种球的bag

通常以hash table实现…(value/key|hash_function|Buckets-Entries(linked list))

所有无序容器可指明hash函数和等效准则以判断是否发生重复

优点：查找特定值元素的速度可能快于关联容器(和使用的hash函数有关)，常量复杂度

缺点：提供一个良好的hash函数并不容易，而且需要提供许多内存给bucket

unordered_map同样支持操作符[]

//基本使用同对应的关联容器，仅仅是插入后次序不可预期

---

容器适配器(container adapter 12章)

stack(先进后出FILO)、queue(先进先出FIFO)基于deque实现

priority_queue(元素具有基于排序准则的优先权)基于vector实现

一个容器适配器接受一种容器类型使其行为看起来像另一种不用的容器

顺序容器适配器

queue 队列 front()第一个，back()最后一个，pop()删除第一个

std::unordered_set

std::unordered_set<int> c;
//普通插入,返回pair<迭代器,插入是否成功>
std::pair<std::unordered_set<int>::iterator, bool> c_insert = c.insert(1);

if(c_insert.second()) {...} //如果插入成功...