C++ -- STL常用容器

STL常用容器整理

string容器

string的基本概念string构造函数string的赋值操作string字符串拼接string中的查找和替换string字符串的比较string字符存取string字符串的插入和删除string字串 vector容器

vector基本概念vector构造函数vector赋值操作vector容量和大小vector的插入和删除vector容器中的数据存取vector互换容器vector预留空间 deque容器

deque容器的构造函数deque容器的赋值操作deque容器的大小操作deque容器中的插入和删除deque容器的数据存取 stack容器

stack基本概念stack的常用接口 queue容器

queue容器的概念queue的常用接口 list容器

list基本概念list构造函数list容器的赋值和交换list容器的大小操作list容器的插入和删除list容器的数据存取list容器中的反转和排序 set和multiset容器

set基本概念set容器的构造和赋值set容器的大小和交换set容器的插入和删除set容器中的查找和统计pair对组的创建set容器的排序 map和multimap容器

map基本概念map构造和赋值map容器的大小和交换map容器中的插入和删除map容器中的查找和统计map容器中的排序

---

string容器 string的基本概念

本质：string是C++风格的字符串，而string的本质是一个类

string与char*的区别：

char*是一个指针；string是一个类，类内部封装了char*，管理这个字符串，是一个char*型的容器；

特点：

string类内部封装了很多成员函数，如查找find，删除delete，替换replace，插入insert等；string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责；

---

string构造函数

构造函数原型：

string(); //创建一个空字符串，例如：string strstring(const char* s); //使用字符串s初始化；string(const string& str); //使用一个string对象的初始化另一个string对象string(int n,char ch); //使用n个字符ch初始化

---

string的赋值操作

函数原型：

string& operator=(const char * s); //char*类型字符串 赋值给当前的字符串；string& operator=(const string &s); //把字符串s赋给当前的字符串string& operator=(char c); //字符赋值给当前的字符串string& operator=(const char * s); //把字符串s赋给当前的字符串string& operator=(const char * s,int n);//把字符串s的前n个字符赋给当前字符串string& operator=(const string &s); //把字符串s赋值给当前字符串string& operator=(int n, char c); //把n个字符赋值给当前字符串

---

string字符串拼接

函数原型：

string& operator+=(const char * s);string& operator+=(const string &s);string& operator+=(char c);string& append(const char * s);string& append(const char * s,int n);//连接前n个string& append(const string &s);string& append(int n, char c);string& append(const string &s,int pos,int n)//将字符串s从pos位置开始截取n个；

---

string中的查找和替换

注意replace的使用：该方法可能会使得字符串长度增加，例子如下：

#include 
#include 
using namespace std;

void test01() {
	string str = "abcdefg";
	str.replace(1, 3, "00000");
    //从1号位置其，将其三个字符替换为00000
	cout << str;
}

int main() {
	test01();
	return 0;
}

---

string字符串的比较

作用：比较字符串是否相等；比较方式：按字符的ASCII码值进行对比；

= 返回 0；> 返回 1；< 返回 -1； 函数原型：

void compare(const string &s) const;void compare(const char * s) const;

---

string字符存取 string中单个字符的存取方式有两种：

char& operator[](int n);char& at(int n);

---

string字符串的插入和删除

函数原型：

string& insert(int pos,const char* s);//插入字符串string& insert(int pos,const string& str);//插入字符串string& insert(int pos,int n,char c);//在指定位置插入单个字符string& erase(int pos,int n = npos);//删除从pos开始的n个字符 注意：插入和删除的起始下标都是从0开始的；

---

string字串

功能：从字符串中截取相应的字串函数原型：string substr(int pos = 0,int n = npos) const;

返回由pos开始的n个字符组成的字符串；

---

vector容器 vector基本概念

功能：vector 数据结构和数组非常相似，也称为单端数组；vector与普通数组的区别：数组是静态空间，而vector是动态空间；动态扩展：并不是在原空间之后续接的新空间，而是找更大的内存空间，然后将元数据拷贝新空间，释放原空间；

---

vector构造函数

功能描述：创建vector容器；函数原型：

vector v;//采用模板创建一个vector容器，使用默认构造；vector(v.begin(),v.end());//将[v.begin(),v.end())区间中的元素拷贝给本身；vector(n,elem);//构造函数将n个elem拷贝给本身；vector(const vector &vec);//拷贝构造函数；

---

vector赋值操作

功能描述：给vector容器进行赋值函数原型：

vector& operator=(const vector &vec;)//重载等号操作符；assign(begin,end);//将[begin，end)区间中的数据拷贝赋值给本身；assign(n,elem);//将n个elem拷贝赋值给本身；

---

