首页 > 代码库 > c++顺序容器
c++顺序容器
- 定义和初始化
#include<vector>
#include<list>
#inlcude<deque>
初始化:C<T> c; 空容器,如vector<int> ivec; C c(c2); 创建容器c2的副本c C c(b,e); 由迭代器b,e标识的范围内的元素的副本,如list<int> ilist(ivec.begin(),ivec.end()); C c(n,t); 用n个值为t 的元素创建容器c C c(n); 创建有n个值初始化元元素的容器
string strings[]={"abc","def",ghi"};
deque<string> sdeq(strings,strings+sizeof(strings)/sizeof(string));
容器元素类型必须满足以下两个条件:
元素类型必须支持赋值运算;
元素类型的对象必须可以复制;
除了引用类型外,所有的内置类型或复合类型都可以用做元素类型。(引用不支持一般意义上的赋值运算),另外,IO类型不支持复制或赋值,故不能创建存放IO类型对象的容器。
容器存放的是复本,对于由其它容器或对象初始化的容器来说,更改其值不会影响被复制的原值。
容器的容器:
vector<vector<string> > lines;
>>中间要使用空格:
vector<vector<string>> lines;//error - 迭代器
迭代器为所有标准库容器类型所提供的运算:
*iter iter->item ++iter iter1==iter2 iter1!=iter2
vector和deque容器的迭代器提供的额外运算:(迭代器算术运算)
iter + n
iter - n
iter1+=iter2
>,>=,<,<=
上述只用于vector和deque容器,因为只有这两种容器为其元素提供快速,随机的访问。 - 容器操作
容器定义的类型别名:size_type UL,最大可能长度,作为索引的类型 iterator 此容器类型的迭代器类型 const_iterator 只读迭代器 reverse_iterator 按逆序寻址元素的迭代器 const_reverse_iterator 只读逆序迭代器 difference_type 足够存储两个迭代器差值的有符号整型,可负 value_type 元素类型 reference 元素左值类型,是value_type&的同义词 const_reference 元素常量左值类型,等效于const value_type&
关系操作符:
所有容器都支持关系操作符来实现来个容器的比较。比较的容器必须要有相同的容器类型,且元素类型也要相同。容器的比较是基于容器内元素的比较,故元素应要支持关系操作。
容器大小操作:
c.size()//当前大小
c.max_size()//可容纳最大数
c.empty()
c.resize(n)//调整大小为n,若n>c.size(),添加值采用初始化方法,否则删除多余值
c.resize(n,t)//调整大小为n,若n>c.size(),添加值为t,否则删除多余值
元素访问:
如果容器非空,则front和back成员将返回容器内第一个或最后一个元素引用:
if(!ilist.empty())
{
list<int>::reference val=*ilist.begin();//引用
list<int>::reference val2=ilist.front();//和val相同
list<int>::reference last=*--ilist.end();
list<int>::reference last2=ilist.back();
}
汇总:
c.back()
c.front()
c[n] //only vector and deque suported ,no list
c.at(n) //only vector and deque suported ,no list
删除元素:
一般来说,需要先找到要删除的元素后才能使用erase方法,寻找一个指定元素最简单的方法是使用标准库里的find方法。<algorithm>c.erase(p) 删除迭代器指向的元素,返回指向删除元素的下个元素的迭代器,若p为c.end()则函数未定义 c.erase(b,e) 删除迭代器b和e范围内的元素,返回指向删除元素段的下个元素的迭代器,若e为c.end(),则返回c.end() c.clear() 删除c中所有元素,返回void c.pop_back() 删除最后一个元素,返回void,若c为空,则函数未定义 c.pop_front() 删除第一个元素,返回void,若c为空,则函数未定义,只适用于list或deque
string searchValue("Quasimodo");
list<string>::iterator iter=find(slist.begin(),slist.end(),searchValue);
if(iter!=slist.end())
slist.erase(iter);
赋值与swapc1=c2 删除c1中所有内容,将c2的元素复制给c1。c1和c2的类型必须相同 c1.swap(c2) 交换内容:类型要相同。执行速度通常比将c2的元素复制到c1的操作快 c.assign(b,e) 重设c的元素:将迭代器b和e标记的范围内的元素复制到c中。b和e不能指向c中的元素 c.assign(n,t) 将c重设为存储n个值为t 的元素
当在不同或相同的容器中,元素类型不相同但是相互兼容,则其不能用=进行赋值,要用assign赋值。
swap:容器类型相同,元素类型相同。
c1.swap(c2);
swap操作没有移动元素,因此迭代器没有失效。比如在交换前,一个迭代器指向c1[2],实现交换后,该迭代器指向c2[2],指向的仍是同一个对象。
- 容器自增长
为了使vector容器实现快速的内存分配,vector容器预留了额外的存储区用于存放新加的元素。
由于vector是在内存中连续存放的,vector容器处理内存分配的细节是其实现的一部分,该部分是由vector的接口去持的。vector类提供了两个成员函数:capacity和reserve,使程序员可与vector容内存分配的实现部分的交互工作。capacity操作获取在容器需要分配更多的存储空间之前能够存储的元素总数,而reserve操作告诉vector容器应该预留多少个元素的存储空间。
size是指容器当前拥有的元数总数,而capacity是指容器在必须分配新的存储空间之前可以存储的元素总数。
vector<int> ivec;
cout<<"ivec:size: "<<ivec.size()<<endl; //0
cout<<"ivec:capacity:"<<ivec.capacity()<<endl; //0
//加入24个元素后
size:24
capacity:32
ivec.reserve(64);
size:24
capacity:64
//再加入24个元素后
size:48
capacity:64 //使用了预留的容量,不分配空间
//再加入24个元素
size:7
capacity:128//重新分配存储空间,以加倍当前容量的分配策略分配(依编译器变化) - 容器选择
Vector Deque List 随机访问 快速 快速 不支持 insert/erase 效率低 效率最低 快速 push_front() 不支持 快速 快速 push_back() 快速 快速 快速 pop_front() 不支持 快速 快速 pop_back() 快速 快速 快速
list不支持随机元素访问:
ilist.at(0);//error
ilist[0];//error
vector不支持push_front(val)和pop_front()操作。
选择容器的提示:
A.如果程序要求随机访问元素,则应使用vector或deque容器。
B.如果程序必须要在中间位置插入或删除元素则应采用list容器。
C.如果不需要在中间插入或删除元素,而是在首或尾部插入或删除元素,则应采用deque容器。
D.如果只需在读取输入时在容器的中间位置插入元素,然后需要随机访问元素,则可考虑在输入时将元素读入到一个list容器中,接着对此容器重新排序,使其适合顺序访问,然后将排序后的list容器复制到vector中。
E.如果程序既需要随机访问又必须在容器的中间位置插入或删除元素,此时选择何种容器取决于下面两种操作的代价:随机访问list的代价,在vector或deque容器中插入/删除元素时复制元素的代价。 - string和容器
string类型支持大多数顺序操作,在某些方面可将string类型视为字符容器。与vector容器不同的是,它不支持以栈方式操纵容器:在string类型中不能使用front,back和pop_back操作。
string 不支持的容器操作:
C<T> c(n) 初始化
push_front(e)
back,front
pop_back() pop_front()
关于string的具体介绍请参阅:《关于C++标准库中的 string》一文 - 容器适配器
除了顺序容器,标准库还提供了三种顺序容器适配器:queue,priority_queue和stack。
适配器支持的通用操作有:
size_type,value_type, container_type, A a; A a(c); 关系运算符
#include<stack>
#include<queue>
初始化:
两种方式:默认构造函数,空对象;带一个容器参数的构造函数将参数容器的副本作为其基础值。
例:假如deq是deque<int>类型的容器,则可用deq初始化一个新stack: stack<int> stk(deq);
覆盖基础容器类型:
默认的stack和queue都基于deque容器上实现,而priority_queue则在vector容器上实现。在创建适配器时,通过将一个顺序容器指定为适配器的第二个类型参数,可覆盖其关联的基础容器类型:
stack< string, vector<string> > str_stk; //implemented on top of vector
stack<string, vector<string> > str_stk(svec);//holds a copy of svec
stack 适配器要要所关联的容器可以是任意一种顺序容器,故可建立在vector,list或deuqe上。
queue适配器要求其关联的基础容器必须提供push_front运算,故只能建立在list容器上,不能建立在vector上。
priority_queue适配器要求提供随机访问的功能, 故可建立在vector或deque容器上,不能建立在list容器上。
栈适配器:
s.empty(),s.size(),s.pop(),s.top() ,s.push(item)
队列:FIFO queue
q.empty(),q.size(),q.pop(),q.front(),q.back(),q.push(item)
c++顺序容器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。