STL容器（一）（附件STL帮助手册）

 

         解决STL编译警告的方法，在头文件的include代码前加上：#pragma warning (disable : 4786)

         注：disable 后边是警告代号。

一     序列

1)         vector模板类（头文件为vector,老版本为vector.h）

数组的一种类表示，可反转容器，rbegin()和rend()分别指向反转序列的第一个和超尾叠待器，类型为reverse_iterator。

1.       使用方法

                   vector属于std命名域的，因此需要通过命名限定，如下完成你的代码：

          using std::vector;

                   vector<int> vec;

                   或者连在一起，使用全名：

                   std::vector<int> vInts;

2.       vector的主要方法：

1)       向vector添加一个数据

vector添加数据的缺省方法是push_back()。push_back()函数表示将数据添加到vector的尾部，并按需要来分配内存。

2)       访问vector中的数据

使用两种方法来访问vector。

                   1、   vector::at()

                   2、   vector::operator[]

operator[]主要是为了与C语言进行兼容。它可以像C语言数组一样操作。但at()是我们的首选，因为at()进行了边界检查，如果访问超过了vector的范围，将抛出一个例外。由于operator[]容易造成一些错误，所有我们很少用它，下面进行验证一下：’

         vector<int> v;

         v.reserve(10);

         for(int i=0; i<7; i++)

              v.push_back(i);

         try

         {

                   int iVal1 = v[7];  // not bounds checked - will not throw

                   int iVal2 = v.at(7); // bounds checked - will throw if out of range

         }

         catch(const exception& e)

         {

                 cout << e.what();

}

         3)      删除vector中的数据

vector能够非常容易地添加数据，也能很方便地取出数据，同样vector提供了erase()，pop_back()，clear()来删除数据，当你删除数据的时候，你应该知道要删除尾部的数据，或者是删除所有数据，还是个别的数据。在考虑删除等操作之前让我们静下来考虑一下在STL中的一些应用。

5.      对矢量可执行的其他操作（非成员函数）

1.      or_each(iterator1,iterator2,function_name);//对矢量区间[iterator1,iterator2)中的每个元素执行函数function_name.

2.      random_shuffle(itr1,itr2);//随即排列矢量区间[iterator1,iterator2)中的元素。要求容器支持随即访问。

3.      对于基本类型，使用sort(itr1,itr2).对矢量区间[iterator1,iterator2)排序（升序）。

对于用户定义的对象（如结构体），需要定义能够处理该类型对象的成员或非成员函数{如operator <(const type & r1,const type &r2)}，再使用上述函数。

如果想按别的数据域排序，则可用sort(itr1,itr2,function_name);//function_name的返回值必须能转换成bool类型。

C++将operator++()作为重载++前缀版本，operator++(int)作为后缀版本（其中参数永远都不会用到）。

2)      deque(头文件queue，是一个适配器类)

deque 和vector一样都是标准模板库中的内容，deque 是双端队列，在接口上和vector 非常相似，在许多操作的地方可以直接替换。vector在默认情况下是典型的使用序列的方法，对于deque，当使用插入删除操作的时候是一个更好的选择。

         1.      细读上面两张表格，你会发现和vector比较这里增加了两个函数。

push_front(elem) —— 在头部插入一个数据。

pop_front() —— 删除头部数据。

相对于vector 缺少了两个函数

 capacity() —— 返回vector当前的容量。

 reserve() —— 给指定大小的vector 分配空间。

deque是大块大块地分配内存，每次插入固定数量的数据。vector是就近分配内存。

         2.      当执行大数据量的调用push_back()的时候，记住要调用vector::reserve()。

         deque分配的空间是预先分配好的，deque维持一个固定增长率，在vector实验中我们考虑到应该调用vecor::reserve().然后在下面这个例子验证了我们的假设，在使用vector的时候调用reserve()能够膀子我们预先分配空间，这将是vector一个默认选择的操作。

         3.      当你分配很多内存单元的时候，记住使用deque回收内存要比vector消耗时间多。

         在实验三中我们探讨了vector和deque在回收非邻接内存块上的不同，分别证明了vector在分配内存的时候是线性增长，而deque是指数增长，同样，vector要回收的内存比deque多的多，如果你循环调用了push_back()，那么deque将获取大量的内存，而且是临近的。我们通过测试发现在分配内存单元消耗的时间和vector的时间接近。

         4.      如果你计划使用insert()，或者需要pop_front()，那就使用deque。

         5.      对于访问数据，vector::at()效率最高。

3)      list(头文件list，双向链表，可反转容器)

         在任一位置的插入和删除的时间都是固定的，不能随记存取。

         与失量迭代器不一样，从容器中插入和删除元素后，迭代器所指向的元素不变。

         常用成员函数：

函数	说明
void merge<list<T, Alloc>&x>	将都已经排序的链表x合并到调用链表中，并且排序，x为空。时间复杂度为线性时间。
void remove(const T & val)	从链表中删除val的所有实例。线性时间。
void sort()	使用<操作符对列表排序。时间复杂度为：NlogN
void splice(iterator pos, list<T, Alloc> x)	将链表x的内容插入到pos的前面，x将为空。固定时间。
void unique()	将连续相同的元素压缩为单个元素。线性时间。

说明:                   splice()方法执行后，迭代其仍然有效。unique()只能将相邻的相同值压缩为单个值。若想每个值占一个位置，应先sort（）后再调用unique().

         非成员函数，要求随即访问迭代器，所以不能用于链表中。

4)  queue（头文件queue，是一个适配器类）

         操作：

方法	说明
bool empty() const	队列为空，返回true，否则返回false
size_type size() const	返回队列中元素的数目
T& front()	返回指向队首元素的引用
T& back()	返回指向队尾元素的引用
void push(const T& x)	在队尾插入x
void pop()	删除队首元素

5)  priority_queue(头文件queue,默认的底层类是vector)

         最大的元素被移到队首。

         使用方法：        priority_queue<int> pq1             priority_queue(<greater<int>>)

         greater<>()是一个欲定义的函数对象，确定哪个元素放到队首的比较方式。

6)  stack(头文件stack,底层类vector，是一个适配器类)

         基本操作：

方法	说明
bool empty() const	如果堆栈为空，则返回true；否则返回false
size_type size() const	返回堆栈中的元素数目
T& top()	返回指向栈顶元素的引用
void pop()	删除栈顶元素
void push(const T& x)	在堆栈顶部插入x

 

续：STL容器（2）