九乡新闻网高破3 超级龙骑兵:C++容器:顺序容器，关联容器
来源：百度文库 编辑：九乡新闻网 时间：2024/04/29 08:03:24
容器主要分为顺序容器和关联容器。
一，顺序容器
vector－－连续存储的元素，单向的
list－－－－由节点组成的不连续存储的双向鏈表
deque－－连续存储的元素，双向的
1，顺序容器主要分为vector, deque, list。
2，容器内的元素类型必须至少满足2个条件：可复制和可赋值。
3，list容器的迭代器，不支持算术运算，不支持关系运算，也没有下标操作，只有最简单的自增 自减 相等 不等 运算。
4，所有的 迭代器范围都是左闭合区间， ［beg，end） 包括beg，但不包括end
5，顺序容器定义的几种类型：
size_type 容器大小
iterator 迭代器， reverse_iterator 逆序迭代器
const_iterator 只读迭代器(指向的元素只读), const_reverse_iterator
difference_type 迭代器的差值，可为负值
value_type 元素类型
reference 相当于 value_type&,即指向迭代器对应的元素
const_reference 相当于const value_type &
6，a.begin() a.end() 对应于 iterator；a.rbegin() a.rend() 对应于reverse_iterator,
注意，如果a是const的，那么iterator也必须是const_iterator的
7，添加元素的擦作
a.push_back(t); 在a末尾增加元素t；
a.push_front(t); 在a前端增加元素t，只使用于list和deque
a.insert(p,t); 在迭代器p前面插入元素t，返回新元素的迭代器
a.insert(p,n,t); 在迭代器p前面插入n个元素t，返回void
a.insert(p,b,e);在迭代器p前面插入迭代器b,e标记的范围内的元素，返回void
8,删除元素的操作
a.pop_back();删除a的最后一个元素，返回void,如果a为空，则函数未定义
a.pop_front();删除a的第一个元素，返回void;如果a为空，则函数未定义；只适用于list和deque
a.erase(p); 删除迭代器p指向的元素，返回下一个元素的迭代器；
a.erase(b,e);删除迭代器b，e之间的元素，返回下一个元素的迭代器
a.clear();删除a的所有元素,返回void
9,容器空间大小的操作
a.size() 元素个数 c.max_size() 最大元素个数
a.empty() bool值，指示a是否为空
c.resize(n,t) 重置c的大小为n，且 新增加的元素初始化为t。
10, a.begin() a.end()指向iterator
a.front() a.back() 指向reference
注意，vector::reference last=a.back(), last1=*--a.end();
，a.back指向最后一个元素，a.end指向最后一个元素的下一位置
11,顺序容器的赋值操作
c1=c2;
c1.swap(c2); c1 c2 互换
c.assign(b,e); 将迭代器b,e之间的元素复制给c
c.assign(n,t); 将c设置为n个值为t的元素
以上操作，都是首先删除c原来的所有元素后再进行的操作
二，顺序容器适配器(adaptor)
stack－－后进先出的排列，类似 堆 #include
queue－－先进先出的排列，队列
priority_queue－－优先队列 #include
1，适配器的初始化
适配器都是建立在某个顺序容器之上的。
stack stk(deg);
其中，deg为deque;
也就是说，创建适配器时，一般将一个顺序容器指定为其原本。
默认的stack和queue是基于deque实现的。
priority_queue则默认在vector上实现。
但是，实际上
statck可以建立在vector,list,deque任何一种容器之上
queue要求关联容器提供front操作，所以只有list和deque满足
priority_queue要求提供随机访问功能 ，所有只有vector和deque满足
如果适配器不是建在其默认类型上，则必须显式的指定其关联类型
stack > stk(ve);
其中ve为vector类型。
2，栈适配器stack的使用
先进后出
stk.empty() bool，空为true
stk.size() 元素个数
stk.pop() 删除栈顶元素，但是不返回其值
stk.top() 返回栈顶元素，但不删除其值
stk.push(item); 在栈顶压入item元素
3，队列和优先级队列
先进先出，优先级队列则按照优先级
三，关联容器(associative container)
map，multimap 类 －－#include
一，顺序容器
vector－－连续存储的元素，单向的
list－－－－由节点组成的不连续存储的双向鏈表
deque－－连续存储的元素，双向的
1，顺序容器主要分为vector, deque, list。
2，容器内的元素类型必须至少满足2个条件：可复制和可赋值。
3，list容器的迭代器，不支持算术运算，不支持关系运算，也没有下标操作，只有最简单的自增 自减 相等 不等 运算。
4，所有的 迭代器范围都是左闭合区间， ［beg，end） 包括beg，但不包括end
5，顺序容器定义的几种类型：
size_type 容器大小
iterator 迭代器， reverse_iterator 逆序迭代器
const_iterator 只读迭代器(指向的元素只读), const_reverse_iterator
difference_type 迭代器的差值，可为负值
value_type 元素类型
reference 相当于 value_type&,即指向迭代器对应的元素
const_reference 相当于const value_type &
6，a.begin() a.end() 对应于 iterator；a.rbegin() a.rend() 对应于reverse_iterator,
注意，如果a是const的，那么iterator也必须是const_iterator的
7，添加元素的擦作
a.push_back(t); 在a末尾增加元素t；
a.push_front(t); 在a前端增加元素t，只使用于list和deque
a.insert(p,t); 在迭代器p前面插入元素t，返回新元素的迭代器
a.insert(p,n,t); 在迭代器p前面插入n个元素t，返回void
a.insert(p,b,e);在迭代器p前面插入迭代器b,e标记的范围内的元素，返回void
8,删除元素的操作
a.pop_back();删除a的最后一个元素，返回void,如果a为空，则函数未定义
a.pop_front();删除a的第一个元素，返回void;如果a为空，则函数未定义；只适用于list和deque
a.erase(p); 删除迭代器p指向的元素，返回下一个元素的迭代器；
a.erase(b,e);删除迭代器b，e之间的元素，返回下一个元素的迭代器
a.clear();删除a的所有元素,返回void
9,容器空间大小的操作
a.size() 元素个数 c.max_size() 最大元素个数
a.empty() bool值，指示a是否为空
c.resize(n,t) 重置c的大小为n，且 新增加的元素初始化为t。
10, a.begin() a.end()指向iterator
a.front() a.back() 指向reference
注意，vector
，a.back指向最后一个元素，a.end指向最后一个元素的下一位置
11,顺序容器的赋值操作
c1=c2;
c1.swap(c2); c1 c2 互换
c.assign(b,e); 将迭代器b,e之间的元素复制给c
c.assign(n,t); 将c设置为n个值为t的元素
以上操作，都是首先删除c原来的所有元素后再进行的操作
二，顺序容器适配器(adaptor)
stack－－后进先出的排列，类似 堆 #include
queue－－先进先出的排列，队列
priority_queue－－优先队列 #include
1，适配器的初始化
适配器都是建立在某个顺序容器之上的。
stack
其中，deg为deque
也就是说，创建适配器时，一般将一个顺序容器指定为其原本。
默认的stack和queue是基于deque实现的。
priority_queue则默认在vector上实现。
但是，实际上
statck可以建立在vector,list,deque任何一种容器之上
queue要求关联容器提供front操作，所以只有list和deque满足
priority_queue要求提供随机访问功能 ，所有只有vector和deque满足
如果适配器不是建在其默认类型上，则必须显式的指定其关联类型
stack
其中ve为vector
2，栈适配器stack的使用
先进后出
stk.empty() bool，空为true
stk.size() 元素个数
stk.pop() 删除栈顶元素，但是不返回其值
stk.top() 返回栈顶元素，但不删除其值
stk.push(item); 在栈顶压入item元素
3，队列和优先级队列
先进先出，优先级队列则按照优先级
三，关联容器(associative container)
map，multimap 类 －－#include