容器与算法

顺序容器

• vector、list、deque

• 容器内元素类型的约束：必须支持赋值和复制操作，故引用类型和IO对象无法放入容器内

• 迭代器，提供的常用操作，*,->,++,--,==,!=

• vector和deque的迭代器提供的额外的操作，+n,-n,+=,-=,>,>=,<,<=

• 顺序容器提供的赋值操作

c1 = c2
c1.swap(c2)
c.assign(b,e)------assign首先会删除容器内所有的元素
c.assign(n,t)

• vector的capacity和reserve成员
  capacity获取vector能够存储的元素总数
  reserve设置vector应该事先预留多少的元素存储空间

• 指适用string的操作

s.substr(pos,n)
s.substr(pos)
s.substr()-----返回是副本

• string.find_first_of(args)在s中查找args的任意字符的第一次出现

• 容器适配器
  queue、priority_queue、stack
  stack和queue都是默认基于deque实现
  priority_queue是默认基于vector实现

• stack支持的操作empty\size\pop\top\push

• queue和priority_queue
  queue:empty\size\pop\front\back\push
  priority_queue:empty\size\pop\top\push
  其中pop都是删除首元素，但不返回值

---

关联容器

• 关联容器通过键来存储和读取元素、顺序容器则是通过容器中的位置顺序存储和访问元素，同时关联容器的元素按键值排序

• pair<string,string> p包含的操作，make_pair,<,==,.first（这是一个const的量）,.second

• 关联容器不能通过容器大小来定义

• list:插入删除、vector：随机访问、deque:首尾插入删除、map：key-value对集合情况、set：键集合

• map键类型约束：其类型必须存在一个比较函数，更进一步说支持<运算

• map相关类型

1、map::key_type
2、map::mapped_type
3、map::value_type 这个是一个pair类型具体而言是
pair<map::key_type,map::mapped_type>

• multimap和multiset，允许多个元素拥有相同的键，即multimap一个键可以对应多个值，multiset可以有多个相同的剑指

//输出同一个键值的多个实例
multimap<string,string>::iterator beg = test.lower_bound("test");
multimap<string,string>::iterator end = test.upper_bound("test");
while(beg!=end){ cout<<beg->second<<endl;beg++;}

---

泛型算法

• 标准容器自定义了很少的操作，标准库并未为每种容器定义其他的可操作的成员函数，而是定义了一组泛型算法，可以操作多种容器。

• 算法不使用容器的操作，其实现与容器类型无关，元素的访问和遍历通过迭代器实现。

• 一个有意思的算法
  string line = accumulate（wordvec.begin(),wordvec.end(),string(" ")）;

• 额外三种迭代器
  1、插入迭代器，实现在容器中插入元素的功能
  2、iosream迭代器，与IO流绑定，迭代遍历绑定的IO流
  3、反向迭代器reverse_iterator

• 五种迭代器

输入迭代器++
输出迭代器++
前向迭代器++
双向迭代器++，--
随机访问迭代器++，--，+=，-=，比较

map，set，list提供双向访问迭代器
vector，string，deque提供随机访问迭代器

• sort(beg,end);
  sort(beg,end,comp);
  find(beg,end,val);
  find_if(beg,end,pred);
  reverse(beg,end)
  reverse(beg,end,dest);

• list使用双向链表实现，故其操作如果使用标准算法，性能大大下降，故在标准库专门为list实现特有的操作，如list.merge、list.romove、list.reverse、list.sort、list.unique等