vector容量和大小

作用：对vector容器的容量和大小操作；

大小是容器中元素的个数；容量永远大于等于大小； 函数原型：

empty();//判断容量是否为空 – 返回true为空，否则非空；capacity();//容器的容量；size();//返回容器中元素的个数；resize(int num);//重写指定容器的长度为num，若容器变长，则默认值（0）填充新位置。如果容器变短，则末尾超粗容器长度的元素被删除。resize(int num,elem);//重新指定容器的长度为num ，若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除；

---

vector的插入和删除

函数原型：

push_back(ele); //尾部插入元素ele；pop_back(); //删除最后一个元素；insert(const_iterator pos,ele);//迭代器指向位置pos插入元素ele;insert(const_iterator pos,int count,ele);//迭代器指向位置为pos插入count个元素ele；erase(const_iterator pos); //删除迭代器指向的元素；erase(const_iterator start,const_iterator end);//删除迭代器从start到end之间的元素；clear(); //删除容器中所有的元素；

---

vector容器中的数据存取

目的：对vector容器中的数据进行存取操作；函数原型：

  at(int idx); //返回索引idx所指的数据；-- v.at(idx);

  operator[]; //返回索引idx所指的数据；

  front(); //返回容器中第一个数据元素；

  back(); //返回容器中最后一个数据元素；

---

vector互换容器

功能：实现两个容器内元素进行互换；函数原型：swap(vec); //将vce容器与本身的元素进行交换；

利用resize();重新指定大小的时候，容器的容量不会改变，会造成内存浪费，这时可以利用swap();来收缩内存；语法：vector(v).swap(v);说明：

此处的v是利用resize();重新指定大小的容器；vector(v)是利用创建匿名对象；

原理：利用swap()交换对象元素之后，预期得到的v容器将容量缩小到和大小一样，而匿名对象由于C++的语法机制，在执行完当前行代码之后，操作系统会帮我们直接释放掉该匿名对象的空间，防止内存浪费；

---

vector预留空间

功能描述：减少vector在动态扩展容量时的扩展次数；函数原型：reserve(int len); //容器预留 len 个元素长度，预留位置不初始化，元素不可访问；

#include 
#include 
using namespace std;

