二、STL容器：容器总结以及vector和list

1 容器简介 1.1 容器 1.1.1 顺序容器

容器	模板	特点
向量容器	vector	从后面快速插入与删除，可以直接访问任何元素。
双向列表容器	list	从任何地方快速插入与删除
双端链表容器	deque	从前面或者后面快速插入与删除，可以直接访问任何元素。

1.1.2 关联容器

容器	模板	特点
映射容器	map	一对多映射，基于关键字快速查找，不允许重复值
多重映射容器	multimap	一对多映射，基于关键字快速查找，允许重复值
集合容器	set	快速查找，不允许重复值
多重集合容器	multiset	快速查找，允许重复值

1.1.3 容器适配器

容器	模板	特点
栈容器	stack	后进先出(LIFO)
队列容器	queue	先进后出(FIFO)
优先级队列容器	priority_queue	最高优先级元素先出

1.2 容器通用操作 1.2.1 实例化

实例化方式	作用	顺序容器	关联容器	容器适配器
C c	默认构造	√	√	√
C c(c1)	复制构造	√	√	√
C c(it_b,it_e)	范围构造	√	√	√
C c(n,t)	填充构造	√	×	×
C c(n)	初始化大小	√	×	×

1.2.2 重载运算符

运算符	作用	顺序容器	关联容器	容器适配器
=	赋值	√	√	√
==	比较	√	√	√
<	小于	√	√	√

1.2.3 迭代器

迭代器	作用	顺序容器	关联容器	容器适配器
c.begin()	头迭代器	√	√	×
c.end()	尾迭代器	√	√	×
c.rbegin()	反向头迭代器	√	√	×
c.rend()	反向尾迭代器	√	√	×

1.2.4 大小

函数	作用	顺序容器	关联容器	容器适配器
c.size()	大小	√	√	√
c.max_size()	最大大小	√	√	×
c.empty()	判空	√	√	√

1.2.5 插入

函数	返回值	作用	顺序容器	关联容器	容器适配器
c.insert(p,t)	iterator	插入一个元素	√	×	×
c.insert(p,n,t)	void	插入n个连续元素	√	×	×
c.insert(p,it_b,it_e)	void	插入范围元素	√	×	×
c.insert(t)	iterator/pair	插入元素	×	√	×
c.insert(it_b,it_e)	void	插入范围元素	×	√	×

1.2.6 删除

函数	返回值	作用	顺序容器	关联容器	容器适配器
c.erase(p)	iterator	删除指定位置元素(注意返回值是iterator)	√	×	×
c.erase(p,q)	iterator	删除指定[p,q)范围连续元素(注意返回值是iterator)	√	×	×
c.erase(k)	size_type	删除指定键值的元素	×	√	×
c.erase(p)	void	删除指定位置元素(注意返回值是void)	×	√	×
c.erase(p,q)	void	删除指定[p,q)范围连续元素(注意返回值是void)	×	√	×
c.clear()	void	删除所有元素	√	√	×

1.3 容器特有操作 1.3.1 顺序容器特有函数

1、访问元素

函数	返回值	作用	vector	list	deque
c.front()	元素	获取第一个元素	√	√	√
c.back()	元素	获取最后一个元素	√	√	√
c.push_back(t)	void	底部添加一个元素	√	√	√
c.pop_back()	void	底部删除一个元素	√	√	√
c.push_front(t)	void	头部添加一个元素	×	√	√
c.pop_front()	void	头部删除一个元素	×	√	√
c[n]/c.at(n)	元素	随机获取元素	√	×	√

2、赋值/扩展

函数	返回值	作用	vector	list	deque
c.assign(n,t)	void	多个连续赋值	√	√	√
c.assign(it_b,it_e)	void	范围赋值	√	√	√
c.resize(n)	void	大小扩展到n	√	√	√
c.resize(n,t)	void	扩展并赋值	√	√	√

1.3.2 关联容器特有查找函数

