郴州微网站建设,竞价服务托管公司,模板王字库,北苑网站建设公司一、容器与模板 前文就说到#xff0c;标准库基于模板编程#xff0c;定义了许多容器类以及一系列泛型算法#xff0c;使程序员可以更简洁、抽象和有效地编写程序。C标准库中有大量的标准容器#xff0c;这些容器通常包含一组数据或对象的集合#xff0c;几乎可以和任何类…一、容器与模板 前文就说到标准库基于模板编程定义了许多容器类以及一系列泛型算法使程序员可以更简洁、抽象和有效地编写程序。C标准库中有大量的标准容器这些容器通常包含一组数据或对象的集合几乎可以和任何类型的对象一起使用C开发者只需要为程序选择合适的容器即可。例如STL库带给我们栈、自动增长的vector、map等等就可以使开发者集中精力于业务应用而不用重复制作轮子。了解所有容器对于C开发者来说至关重要。 想来大家对c/c语言的一门课数据结构不陌生吧它是c/c编程密切相关的科目几乎任何特定的数据结构都是为了实现某种算法而创建的。标准库中的容器就是将运用最广泛的一些数据结构实现出来。常用的数据结构不外乎是数值、链表、树、堆栈、队列、散列表、集合、映射表等。容器的好用及易用可能都致使大家把学过的数据结构与算法还回给课本了吧。 标准库定义类顺序容器和关联容器两大类其主要的区别就是顺序容器内的元素按其位置实现存储和访问等功能关联容器内的元素按其按键key实现存储和访问、排序等功能。并且关联容器共享了许多顺序容器提供的操作此外它们还定义了自己特殊的操作。 另外为了更好兼顾各个容器的功能操作标准库还将与容器操作的一些共性算法抽取处理作为泛型算法为容器类型提供通用接口服务。例如算法库提供了各种各样经典算法的有效实现像查找、排序及其他常见的算法任务。这些算法可作用于各种不同的容器类型这样容器提供的操作和算法是一致定义的接口的一致性使程序变得更灵活也便于标准库学习。
二、 顺序容器 顺序容器将单一类型元素聚集起来成为容器然后根据位置来存储和访问这些元素。其的元素排列次序与元素值无关而是由元素添加到容器里的次序决定。PS顺序容器的顺序是指元素存储的次序而非排序。 标准库定义了三种顺序容器类型数组(vector)、链表(list) 和双端队列( deque),它们的差别在于访问元素的方式以及添加或删除元素相关操作的运行代价。并根据三种顺序容器所提供的操作通过定义新的操作接口创建了容器适配器adaptors包括 栈(stack)、队列(queue) 和 priority_queue (优先队列)。前面提到容器只定义了少量操作大多数额外操作则由标准库的泛型算法提供。PSstring也可以 视为仅包含字符的特殊顺序容器string 类型提供大量的容器操作。 容器本质上是模板 这些容器类型的服务接口差别在于它们提供哪些操作但是如果两个容器提供了相同的操作则它们的接口函数名字和参数个数应该相同。
template typename T, typename Alloc alloc
class Vector
{...
}; 2.1 容器实例化与容器构造函数 所有容器都是类模板和我们自定义模板一样使用时需要显式指明模板参数容器类才能根据实参实例化容器类。并所有容器类型都定义了默认构造函数用于创建指定类型的空容器对象。默认构造函数不带参数并创造空对象类是容器类型最常用的构造函数大多数的程序中使用默认构造函数能达到最佳运行时性能。
#include vector
#include list
#include deque#include string
//vectorstd::string str_vec; //定义保存字符串类型的数组listint i_list; //定义保存整数类型的链表dequedouble d_dqs; //定义保存长浮点类型的双端队列 除了默认构造函数容器类型还提供其他的构造函数用其他构造函数初始化顺序容器时无论是直接还是间接都会指定该容器有多少个元素并提供这些元素的初值。
//
str_vec.push_back(hi);
vectorstring str_vec_copy(str_vec); //拷贝构造
vectorstring str_vec_size(2); //指定元素个数构造只适用于顺序容器,元素默认值就是元素类型默认构造
vectorstring str_vec_sVal(2,hello); 指定元素个数及元素默然值构造只适用于顺序容器
vectorstring str_vec_copy_it(str_vec.begin(),str_vec.end()); //拷贝构造指定复制区间[begin,end) 用其他的构造函数创建的容器必须确保为同一个容器类型及模板参数类型。
vectorint ivec;
vectorint ivec2(ivec); // ok
listint ilist(ivec); // error: ivec is not listint
vectordouble dvec(ivec); // error: ivec holds int not double 2.2 容器迭代器与拷贝构造 如果确实需要一种类型容器内的元素复制给另一种类型容器内就需要使用迭代器标准库允许通过传递一对迭代器间接实现该实现该功能不要求容器类型相同。容器内的元素类型也可以不相同只要它们相互兼容能够将要复制的元素转换为所构建的新容器的元素类型。
vectorstring str_vec_sVal(2,hello);
liststring slist(str_vec_sVal.begin(), str_vec_sVal.end());
dequestring front(str_vec_sVal.begin(), str_vec_sVal.begin()1); 为何可以这样呢那是因为迭代器本质上就是特殊的指针该指针指向顺序容器而顺序容器本质存储类似数组顺序容器通过迭代器拷贝本质上就是数组数据复制。 2.3 自定义容器模板参数类型 作为容器模板参数的元素类型必须是内置或复合类型或者是提供了默认构造函数的类类型。如果元素类型没有默认构造函数则必须显式指定其元素初始化式。
class DTest
{public:DTest():val(0){};DTest(int val_):val(val_){};int val;
};//vectorDTest dt_vec(2,DTest()); //定义保存DTest类型的数组,大小为2指定默认值为DTest()vectorDTest dt_vec_cp(dt_vec); //拷贝构造,定义保存DTest类型的数组DTest dt_(10);dt_vec_cp.push_back(dt_);dt_ dt_vec[0]; 对于顺序容器来说作容器的元素类型。容器元素类型必须满足以下两个约束 • 元素类型必须支持赋值运算。 • 元素类型的对象必须可以复制。
class DTest
{public:DTest():val(0){};DTest(int val_):val(val_){};int val;private:DTest(DTest constrhs); //禁止拷贝构造DTest operator(const DTest rhs); //禁止拷贝赋值构造
};//vectorDTest dt_vec(2,DTest()); //定义保存DTest类型的数组,大小为2指定默认值为DTest()vectorDTest dt_vec_cp(dt_vec); //error: DTest::DTest(const DTest) is privateDTest dt_(10);dt_vec_cp.push_back(dt_);dt_ dt_vec[0];//error, DTest DTest::operator(const DTest) is private 采用自定义类型作为容器的模板参数必须符合容器类对模板参数类型的要求尤其是自定义类型是编译器无法创建默认构造、拷贝构造、赋值函数等的情况例如自定义类型中包含有指针类型、复杂结构体等情况。 支持复制和赋值功能是容器元素类型的最低要求。此外不同类型容器操作对元素类型还有特殊要求。如果元素类型不支持这些特殊要求则相关的容器操作就不能执行即可以定义该类型的容器但不能使用某些特定的操作。 2.4 容器的容器 容器类也是数据类型和普通结构类型一样容器类也可以作为容器的模板参数如下图所示注意用空格隔开两个相邻的 符号以示这是两个分开的符号否则系统会认为 是单个符号为右移操作符并导致编译时错误
//
vectorstring str_vec; //定义保存字符串类型的数组
vectorvectorstring str_vecs; //定义保存vectorstring类型的数组
str_vecs.push_back(str_vec); 这时模板参数类型就变成了vectorstring作为模板参数同样需要满足赋值运算、拷贝构造等约束。所幸容器类作为一个标准化的类已经提供了这些支持我们不必担心。 2.5 容器迭代器与指针 每种容器类型都提供若干共同工作的迭代器类型。与容器类型一样所有迭代器具有相同的接口如果某种迭代器支持某种操作那么支持这种操作的其他迭代器也会以相同的方式支持这 种操作。例如所有容器迭代器都支持以解引用运算从容器中读入一个元素。类似地容器都提供自增和自减操作符来支持从一个元素到下一个元素的访问。迭代器本质上是指针例如
template typename T, typename Alloc alloc
class Vector
{public:typedef T value_type;typedef value_type* pointer;typedef value_type* iterator;typedef value_type* reference;...protected:iterator start;//目前可使用空间开始iterator finsh;//目前可使用空间结尾iterator end_of_storage;//目前可用空间结尾...public:iterator begin(){return start;};...
}; 因此在迭代器定义时主要还是通过确定的容器类及模板实参类确定的
vectorstring::iterator it;
it str_vec.begin(); 2.6 容器迭代器运算操作 标准库为给顺序容器迭代器提供通用运算操作operator*、operator-、operator、operator--operator、operator!针对vector和deque容器额外提供operator、operator、operator、operator-、/// 等运算方法。
//
vectorstring::iterator iter_vec str_vec.begin() str_vec.size()/2;//OK
//listint::iterator iter_list i_list.begin() i_list.size()/2;//error vector 和 deque 容器为其元素提供快速、随机的访问。它们确保可根据元素位置直接有效地访问指定的容器元素因此它们的迭代器可以有效地实现算术和关系运算。而list 容器的迭代器既不支持算术运算加法或减法也不支持关系运算, , , 它只提供前置和后置的自增、自减运算以及相等不等运算即前面讲到的通用运算操作。 标准库使用一对迭代器标记迭代器范围iterator range两个迭代器分别指向同一个容器中的两个元素或超出末端的下一位置形成左闭合区间left-inclusive interval[...) 。 除了迭代器iterator职务容器还定义了其他特殊迭代器
template typename T, typename Alloc alloc
class Vector
{public:typedef T value_type;typedef value_type* iterator; //此容器类型的迭代器类型typedef value_type const* const_iterator; //元素的只读迭代器类型typedef value_type* reverse_iterator; //按逆序寻址元素的迭代器typedef value_type const* const_reverse_iterator; //元素的只读不能写逆序迭代器...
}; 2.7 容器成员操作函数 每种顺序容器都提供了一组有用的类型定义以及以下操作 • 在容器中添加元素。 • 在容器中删除元素。 • 设置容器大小是否为空。 • 遍历容器。 以vector容器为例一般包含以下操作
1.增加函数void push_back(const T x):向量尾部增加一个元素Xiterator insert(iterator it,const T x):向量中迭代器指向元素前增加一个元素xiterator insert(iterator it,int n,const T x):向量中迭代器指向元素前增加n个相同的元素xiterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据2.删除函数iterator erase(iterator it):删除向量中迭代器指向元素iterator erase(iterator first,iterator last):删除向量中[first,last)中元素void pop_back():删除向量中最后一个元素void clear():清空向量中所有元素3.遍历函数reference at(int pos):返回pos位置元素的引用reference front():返回首元素的引用reference back():返回尾元素的引用iterator begin():返回向量头指针指向第一个元素iterator end():返回向量尾指针指向向量最后一个元素的下一个位置reverse_iterator rbegin():反向迭代器指向最后一个元素reverse_iterator rend():反向迭代器指向第一个元素之前的位置4.判断函数bool empty() const:判断向量是否为空若为空则向量中无元素5.大小函数int size() const:返回向量中元素的个数int capacity() const:返回当前向量所能容纳的最大元素值int max_size() const:返回最大可允许的 vector 元素数量值 在容器中添加元素时系统是将元素值复制到容器里。类似地使用一段元素初始化新容器时新容器存放的是原始元素的副本。被复制的原始值与新容器中的元素各不相关此后容器内元素值发生变化时被复制的原值不会受到影响反之亦然。 string srt_ hello;str_vec.push_back(srt_);srt_ change;str_vec.insert(str_vec.begin(),srt_);it str_vec.begin();while(it!str_vec.end()){std::cout *it std::endl;it;} 容器类提供push_back、insert函数增加容器元素push_back直接操作容器类对象而insert通过容器迭代器间接操作到容器类对象。在容器对象中 insert 或push_back压入一个元素时该对象的大小增加 1标准库处理存储这些新元素的内存分配问题。 2.8 容器迭代器失效问题 在 顺序容器中添加元素可能会导致整个容器的重新加载这样的话该容器涉及的所有迭代器都会失效。即任何 insert 或 push 操作都可能导致迭代器失效。当编写循环将元素插入到 vector 或 deque 容器中时程序必须确保迭代器在每次循环后都得到更新。 it str_vec.begin(); //迭代器先指向string srt_ hello;str_vec.push_back(srt_); //容器执行了push_back//it str_vec.begin(); //while(it!str_vec.end()) //error,迭代器失效{std::cout *it std::endl;it;} 尤其是在操作迭代器进行遍历容器时 如果有删减动作(增加内容也一样)必须要特别注意
vectorstring::iterator it str_vec.begin();
while(it!str_vec.end())
{std::cout *it std::endl;if(*ithi)str_vec.erase(it); //error,it失效it;
}
/*------------------------------------------------------------*/
vectorstring::iterator it str_vec.begin();
vectorstring::iterator last str_vec.end();
while(it!last) //error,循环更改了容器内容,last失效
{std::cout *it std::endl;if(*ithi){
#ifdef WIN32it str_vec.erase(it); //重新赋值
#else vectorstring::iterator it_temp it;str_vec.erase(it_temp);
#endif//last str_vec.end();continue;}it;
} 在使用容器时建议在每次做完增删运算后重新计算迭代器指向。 it str_vec.begin();while(it!str_vec.end()) //循环更改了容器内容,end()可以实时指向新的{std::cout *it std::endl;if(*ithi){#ifdef WIN32it str_vec.erase(it); //重新赋值#else vectorstring::iterator it_temp it;str_vec.erase(it_temp);#endifcontinue;}it;} 2.9 容器类型的关系比较 所有的容器类型都支持用关系操作符来实现两个容器的比较比较的容器必须具有相同的容器类型而且其元素类型也必须相同。容器的比较本质上是基于容器内元素的比较。容器的比较使用了元素类型定义的同一个关系操作符例如两个容器做 ! 比较实际上是使用了其元素类型定义的 ! 操作符来逐一比较容器的元素。如果容器模板参数类型不支持某种操作符则该容器类型就不能做这种比较运算。
vectorstring str_vec; //定义保存字符串类型的数组
str_vec.push_back(hi);
vectorstring str_vec_copy(str_vec); //拷贝构造
std::cout string((str_vecstr_vec_copy)?true:false) std::endl;//true
str_vec_copy[0]hil;//hil
std::cout string((str_vecstr_vec_copy)?true:false) std::endl;//false
std::cout string((str_vecstr_vec_copy)?true:false) std::endl;//true
str_vec.push_back(adc);//hi,abc
std::cout string((str_vecstr_vec_copy)?true:false) std::endl;//false 因此如果采用自定义类型作为容器的模板参数时和运算操作符一样如果想就该容器类型实现对应的关系操作符就必须提供模板参数类型的对应关系操作符。 //用到了容器的操作符,就需要先定义模板参数类型的操作符inline bool operator(const DTest obj1, const DTest obj2) {return obj1.valobj2.val;};//vectorDTest dt_vec(2,DTest()); //定义保存DTest类型的数组,大小为2指定默认值为DTest()vectorDTest dt_vec_cp(dt_vec); //拷贝构造,定义保存DTest类型的数组std::cout string((dt_vecdt_vec_cp)?true:false) std::endl; //falseDTest dt_(10);dt_vec_cp.push_back(dt_);std::cout string((dt_vecdt_vec_cp)?true:false) std::endl;//truedt_vec.push_back(DTest(9));std::cout string((dt_vecdt_vec_cp)?true:false) std::endl;//true 2.10 容器大小、元素访问与增删 所有容器类型顺序及关联容器都提供四种与容器大小相关的操作size 操作返回容器内元素的个数empty 操作则返回一个布尔值当容器的大小为 0 时返回值为 true否则为 false。还可以通过resize重新调整容器 c的长度大小使其能容纳 n 个元素如果 n c.size()则删除多出来的元素否则添加采用值初始化的新元素。
//std::cout Container size\n;std::cout str_vec.empty() str_vec.empty() std::endl; //falsestd::cout str_vec.size() str_vec.size() std::endl; //3std::cout str_vec.max_size() str_vec.max_size() std::endl;//178956970str_vec.resize(5);std::cout str_vec.size() str_vec.size() std::endl; //5std::cout str_vec.max_size() str_vec.max_size() std::endl;//178956970str_vec.resize(2);std::cout str_vec.size() str_vec.size() std::endl; //2std::cout str_vec.max_size() str_vec.max_size() std::endl;//178956970 顺序容器访问元素可以通过迭代器访问还可以通过front 和 back 成员函数访问特定元素,部分(vector 和 deque 容)可以通过下标访问。
std::cout str_vec[0] str_vec[0] std::endl;
std::cout str_vec.at(0) str_vec.at(0) std::endl;
std::cout str_vec.front() str_vec.front() std::endl;
std::cout *(str_vec.begin()) *(str_vec.begin()) std::endl; 在使用下标访问元素时需保证在指定下标位置上的元素确实存在。下标操作符本身不会做相关的检查。使用 front 或 back 运算时如果容器为空那么这些操作将产生未定义的结果。 前面内容中展示过erase删除容器元素的代码案例除此之外容器类型提供了特定的 pop_front 和 pop_back 操作来删除容器内的元素以及clear清空容器所有元素。
c.erase(p) 删除迭代器 p 所指向的元素
c.erase(b,e) 删除迭代器 b 和 e 所标记的范围内所有的元素
c.clear() 删除容器 c 内的所有元素。返回 void
c.pop_back() 删除容器 c 的最后一个元素。返回 void。如果 c 为空容器则该函数未定义
c.pop_front() 删除容器 c 的第一个元素。返回 void。如果 c 为空容器则该函数未定义只适用于 list 或 deque 容器 erase的这两种形式都返回一个迭代器它指向被删除元素或元素段后面的元素。erase 操作也不会检查它的参数。使用者必须确保用作参数的迭代器或迭代器范围是有效的。正如本文前面在循环体里涉及erase 调用一样。 2.11 容器元素交换功能 比起前面简述的这些常用函数操作顺序容器还提供了一些其他方面函数操作
void swap(vector):交换两个同类型向量的数据
void assign(int n,const T x):设置向量中前n个元素的值为x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素 swap操作实现交换两个容器内所有元素的功能该操作不会使迭代器失效使用时确保操作数必须是相同类型的容器而且所存储的元素类型也必须相同。完成 swap 操作后尽管被交换的元素已经存放在另一容器中但迭代器仍然指向相同的元素。而assign 操作和赋值函数一样会使左操作数容器的所有迭代器失效。 str_vec.swap(str_vec_copy);std::cout str_vec.front() str_vec.front() std::endl;std::cout str_vec.back() str_vec.back() std::endl;str_vec.assign(5, Hi prfree!);std::cout str_vec.size() str_vec.size() std::endl;std::cout str_vec.front() str_vec.front() std::endl; 由于swap操作时容器内没有移动任何元素因此迭代器不会失效也因此节省删除元素的成本。 2.12 容器应用选择 在前面已经提到标准库已经为容器做了内存管理插入及删除元素时标准库处理存储这些新元素或删除旧元素的内存分配问题。同时应该也清楚顺序容器中vector 、deque为了支持快速的随机访问元素以连续的方式存放一个元素都紧挨着前一个元素存储。假设当我们在vector 容器内添加一个元素时如果容器中已经没有空间容纳新的元素此时由于元素必须连续存储以便索引访问所以不能在内存中随便找个地方存储这个新元素。于是vector 容器必须重新分配存储空间用来存放原来的元素以及新添加的元素存放在旧存储空间中的元素被复制到新存储空间里接着插入新元素最后撤销旧的存储空间。如果 vector 容器在每次添加新元素时都要这么分配和撤销内存空间其性能将会非常慢简直无法接受。当然只是假设每次新增元素时连续空间都被占用了的情况。实际中标准库为了使 vector 容器实现快速的内存分配其实际分配的容量要比当前所需的空间多一些。vector 容器预留了这些额外的存储区用于存放新添加的元素。 对于不连续存储元素的容器不存在这样的内存分配问题。例如在 list 容器中添加一个元素标准库只需创建一个新元素然后将该新元素连接在已存在的链表中不需要重新分配存储空间也不必复制任何已存在的元素。 list 容器表示不连续的内存区域允许向前和向后逐个遍历元素。在任何位置都可高效地 insert 或 erase 一个元素。插入或删除 list 容器中的一个元素不需要移动任何其他元素。另一方面list 容器不支持随机访问访问某个元素要求遍历涉及的其他元素。 为此通过下面例子测试一下
//listint i_list; //定义保存整数类型的链表const int test_count 1000000;std::cout clock() clock() std::endl;for(int i0; itest_count ; i){i_list.push_back(i%3);}for(int i0; itest_count ; i){i_list.pop_back();}std::cout clock() clock() std::endl;vectorint i_vec;std::cout clock() clock() std::endl;for(int i0; itest_count ; i){i_vec.push_back(i%3);}for(int i0; itest_count ; i){i_vec.pop_back();}std::cout clock() clock() std::endl; 而输出结果却不大敢相信
clock() 51
clock() 263
clock() 264
clock() 300 为此调整代码不在容器末尾添加元素而是在容器头部插元素。
//listint i_list; //定义保存整数类型的链表const int test_count 1000000;std::cout clock() clock() std::endl;for(int i0; itest_count ; i){//i_list.push_back(i%3);i_list.insert(i_list.begin(),i%3);}for(int i0; itest_count ; i){i_list.pop_back();}std::cout clock() clock() std::endl;vectorint i_vec;std::cout clock() clock() std::endl;for(int i0; itest_count ; i){//i_vec.push_back(i%3);i_vec.insert(i_vec.begin(),i%3);}for(int i0; itest_count ; i){i_vec.pop_back();}std::cout clock() clock() std::endl; 展示的差距一下子就出来了。对于 vector 容器除了容器尾部外其他任何位置上的插入或删除操作都要求移动被插入或删除元素右边所有的元素。
//const int test_count 1000000;
clock() 43
clock() 268
clock() 269
clock() 267175//const int test_count 100;
clock() 38
clock() 38
clock() 39
clock() 39 deque 容器拥有更加复杂的数据结构和vector一样支持对所有元素的随机访问并从 deque 队列的两端插入和删除元素都非常快但在容器中间插入或删除付出的代价将更高。 因此一般而言元素频繁增删时(除了仅在末尾添加元素无其他增删操作)使用 list 容器优于 vector 容器尤其时在容器元素个数大的情况下。但是通常出现的反而是以下情况对于大部分应用使用 vector 容器是最好的。原因在于标准库的实现者使用这样内存分配策略以最小的代价连续存储元素。由此而带来的访问元素的便利弥补了其存储代价。 另外vector 也不必为每个新元素重新分配容器。所分配的额外内存容量的确切数目因库的实现不同而不同。比起每添加一个新元素就必须重新分配一次容器这个分配策略带来显著的效率。事实上其性能非常好因此在实际应用中比起 list 和deque 容器vector 的增长效率通常会更高。 2.13 容器存储空间分配 为此vector 类提供了两个成员函数capacity 和reserve 使程序员可与 vector 容器内存分配的实现部分交互工作。capacity操作获取在容器需要分配更多的存储空间之前能够存储的元素总数而 reserve操作则告诉 vector 容器应该预留多少个元素的存储空间。
//std::cout str_vec.size() str_vec.size() std::endl; //5std::cout str_vec.capacity() str_vec.capacity() std::endl;//5str_vec.push_back(test1);str_vec.push_back(test2);std::cout str_vec.size() str_vec.size() std::endl;//7std::cout str_vec.capacity() str_vec.capacity() std::endl;//10for(int i0; i10; i){str_vec.push_back(test_);}std::cout str_vec.size() str_vec.size() std::endl;//17std::cout str_vec.capacity() str_vec.capacity() std::endl;//20str_vec.reserve(30); std::cout str_vec.size() str_vec.size() std::endl;//17std::cout str_vec.capacity() str_vec.capacity() std::endl;//30str_vec.clear();std::cout str_vec.size() str_vec.size() std::endl;//0std::cout str_vec.capacity() str_vec.capacity() std::endl;//30str_vec.reserve(5); std::cout str_vec.size() str_vec.size() std::endl;//0std::cout str_vec.capacity() str_vec.capacity() std::endl;//30 vector 容器在只要有剩余的容量就不必为其元素重新分配存储空间。reserve可以指定预留量但只有在capacity 小于reserve指定量时才其作用否则capacity 时不会做出调整的。 总的来说vector 和 deque容器提供了对元素的快速随机访问类似于内存地址偏移访问一样但付出的代价是在容器的任意位置插入或删除元素比在容器尾部插入和删除的开销更大。list 类型在任何位置都能快速插入和删除但付出的代价是元素的随机访问开销较大。在实际项目使用中根据具体使用场景配用。 如果无法确定某种应用应该采用哪种容器则编写代码时尝试只使用 vector 和 lists 容器都提供的操作使用迭代器而不是下标并且避免随机访问元素。这样编写在必要时可很方便地将程序从使用 vector 容器修改为使用 list 的容器。 2.14 伪容器string类 前面还提到过string 类型可以看作是模板参数类型为字符的顺序容器它支持大多数顺序容器操作。除了一些特殊操作string 类型提供与 vector 容器相同的操作例如下标访问、迭代器访问、容器大小、增加元素等。string 类型与 vector 容器不同的是它不支持以栈方式操纵容器在 string 类型中不能使用 front、back 和 pop_back 操作。
//string s_vec hello world;s_vec.push_back(!);string::iterator iter_s s_vec.begin();while (iter_s ! s_vec.end()){cout *iter_s; }cout \n;for(int i0; is_vec.size(); i){cout s_vec[i];}cout \n; 下面给出string的大体成员函数对标一下前面所述的vector竟然是如此相近,妥妥的类似于vectorchar。
1)字符访问string::at–访问特定字符带边界检查string::operator[]–访问特定字符string::front–访问第一个字符string::back–访问最后一个字符string::data–访问基础数组C11 后与 c_str() 完全相同string::c_str–返回对应于字符串内容的 C 风格零结尾的只读字符串string::substr–以子串构造一个新串参数为空时取全部源串2)迭代器string::begin–获得指向开始位置的迭代器string::end–获得指向末尾的迭代器string::rbegin–获得指向末尾的逆向迭代器string::rend–获得指向开始位置的逆向迭代器string::cbegin–获得指向开始位置的只读迭代器string::cend–获得指向末尾的只读迭代器string::crbegin–获得指向末尾的逆向只读迭代器string::crend–获得指向开始位置的逆向只读迭代器3)容量大小string::empty–检查是否为空string::size–返回数据的字符长度string::length–返回数据的字符长度与 size() 完全相同string::max_size–返回可存储的最大的字节容量在 32 位 Windows 上大概为 43 亿字节。string::reserve–改变 string 的字符存储容量实际获得的存储容量不小于 reserve 的参数值。string::capacity–返回当前的字符存储容量string::shrink_to_fitC11新增–降低内存容量到刚好4增改string::clear–清空内容string::insert–插入字符或字符串。目标 string 中的插入位置可用整数值或迭代器表示。如果参数仅为一个迭代器则在其所指位置插入0值。string::erase–删除 1 个或 1 段字符string::push_back–追加 1 个字符string::pop_back–删除最后 1 个字符C11 标准引入string::append–追加字符或字符串string::operator–追加只有一个参数——字符指针、字符或字符串不像 append() 一样可以追加参数的子串或若干相同字符string::copy–拷贝出一段字符到 C 风格字符数组有溢出危险string::resize–改变增加或减少字符串长度如果增加了字符串长度新字符缺省为 0 值string::swap–与另一个 string 交换内容string::replace–替换子串如果替换源数据与被替换数据的长度不等则结果字符串的长度发生改变5搜索string::find–前向搜索特定子串的第一次出现string::rfind–从尾部开始后向搜索特定子串的第一次出现string::find_first_of–搜索指定字符集合中任意字符在 *this中的第一次出现string::find_last_of–搜索指定字符集合中任意字符在 *this 中的最后一次出现string::find_first_not_of–*this 中的不属于指定字符集合的首个字符string::find_last_not_of–*this 中的不属于指定字符集合的末个字符string::compare–与参数字符串比较
二、容器适配器 标准库基于vector、list、deque容器提供了三种顺序容器适配器queue、priority_queue 和 stack。适配器adaptor是标准库中通用的概念包括容器适配器、迭代器适配器和函数适配器。本质上适配器是使一事物的行为类似于另一事物的行为的一种机制类似于我们说的适配器设计模式。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。 默认的 stack 和 queue 都基于 deque 容器实现而 priority_queue 则在 vector 容器上实现。 2.1 stack容器适配器 例如我们可以通过类模板定义仿标准库定义stack类观察它实现原理
template typename T
class MyStack
{private:std::dequeT elems;public:void push(T const val);void pop();T top() const;bool empty() const;bool clear();//template typename T1MyStackT operator(MyStackT1 const);
};
template typename T
void MyStackT::push(T const val)
{elems.push_front(val);//栈顶增加
};template typename T
void MyStackT::pop()
{elems.pop_front();//栈顶先出
};template typename T
T MyStackT::top() const
{return elems.front();//优先取栈顶元素
};template typename T
bool MyStackT::empty() const
{return elems.empty();//
};template typename T
bool MyStackT::clear()
{return elems.clear();
};template typename T
template typename T1
MyStackT MyStackT::operator(MyStackT1 constrhs)
{if((void*)this(void*)rhs) //禁止赋值自身{return *this;}MyStackT1 tmp(rhs);elems.clear();while(!tmp.empty()){elems.push_back(tmp.top());//先进后出,保持和右值容器次序一致tmp.pop();}return *this;
};//MyStackint i_mystack;MyStackfloat f_mystack;i_mystack.push(100);i_mystack.push(200);f_mystack i_mystack; //Ok,int型被转换为floatstd::cout f_mystack.top() f_mystack.top() std::endl; 所有容器适配器都根据其基础容器类型所支持的操作来定义自己的操作。上述的类模板以deque容器为基础通过按栈的行为重新设计操作行为提供栈特性的处理能力将双端队列操作行为的容器适配为栈行为的容器。stack 栈可以建立在vector、list 或者 deque 容器之上。而 deque容器提供 push_front 运算可以在集合的另一端插入元素很好地满足栈的特性因此优先选择了建立在deque 容器上。这里只是抛砖引玉标准库做了类似的实现只是提供了更加丰富、更加完善的功能。 2.2 队列及优先队列容器适配器 标准库队列使用了先进先出FIFO的存储和检索策略。进入队列的对象被放置在尾部下一个被取出的元素则取自队列的首部。标准库提供了两种风格的队列FIFO 队列FIFO queue简称 queue以及优先级队列priority queue。两者提供了类似的操作不查看源码我们并不会想到它们是基于不同的原型容器实现的它们统一由 《queue》标准库文件提供主要区别就是优先队列在容器进入队列时会按排序加入队列。
q.empty() 如果队列为空则返回 true否则返回 false
q.size() 返回队列中元素的个数
q.pop() 删除队首元素但不返回其值
q.front() 返回队首元素的值但不删除该元素
该操作只适用于队列
q.back() 返回队尾元素的值但不删除该元素
该操作只适用于队列
q.top() 返回具有最高优先级的元素值但不删除该元素
该操作只适用于优先级队列
q.push(item) 对于 queue在队尾压入一个新元素对于 priority_quue在
基于优先级的适当位置插入新元素 priority_queue 允许用户为队列中存储的元素设置优先级。这种队列不是直接将新元素放置在队列尾部而是放在比它优先级低的元素前面。标准库默认使用元素类型的 操作符来确定它们之间的优先级关系当在队列push元素时优先队列会自动依据元素类型操作符给其排序。
#include queue
class DTest
{public:DTest():val(0){};DTest(int val_):val(val_){};int val;private://DTest(DTest constrhs); //禁止拷贝构造//DTest operator(const DTest rhs); //禁止拷贝赋值构造
};inline bool operator(const DTest obj1, const DTest obj2)
{return obj1.valobj2.val;
};//priority_queueDTest pque;//push元素,注意DTest类型是数越大优先级越高pque.push(23);pque.push(15);pque.push(18);pque.push(21);while (!pque.empty()){cout pque.top().val ; //23 21 18 15pque.pop();}cout \n; 其实容器定义的操作非常少只定义了构造函数、添加或删除元素的操作、设置容器长度的操作以及返回指向特殊元素的迭代器的操作。其他一些有用的操作如排序、查找则不是由容器类型定义标准库是通过标准泛型算法为容器额外提供的待续。
三、测试源码补充 创建test.h/cpp源文件运行g test.cpp -o test.exe指令编译运行输出程序 test.h
#ifndef _TEST_H_
#define _TEST_H_#include vector
#include list
#include deque
#include queueclass DTest
{public:DTest():val(0){};DTest(int val_):val(val_){};int val;private://DTest(DTest constrhs); //禁止拷贝构造//DTest operator(const DTest rhs); //禁止拷贝赋值构造
};inline bool operator(const DTest obj1, const DTest obj2)
{return obj1.valobj2.val;
};template typename T
class MyStack
{private:std::dequeT elems;public:void push(T const val);void pop();T top() const;bool empty() const;bool clear();//template typename T1MyStackT operator(MyStackT1 const);
};
template typename T
void MyStackT::push(T const val)
{elems.push_front(val);//栈顶增加
};template typename T
void MyStackT::pop()
{elems.pop_front();//栈顶先出
};template typename T
T MyStackT::top() const
{return elems.front();//优先取栈顶元素
};template typename T
bool MyStackT::empty() const
{return elems.empty();//
};template typename T
bool MyStackT::clear()
{return elems.clear();
};template typename T
template typename T1
MyStackT MyStackT::operator(MyStackT1 constrhs)
{if((void*)this(void*)rhs) //禁止赋值自身{return *this;}MyStackT1 tmp(rhs);elems.clear();while(!tmp.empty()){elems.push_back(tmp.top());//先进后出,保持和右值容器次序一致tmp.pop();}return *this;
};#endif //_TEST_H_ test.cpp
#include test.h
#include string
#include iostream
#include time.husing namespace std;int main(int argc, char* argv[])
{std::cout Container define\n;vectorstring str_vec; //定义保存字符串类型的数组listint i_list; //定义保存整数类型的链表dequedouble d_dqs; //定义保存长浮点类型的双端队列//std::cout Container construction\n;str_vec.push_back(hi);vectorstring str_vec_copy(str_vec); //拷贝构造std::cout string((str_vecstr_vec_copy)?true:false) std::endl;str_vec_copy[0]hil;std::cout string((str_vecstr_vec_copy)?true:false) std::endl;std::cout string((str_vecstr_vec_copy)?true:false) std::endl;//str_vec.push_back(adc);std::cout string((str_vecstr_vec_copy)?true:false) std::endl;vectorstring str_vec_size(2); //指定元素个数构造只适用于顺序容器,元素默认值就是元素类型默认构造vectorstring str_vec_sVal(2,hello); 指定元素个数及元素默然值构造只适用于顺序容器vectorstring str_vec_copy_it(str_vec.begin(),str_vec.end()); //拷贝构造指定复制区间[begin,end)//std::cout construction from other Container type\n;//vectorstring str_vec_sVal(2,hello); liststring slist(str_vec_sVal.begin(), str_vec_sVal.end());dequestring front(str_vec_sVal.begin(), str_vec_sVal.begin()1);//std::cout construction from other user def type\n;vectorDTest dt_vec(2,DTest()); //定义保存DTest类型的数组,大小为2指定默认值为DTest()vectorDTest dt_vec_cp(dt_vec); //拷贝构造,定义保存DTest类型的数组std::cout string((dt_vecdt_vec_cp)?true:false) std::endl;DTest dt_(10);dt_vec_cp.push_back(dt_);std::cout string((dt_vecdt_vec_cp)?true:false) std::endl;dt_ dt_vec[0];dt_vec.push_back(DTest(9));std::cout string((dt_vecdt_vec_cp)?true:false) std::endl;//std::cout construction is template arg type\n;vectorvectorstring str_vecs; //定义保存vectorstring类型的数组str_vecs.push_back(str_vec);//std::cout Container iterator type\n;vectorstring::iterator it;it str_vec.begin();//vectorstring::iterator iter_vec str_vec.begin() str_vec.size()/2; //OK//listint::iterator iter_list i_list.begin() i_list.size()/2; //error//std::cout Container comment is copy data\n;string srt_ hello;str_vec.push_back(srt_);srt_ change;str_vec.insert(str_vec.begin(),srt_);it str_vec.begin();while(it!str_vec.end()){std::cout *it std::endl;it;}//std::cout Container comment is change for iterator\n;it str_vec.begin();while(it!str_vec.end()) //循环更改了容器内容,end()可以实时指向新的{std::cout *it std::endl;if(*ithi){#ifdef WIN32it str_vec.erase(it); //error#else vectorstring::iterator it_temp it;str_vec.erase(it_temp);#endifcontinue;}it;}std::cout iterator traversing \n;it str_vec.begin();while(it!str_vec.end()){std::cout *it std::endl;it;}//std::cout Container size\n;std::cout str_vec.empty() str_vec.empty() std::endl;std::cout str_vec.size() str_vec.size() std::endl;std::cout str_vec.max_size() str_vec.max_size() std::endl;str_vec.resize(5);std::cout str_vec.size() str_vec.size() std::endl;std::cout str_vec.max_size() str_vec.max_size() std::endl;str_vec.resize(2);std::cout str_vec.size() str_vec.size() std::endl;std::cout str_vec.max_size() str_vec.max_size() std::endl;//std::cout Container comment get it\n;std::cout str_vec[0] str_vec[0] std::endl;std::cout str_vec.at(0) str_vec.at(0) std::endl;std::cout str_vec.front() str_vec.front() std::endl;std::cout *(str_vec.begin()) *(str_vec.begin()) std::endl;//std::cout Container other func test\n;str_vec.swap(str_vec_copy);std::cout str_vec.front() str_vec.front() std::endl;std::cout str_vec.back() str_vec.back() std::endl;str_vec.assign(5, Hi prfree!);std::cout str_vec.size() str_vec.size() std::endl;std::cout str_vec.front() str_vec.front() std::endl;////const int test_count 1000000;const int test_count 100;std::cout clock() clock() std::endl;for(int i0; itest_count; i){//i_list.push_back(i%3);i_list.insert(i_list.begin(),i%3);}for(int i0; itest_count; i){i_list.pop_back();}std::cout clock() clock() std::endl;vectorint i_vec;std::cout clock() clock() std::endl;for(int i0; itest_count; i){//i_vec.push_back(i%3);i_vec.insert(i_vec.begin(),i%3);}for(int i0; itest_count; i){i_vec.pop_back();}std::cout clock() clock() std::endl;//std::cout str_vec.size() str_vec.size() std::endl; //5std::cout str_vec.capacity() str_vec.capacity() std::endl;//5str_vec.push_back(test1);str_vec.push_back(test2);std::cout str_vec.size() str_vec.size() std::endl;//7std::cout str_vec.capacity() str_vec.capacity() std::endl;//10for(int i0; i10; i){str_vec.push_back(test_);}std::cout str_vec.size() str_vec.size() std::endl;//17std::cout str_vec.capacity() str_vec.capacity() std::endl;//20str_vec.reserve(30); std::cout str_vec.size() str_vec.size() std::endl;//17std::cout str_vec.capacity() str_vec.capacity() std::endl;//30str_vec.clear();std::cout str_vec.size() str_vec.size() std::endl;//0std::cout str_vec.capacity() str_vec.capacity() std::endl;//30str_vec.reserve(5); std::cout str_vec.size() str_vec.size() std::endl;//0std::cout str_vec.capacity() str_vec.capacity() std::endl;//5//string s_vec hello world;s_vec.push_back(!);string::iterator iter_s s_vec.begin();while (iter_s ! s_vec.end()){cout *iter_s; }cout \n;for(int i0; is_vec.size(); i){cout s_vec[i];}cout \n;//MyStackint i_mystack;MyStackfloat f_mystack;i_mystack.push(100);i_mystack.push(200);f_mystack i_mystack;std::cout f_mystack.top() f_mystack.top() std::endl;//priority_queueDTest pque;//push元素,注意DTest类型是数越大优先级越高pque.push(23);pque.push(15);pque.push(18);pque.push(21);while (!pque.empty()){cout pque.top().val ; pque.pop();}cout \n;return 0;
};