void test01() {
	vector v;
	int num = 0;
	int *p = NULL;
	for(int i = 0; i<10000; i++) {
		v.push_back(i);
		if(p != &v[0]) {
			p = &v[0];
			num++;
		}
	}
	cout<<"未预留空间："< v;
	//预留空间
	v.reserve(10000); 
	
	int num = 0;
	int *p = NULL;
	for(int i = 0; i<10000; i++) {
		v.push_back(i);
		if(p != &v[0]) {
			p = &v[0];
			num++;
		}
	}
	cout<<"预留空间："< 
 
deque容器 
deque容器基本概念
 
功能：双端数组，可以对头端进行插入删除操作；deque和vector区别： 
  
vector对于头部的插入和删除效率低，数据量越大，效率越低； 
    
vector头部插入删除时需要移动元素； deque相对而言，头部的插入删除速度会比vector快；vector访问元素时的速度会比deque快，这和两者内部实现有关； deque内部工作原理： 
  
deque内部有个中控器，维护每段缓冲区中的内容，缓冲区存放真实数据；中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的区域；
  deque容器的迭代器也是支持随机访问的； 
 
deque容器的构造函数 
功能描述：deque容器构造；函数原型： 
  
deque deqT; //默认构造函数；deque(d1.begin(),d1.end()); //构造函数将[begin,end)区间中的 元素拷贝给本身；deque(n,elem); //构造函数将n个elem拷贝给本身；deque(const deque &deq); //拷贝构造函数  
 
deque容器的赋值操作 
功能描述：给deque容器进行赋值；函数原型： 
  
deque& operator=(const deque &deq); //重载等号操作符assign(d1.begin(),d1.end())//将该区间中的数据拷贝赋值给本身；assign(n,elem); //将n个elem拷贝赋值给本身；  
 
deque容器的大小操作 
功能：对大小进行操作；函数原型： 
  
deque.empty(); //判断容器是否为空；deque.size(); //返回容器中元素的个数；deque.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出长度的元素被删除；deque.resize(num,elem); //重新指定容器的长度，若容器的长度变长，则以elem值填充；长度变短，则删除超过容器长度的元素； deque容器没有容量的概念； 
 
deque容器中的插入和删除 
功能：向deque容器中插入和删除数据；函数原型： 
  
两端插入操作： 
    
push_back(elem); //在容器尾部添加一个元素；push_front(elem); //在容器头部添加一个元素；pop_back(); //删除容器最后一个元素；pop_front(); //删除容器第一个元素； 指定位置操作： 
    
insert(pos,elem); //在pos位置插入一个elem元素的拷贝 并返回新数据的位置；insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值insert(pos,beg,end); //在pos位置插入区间数据，无返回值；clear(); //清空容器数据；erase(beg,end); //删除区间数据，返回下一个数据的位置；erase(pos); //删除pos位置的数据，返回下一个数 据的位置；   
 
deque容器的数据存取 
函数原型： 
  
at(int idx); //返回索引idx所指的数据；-- d.at(idx);operator[]; //返回索引idx所指的数据；front(); //返回容器中第一个数据元素；back(); //返回容器中最后一个数据元素；  
 
stack容器 
stack基本概念 
 
概念：stack是一种先进后出（First in Last Out,FILO）的数据结构，它只有一个出口；
  
栈中只有栈顶的元素可以被外界使用，因此栈不允许有遍历行为；
  
可以判断是否为空；
  
可以返回元素个数 – 进一个元素，计数一次；
  
 
stack的常用接口 
功能描述：栈容器常用的对外接口；构造函数： 
  
stack stk; //stack采用模板类实现，stack对象的默认构造形式；stack(const stack &stk); //拷贝构造函数 赋值操作： 
  
stack& operator=(const stack &stk); //重载等号操作符 数据存取： 
  
push(elem); //向栈顶添加元素pop(); //从栈顶移除元素top(); //返回栈顶元素 大小操作： 
  
empty(); //判断堆栈是否为空size(); //返回栈大小  
 
queue容器 
queue容器的概念 
 
Queue是一种先进先出（first in first out）的数据机构，它有两个出口；
  
队列容器允许从一端新增元素，从另一端移除元素。
  
队列只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为；
  
队列中进数据称为 – 入队push
  
队列中出数据称为 – 出队pop
  
 
queue的常用接口 
功能：栈容器常用的对外接口构造函数： 
  
queue que; //queue采用模板类实现，queue对象的默认构造形式queue(const queue &que); //拷贝构造函数 赋值操作： 
  
queue& operator=(const queue &que);//重载等号操作符 数据存取： 
  
push(elem); //往队尾添加元素pop(); //从队头移除一个元素back(); //返回最后一个元素front(); //返回第一个元素 大小操作： 
  
empty(); //判断堆栈是否为空size(); //返回栈的大小  
 
list容器 
list基本概念 
 
功能：对数据进行链式存储；
  
说明：
 
  
List是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针实现的；链表的组成：链表由一系列结点组成；结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域；STL中的链表是一个双向循环链表；  
链表中的迭代器
 
  
 
由于链表的存储方式是非连续，因此链表list中的迭代器只支持前移后移；
  
属于双向迭代器；
   
链表的优点：
  
采用动态存储分配，不会造成内存浪费和溢出；链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素；
 
链表缺点： 
链表灵活，但是空间非连续，访问速度较慢；
 
补充：链表有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的；总结：STL中list和vector是两个最常被使用的容器，各有优缺点； 
 
list构造函数 
函数原型： 
  
list l; //list采用模板类实现，对象的默认构造形式list(beg,end); //构造函数将该区间内中的元素拷贝给本身list(n,elem); //构造函数将n个elem元素拷贝给本身list(const list &l); //拷贝构造函数
  
 
list容器的赋值和交换 
函数原型： 
  
assign(beg,end); //将区间中的数据拷贝赋值给本身assign(n,elem); //将n个elem拷贝赋值给本身list& operator=(const list &list);//重载等号操作符swap(list); //将list与本身的元素互换
  
 
list容器的大小操作 
函数原型： 
  
size(); //返回容器中元素的个数empty(); //判断容器是否为空resize(num); //重新指定容器的长度为num,若容器变长，则以默认 值填充新位置；如果容器变短，则末尾超出容器长度 的元素被删除resize(num,elem);//重新指定容器的长度为num,容器变长时用elem填 充；变短时则删除超出部分；
  
 
list容器的插入和删除 
push_back(elem); //尾插元素pop_back(); //尾删元素push_front(); //头插元素pop_front(); //头删元素insert(pos,elem); //在pos位置插入elem元素，并返回新数据位置insert(pos,n,elem);//在pos位置插入n个elem元素，无返回值insert(pos,beg,end);//在pos位置插入该区间的元素clear(); //清空链表erase(beg,end); //擦除该区间内的数据erase(pos); //擦除该位置的数据remove(elem); //删除容器中所有与elem值匹配的元素 
 
list容器的数据存取 
front(); //返回第一个元素back(); //返回最后一个元素 
 
list容器中的反转和排序 
将容器中的元素反转，以及将容器中的数据进行排序；函数原型： 
  
reverse(); //反转链表sort(); //链表排序 
    
此处的sort是成员函数该成员函数提供函数重载版本，默认为升序，可以定义降序，定义规则和algorithm中的sort规则相同； 
 注意： 
  
所有不支持随机访问迭代器的容器不可以使用标准算法；不支持随机访问迭代器的容器内部会有一些相应的成员函数；
  
 
set和multiset容器 
set基本概念 
• 简介：所有元素都会在插入时自动被排序；
 • 本质：set/multiset属于关联式容器，底层结构是用二叉树实现
 • set和multiset的区别：
 o set不允许容器中有重复的元素；
 o multiset允许容器中有重复的元素；
 • set容器插入数据只有s.insert()方法；
 
 
set容器的构造和赋值 
• 构造：
 o set s; //类模板默认构造
 o set(const set &s); //拷贝构造
 • 赋值：
 o set& operator=(const set &s);//重载等号操作符
 
 
set容器的大小和交换 
• size(); //返回容器中元素的数目
 • empty(); //判断容器是否为空
 • swap(s); //交换两个集合容器
 
 
set容器的插入和删除 
• insert(elem); //在容器中插入元素
 • clear(); //清空容器
 • erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器
 • erase(beg,end); //删除区间内部所有的迭代器，返回下一个元素的迭代器
 • erase(elem); //删除容器中值为elem的所有元素
 
 
set容器中的查找和统计 
• find(key); //查找key是否存在，若存在则返回该key的元素位置，不存 在则返回 set.end();
 • count(key); //统计key的元素个数
 
 
pair对组的创建 
• 功能描述：成对出现的数据，利用对组可以返回两个数据；
 • 两种创建方式：
 o pair p (value1,value2);
 o pair p = make_pair(value1,value2);
 
#include 
#include 
using namespace std;

void test01() {
	pair p("Chris",20);
	cout<<"访问对组的内容："<p2 = make_pair("Song",19);
	cout<<"访问对组的内容："< 
 
set容器的排序 
• 目标：利用仿函数，可以改变排序顺序规则；
 o 仿函数 – 重载“（）”运算符。
 
#include 
#include 

using namespace std;

void printSet(const set &s) {
	for (set::const_iterator it = s.begin(); it != s.end(); it++) {
		cout << *it << ' ';
	}
	cout << endl;
}

void test01() {
	set s1;
	s1.insert(1);
	s1.insert(3);
	s1.insert(5);
	s1.insert(4);
	s1.insert(2);
	s1.insert(6);
	printSet(s1);
}

//改变容器的排序方式
class MyCompare {
public:
	bool operator()(int a, int b) const
	{
		return a > b;
	}
};

void test02() {
	set s2;
	s2.insert(1);
	s2.insert(3);
	s2.insert(5);
	s2.insert(4);
	s2.insert(2);
	s2.insert(6);
	//printSet(s2);
	for (set::const_iterator it = s2.begin(); it != s2.end(); it++) {
		cout << *it << ' ';
	}
	cout << endl;
}

int main() {
	test01();
	test02();
	return 0;
}

 
 
map和multimap容器 
map基本概念 
• map 中所有元素都是 pair(对组)；
 • pair 中第一个元素为 key（键值），起到索引的作用，第二个元素为value(实值)；
 • 所有元素都会根据元素的键值自动排序；
 • 本质：
 o map/multimap属于关联式容器，底层结构是用二叉树实现的；
 • 优点：可以根据key值快速找到value值；
 • map/multimap区别：
 o map 不允许容器中有重复key值元素；
 o multimap 允许容器中有重复 key 值元素；
 
 
map构造和赋值 
• 构造：
 o map m;//类模板默认构造
 o map(const map &m);//拷贝构造函数
 • 赋值：
 o map& operator=(const map &m); //重载等号运算符
 
 
map容器的大小和交换 
• size(); //返回容器中元素的数目
 • empty();//判断容器是否为空
 • swap(m); //交换两个集合容器
 
 
map容器中的插入和删除 
• insert(elem); //在容器中插入元素
 • clear(); //清楚所有元素
 • erase(beg,end);//删除区间中的所有元素，返回下一个元素的迭代器
 • erase(pos); //删除pos迭代器所指的元素，返回下一个元素迭代器
 • erase(key);//删除容器中值为key的元素
 
 
map容器中的查找和统计 
• find(key); //查找key是否存在，返回该键元素的迭代器，否则返回end();
 • count(key); //统计key的元素个数
 
 
map容器中的排序 
• 主要利用仿函数改变排序规则
 
#include 
#include