函数	返回值	作用	map	multimap	set	multiset
c.find(k)	iterator	查找	√	√	√	√
c.count(k)	size_type	统计	√	√	√	√
c.upper_bound(k)	iterator	小于或等于k的第一个元素位置	√	√	√	√
c.equal_bound(k)	pair	等于k的开始和结束位置	√	√	√	√
c.key_comp()	key_compare	键比较	√	√	√	√
c.value_comp()	value_compare	值比较	√	√	√	√

1.3.3 容器适配器特有函数

函数	返回值	作用	stack	queue	priority_queue
c.push(t)	void	压入元素	√	√	√
c.pop()	void	弹出元素	√	√	√
c.top()	元素	顶部元素	×	√	√
c.front()	元素	头部元素	√	×	×
c.back()	元素	底部元素	√	×	×

注：容器适配器不支持迭代器

1.3.4 list特有函数

截取splice
删除remove
去重unique
合并merge
排序reverse
反转sort

1.5 其他 1.5.1 字符串

1.5.2 C++11增加容器

1.6 实例分析

实例1：vector和list

#include 
using namespace std;
int main(){
    vector vec = {1,3,2,6,4,5,3,2,6,11};
    auto it = vec.begin();
    vec.erase(it+1,it+4); //删除[it+1,it+4)之间的元素,半开半闭
    for(auto n:vec){
        cout << n << " ";
    }
    cout << endl;
    //逆序迭代
    for(auto rit = vec.rbegin();rit != vec.rend();++rit){
        cout << *rit << " ";
    }
    cout << endl;
    //插入
    vec.insert(vec.begin(),5,100);
    for(auto n:vec){
        cout << n << " ";
    }
    cout << endl;

    list li(vec.begin()+5,vec.end()-2);
    for(auto n:li){
        cout << n << " ";
    }
    cout << endl;
    //排序
    li.sort();
    for(auto n:li){
        cout << n << " ";
    }
    cout << endl;
}

1 4 5 3 2 6 11 
11 6 2 3 5 4 1 
100 100 100 100 100 1 4 5 3 2 6 11 
1 4 5 3 2 
1 2 3 4 5

实例2：vector和list

#include 
#include 
#include 
#include 
using namespace std;
int main(){
    int arr[] = {1,4,5,2,3};
    //数组下标访问
    for(int i = 0;i < sizeof(arr)/sizeof(int);++i){
    	cout << arr[i] << " ";
    }
    cout << endl;
    //字符串下标访问
    const char* str = "abcde";
    for(int i = 0;i < strlen(str);++i){
    	cout << str[i] <<  " ";
    }
    cout << endl;
    //字符串指针遍历
    const char* p = str;
    while(*p){
    	cout << *p++ << " ";
    }
    cout << endl;

    //容器
    vector vec = {1,4,5,2,3};
    //数组下标方式遍历
    for(int i = 0;i < vec.size();++i){
    	cout << vec[i] << " ";
    }
    cout << endl;
    //迭代器遍历,迭代器可以看作一种特殊的指针，支持解引用和++操作
    vector::iterator it = vec.begin();
    while(it != vec.end()){
    	cout << *it++ << " ";
    }
    cout << endl;

    cout << "const:";
    vector::const_iterator cit = vec.cbegin();
    while(cit != vec.cend()){
    	cout << *cit++ << " ";
    }
    cout << endl;

    //C++11基于范围的for循环
    cout << "C++11基于范围:";
    for(auto n:arr){
        cout << n << " ";
    }
    cout << endl;

    for(auto n:vec){
    	cout << n << " ";
    }
    cout << endl;
    
    //list链表
    //可以用vector初始化list
    list vec_li(vec.begin(),vec.end()); 
    for(auto n:vec_li){
    	cout << n << " ";
    }
    cout << endl;
    list li = {1,2,3,4,5}; //C++11特有的初始化方式
    for(auto it=li.begin();it != li.end();++it){
    	cout << *it  << " ";
    }
    cout << endl;
    //删除
    list::iterator list_it = li.begin();
    ++list_it;
    li.erase(list_it);
    for(auto n:li){
    	cout << n << " ";
    }    
    cout << endl;
}

