C++中STL容器的分类和基本功能（一）：向量(vector) 双端队列(deque) 列表(list)

我就是我 2024-04-17 05:33 50阅读 0赞

# 容器的分类与基本功能 #

## 七种基本容器 ##

*  ### 向量(vector) ###
 *  ### 双端队列(deque) ###
 *  ### 列表(list) ###
 *  ### 集合(set) ###
 *  ### 多重集合(multiset) ###
 *  ### 映射(map) ###
 *  ### 多重映射(multimap) ###

## 按容器中元素的组织方式 ##

*  ### 顺序容器 ###
 *  ### 关联容器 ###

## 按与容器相关的迭代器类型 ##

*  ### 可逆容器 ###
 *  ### 随机访问容器 ###

##    容器的通用功能 ##

*  vector<int> s1,s2;   //使用默认构造函数构造空容器
 *  s1 == s2;    //支持关系运算符： == 、!=、<、<=、>、>=
 *  s1.begin(); s1.end(); //获得容器首、尾迭代器
 *  s1.clear(); //将容器清空
 *  s1.empty(); //判断容器是否为空
 *  s1.size(); //得到容器元素个数
 *  s1.swap(s2); //将s1和s2两容器内容交换

##    随机访问容器 ##

*  s\[n\] //获得容器s的第n个元素

##    相关迭代器类型（s 表示容器类型） ##

*  s::iterator //指向容器元素的迭代器类型
 *  s::const\_iterator //常迭代器类型 一经初始化便无法修改

## 可逆（双向）容器的功能 ##

*  s::reverse\_iterator //双向迭代器类型
 *  s::const\_reverse\_iterator //逆向常迭代器类型
 *  rbegin() //指向容器尾的逆向迭代器
 *  rend() //指向容器首的逆向迭代器

### 例： ###

> copy(s.begin(), s.end(), ostream\_iterator<int>(cout, " "));  
> copy(s.rbegin(), s.rend(), ostream\_iterator<int>(cout, " "));

##    顺序容器通用功能 ##

### **构造：** ###

*  S s(n,t);  //构造一个由n个t元素构成的容器实例s
 *  S s(n);  //构造一个有n个元素的容器实例s，每个元素都是T()
 *  S s(q1,q2);  //使用将\[q1,q2)区间内的数据作为s的元素构造s

### 赋值： ###

*  s.assing(n,t); //赋值后的容器由n个t元素构成  
 *  s.assing(n);  //赋值后的容器由n个元素，每个元素都是T()
 *  s.assing(q1,q2);赋值后的容器为\[q1,q2)区间内的数据

### 插入：  ###

*  s.insert(p1,t);  //在容器s中p1所指向的位置插入一个新的元素t，该函数会返回一个迭代器指向新插入的元素
 *  s.insert(p1,n,t);  //在容器s中p1所指向的位置插入n个新的元素t，没有返回值
 *  s.insert(p1,q1,q2);  //将\[q1,q2)区间内的元素顺序插入到s容器中p1位置处。
 *  s.push\_front(t); s.push\_front(); //在容器前插入一个元素，对list 和 deque使用
 *  s.push\_back(t); s.push\_back();  //在容器后插入一个元素，对list 和 deque使用

### 删除： ###

*  s.erase(p1);  //删除s1容器中p1所指向的元素，返回被删除的下一个元素的迭代器
 *  s.erase(p1,p2);  //删除s1容器中\[p1,p2)区间内元素，返回最后一个被删除元素的下一个元素的迭代器
 *  s.erase();
 *  s.clear();
 *  s.pop\_front();  //取出前面第一个的元素，对list和deque 使用 
 *  s.pop\_back();  //取出最后面的元素，对list和deque 使用

### 首尾元素直接访问： ###

*  s.front(); s.back();  //返回引用

### 改变大小： ###

*  s.resize(n);  //将容器的大小变为n，如果原有的元素个数大于n，则容器末尾多余的元素会被删除；如果原油的元素个数小于n，则在容器的末尾会用T()填充

## /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/ ##

## 向量vector ##

###    特点： ###

*  一个可以扩展的动态数组
 *  随机访问容器
 *  在头部插入速度较慢，在尾部插入速度较快，容器内存连续，在头部插入要修改n个内存。