1 4 5 2 3 
a b c d e 
a b c d e 
1 4 5 2 3 
1 4 5 2 3 
const:1 4 5 2 3 
C++11基于范围:1 4 5 2 3 
1 4 5 2 3 
1 4 5 2 3 
1 2 3 4 5 
1 3 4 5

实例3：使用vector实现带有增删查改的学生管理系统

#include 
#include 
#include 
#include 
using namespace std;
class Student{
    string name;
    int age;
    float score;
public:
    Student():name(),age(0),score(0){}
    Student(const string& name,int age,float score):name(name),age(age),score(score){}
    string GetName()const{
        return name;
    }
    friend ostream& operator<<(ostream& os,const Student& s){
    	return os << s.name << " " << s.age << " " << s.score << endl;
    }
    friend istream& operator>>(istream& is,Student& s){
    	return is >> s.name >> s.age >> s.score;
    }
};
class StudentInfo{
    vector vec;
public:
    void Load(const string& path){
    	ifstream fin(path,ios::in);
	    Student s;
	    while(fin >> s){
	    	vec.push_back(s);
	    }
	    fin.close();
    }
    void Append(Student s){
    	vec.push_back(s);
    }
    void Save(const string& path){
    	ofstream fout(path,ios::out);
    	for(int i = 0;i < vec.size();++i){
	   cout << vec[i];
	   fout << vec[i];
	}
	fout.close();
    }
    Student SearchStudent(const string& name)const{
    	for(int i = 0;i < vec.size();++i){
	    if(vec[i].GetName() == name){
	    	return vec[i];
	    }
	}
	
	return Student();
    }
    bool UpdataStudent(Student s){
    	for(int i = 0;i < vec.size();++i){
	    if(vec[i].GetName() == s.GetName()){
	    	vec[i] = s;
		return true;
	    }
	}
	return false;
    }
    bool DeleteStudent(const string& name){
	
	vector::iterator it = vec.begin();
	//auto it = vec.begin();
	while(it != vec.end()){
	    if(it->GetName() == name){
	    	vec.erase(it);
		return true;
	    }
	    ++it;
	}
	return false;
    }
    friend ostream& operator <<(ostream& os,StudentInfo& si){
    	os << "姓名 年龄 成绩" << endl;
	for(int i = 0;i < si.vec.size();++i){
	    os << si.vec[i];
	}
	return os;
    }
};
int main(){
    StudentInfo info;
    string path = "./Student";
    info.Load(path);
    const char* item[] = {
    "查看学生信息",
    "添加学生信息",
    "查找学生信息",
    "修改学生信息",
    "删除学生信息",
    "退出",
    };
    while(true){
    	for(int i = 0;i < sizeof(item)/sizeof(item[0]);i++){
            cout << i+1 << "." << item[i] << endl;
    	}
	cout << "请输入选择：";
	int num;
	cin >> num;
	switch(num){
	    case 1:
  		 cout << info;
		 break;
	    case 2:{
		Student s;
		cout << "请依次输入学生姓名、年龄、成绩:";
		cin >> s;
		info.Append(s);
		info.Save(path);
  		break;
 	    }
	    case 3:{
		cout << "请输入姓名：";
		string name;
		cin >> name;
		Student s = info.SearchStudent(name);
		if(s.GetName().empty()){
		    cout << "没找到:" << name << endl;
		}else{
		    cout << s;
		}
  		break;
	    }
	    case 4:{
		cout << "请依次输入学生姓名、年龄、成绩:";
		Student s;
		cin >> s;
  		if(info.UpdataStudent(s)){
		    cout << "修改成功" << endl;
		    info.Save(path);
		}else{
		    cout << "未找到：" << s.GetName() << endl;
		}
		break;
	    }
	    case 5:{
	 	cout << "请输入删除学生姓名：";
	        string name;
		cin >> name;
		if(info.DeleteStudent(name)){
		    cout << "删除成功" << endl;
		    info.Save(path);
		}else{
		    cout << "未找到：" << name << endl;
		}
		break;
	    }
	    case 6:
		return 0;
	}
    }
}