### 向量的容量： ###

**容量(capacity)：实际分配空间的大小**

*  s.capacity();  //发挥当前容量
 *  s.reserve(n);  //若容量小于n，则对s进行扩展，使其容量至少为n

#include <stdlib.h>
    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    using namespace std;
     
    int main()
    {
    	const int N = 5;
    	vector<int> s;
    	s.reserve(3);
    	cout << s.capacity() << endl; 
    	cout << s.size() <<endl;
    	for(int i = 0; i < N; i++)
    	{
    		s.push_back(i);
    	}
    	s.insert(s.begin() + 3, 9);
    	copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
    	cout << endl;
    	s.pop_back();
    	copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
    	cout << endl;
    	
    	system("pause");
    	return 0;
    }

输出： 3  
0  
0 1 2 9 3 4  
0 1 2 9 3  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

## 双端队列(deque) ##

### 特点： ###

*  在两端插入或删除元素较快
 *  在中间插入或删除元素较慢
 *  随机访问较快，但是比向量容器慢

### 存储结构： ###

*  数组
 *  分段数组

例：奇偶排序  
先按照从大到小顺序输出奇数，再按照从小到大顺序输出偶数

#include <stdlib>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <iterator>
    using namespace std;
     
    int main()
    {
    	istream_iterator<int> i1(cin), i2;
    	vector<int> s1(i1, i2);
    	sort(s1.begin(), s1.end());
    	copy(s1.begin(), s1.end(), ostream_iterator<int>(cout, " "));
    	cout << endl;
    	deque<int> s2;
    	for(vector<int>::iterator iter = s1.begin(); iter != s1.end(); iter++)
    	{
    		if(*iter % 2 == 0)
    		{
    			s2.push_back(*iter);
    		}
    		else
    		{
    			s2.push_front(*iter);
    		}
    	}
    	copy(s2.begin(), s2.end(), ostream_iterator<int>(cout, " "));
    	cout << endl;
    	
    	system("pause");
    	return 0;
    }

输出： 1 4 3 2 7 6 5   
^Z                               //此处的为 CTRL+Z表示结束符  
1 2 3 4 5 6 7  
7 5 3 1 2 4 6  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

### 列表(list) ###

### 特点： ###

*  再任意位置插入和删除元素都很快
 *  不支持随机访问

结合(splice)操作：  
s1.splice(p ,s2, q1, q2);  //将s2中\[q1,q2)移动到s1中p所指向元素之前

#include <stdlib>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <list>
    #include <iterator>
    using namespace std;
     
    int main()
    {
    	string names1[] = {"A", "B", "C", "D"};
    	string names2[] = {"E", "F", "G", "H"};
    	list<string> s1(names1, names1 + 4);
    	list<string> s3(names2, names2 + 4);
    	
    	s2.splice(s2.end(), s1, s1.begin());
    	//s1:B C D    s2:E F G H A
    	copy(s1.begin(), s1.end(), ostream_iterator<string>(cout, " "));
    	cout << endl;
    	copy(s2.begin(), s2.end(), ostream_iterator<string>(cout, " "));
    	cout << endl;
    	
    	list<string>::iterator iter1 = s1.begin();
    	advance(iter1, 2);
    	list<string>::iterator iter2 = s2.begin();
    	++iter2;
    	list<string>::iterator iter3 = s3.begin();
    	s1.splice(iter1, s2, iter2, iter3);  //s1:B C D
    	copy(s1.begin(), s1.end(), ostream_iterator<string>(cout, " "));
    	cout << endl;
    	copy(s2.begin(), s2.end(), ostream_iterator<string>(cout, " "));
    	cout << endl;
    	
    	system("pause");
    	return 0;
    }

输出： B C D  
E F G H A  
B C D  
E F G H A

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

### 三种顺序容器的比较 ###

*  如果需要执行大量的随机访问操作，而且当扩展容器时只需要向容器尾部加入新的元素，就应当选择向量容器(vector)
 *  如果需要少量的随机访问操作，需要在容器两端插入或删除元素，则应当选择双端队列容器(deque)
 *  如果不需要对容器进行随机访问，但是需要在中间位置插入或者删除元素，就应当选择列表容器(list)