实例4：使用list实现带有增删查改的学生管理系统

#include 
#include 
#include 
#include 
using namespace std;
class Student{
    string name;
    int age;
    float score;
public:
    Student():name(),age(0),score(0){}
    Student(const string& name,int age,float score):name(name),age(age),score(score){}
    string GetName()const{
        return name;
    }
    friend ostream& operator<<(ostream& os,const Student& s){
    	return os << s.name << " " << s.age << " " << s.score << endl;
    }
    friend istream& operator>>(istream& is,Student& s){
    	return is >> s.name >> s.age >> s.score;
    }
};
class StudentInfo{
    list vec;
public:
    void Load(const string& path){
    	ifstream fin(path,ios::in);
	    Student s;
	    while(fin >> s){
	    	vec.push_back(s);
	    }
	    fin.close();
    }
    void Append(Student s){
    	vec.push_back(s);
    }
    void Save(const string& path){
    	ofstream fout(path,ios::out);
	
	list::iterator it = vec.begin();
	while(it != vec.end()){
	    fout << *it;
	    ++it;
	}
	fout.close();
    }
    Student SearchStudent(const string& name)const{
    	
	list::const_iterator it = vec.cbegin();
	while(it != vec.cend()){
	    if(it->GetName() == name){
	    	return *it;
	    }
	    ++it;
	}
	return Student();
    }
    bool UpdataStudent(Student s){
	
	list::iterator it = vec.begin();
	while(it != vec.end()){
	    if(s.GetName() == it->GetName()){
	    	*it = s;
	    }
	    it++;
	    return true;
	}
	return false;
    }
    bool DeleteStudent(const string& name){
	
	list::iterator it = vec.begin();
	//auto it = vec.begin();
	while(it != vec.end()){
	    if(it->GetName() == name){
	    	vec.erase(it);
		return true;
	    }
	    ++it;
	}
	return false;
    }
    friend ostream& operator <<(ostream& os,StudentInfo& si){
    	os << "姓名 年龄 成绩" << endl;
	
	list::iterator it = si.vec.begin();
	while(it != si.vec.end()){
 	    os << *it++;
	}
	return os;
    }
};
int main(){
    StudentInfo info;
    string path = "./Student";
    info.Load(path);
    const char* item[] = {
    "查看学生信息",
    "添加学生信息",
    "查找学生信息",
    "修改学生信息",
    "删除学生信息",
    "退出",
    };
    while(true){
    	for(int i = 0;i < sizeof(item)/sizeof(item[0]);i++){
            cout << i+1 << "." << item[i] << endl;
    	}
	cout << "请输入选择：";
	int num;
	cin >> num;
	switch(num){
	    case 1:
  		 cout << info;
		 break;
	    case 2:{
		Student s;
		cout << "请依次输入学生姓名、年龄、成绩:";
		cin >> s;
		info.Append(s);
		info.Save(path);
  		break;
 	    }
	    case 3:{
		cout << "请输入姓名：";
		string name;
		cin >> name;
		Student s = info.SearchStudent(name);
		if(s.GetName().empty()){
		    cout << "没找到:" << name << endl;
		}else{
		    cout << s;
		}
  		break;
	    }
	    case 4:{
		cout << "请依次输入学生姓名、年龄、成绩:";
		Student s;
		cin >> s;
  		if(info.UpdataStudent(s)){
		    cout << "修改成功" << endl;
		    info.Save(path);
		}else{
		    cout << "未找到：" << s.GetName() << endl;
		}
		break;
	    }
	    case 5:{
	 	cout << "请输入删除学生姓名：";
	        string name;
		cin >> name;
		if(info.DeleteStudent(name)){
		    cout << "删除成功" << endl;
		    info.Save(path);
		}else{
		    cout << "未找到：" << name << endl;
		}
		break;
	    }
	    case 6:
		return 0;
	}
    }
}

二、STL容器：容器总结以及vector和list

C/C++/C#相关栏目本月热门文章