C++的标准模板库STL

目录

STL基本概念

STL六大组件

容器、算法、迭代器初识

string容器

vector容器

deque容器（deque意为“双端队列”）

stack容器

queue容器

list容器

set/multiset容器

pair对组创建

map/multimap容器

函数对象

谓词

内建函数对象

---

STL基本概念

• STL(Standard Template Library)，标准模板库
• 从广义上分为：容器(containor)、算法(algorithm)、迭代器(iterator)
• 容器和算法之间通过迭代器进行无缝衔接
• STL几乎所有的代码都采用了模板类或者模板函数

STL六大组件

• 容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据
• 算法：各种常用的算法，如sort、find、copy、for_each等
• 迭代器：扮演了容器与算法的胶合剂
• 仿函数：行为类似函数，可作为算法的某种策略
• 适配器（配接器）：一种用来修饰容器或仿函数或迭代器接口的东西
• 空间配置器：负责空间的配置与管理

容器

• 容器就是将最广泛的一些数据结构实现出来
• 常见的数据结构包括 数组、链表、树、栈、队列、集合、映射表 等
• 序列式容器：强调值的排序，序列式容器中的每个元素均有固定的位置
• 关联式容器：二叉树结构，各元素之间没有严格的物理顺序关系

算法

• 质变算法：运算过程会更改区间内元素的内容，如拷贝、替换、删除等
• 非质变算法：运算过程不会更改区间内元素的内容，如查找、计数、遍历等

迭代器

• 提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露其内部表达方式
• 每个容器都有专属的迭代器
• 迭代器使用非常类似于指针，初学阶段先理解其为指针
• 迭代器种类如下，其中常见的是双向迭代器和随机访问迭代器

容器、算法、迭代器初识

• vector存放内置数据类型（请将其他遍历方式注释后使用）

  #include 
  #include 
  #include 
  #include 
  using namespace std;
  
  void myPrint(int val) {
  	cout << val << endl;
  }
  
  void test01() {	
  	//创建了一个vector容器
  	vector v;
  
  	//向容器中插入数据
  	v.push_back(10);
  	v.push_back(20);
  	v.push_back(30);
  	v.push_back(40);
  
  	//第一种遍历方式
  
  	//通过迭代器来访问容器中的数据
  	//起始迭代器，指向容器第一个元素的位置
  	vector::iterator itBegan = v.begin();	
  	//结束迭代器，指向容器最后元素的下一元素位置
  	vector::iterator itEnd = v.end();	
  
  	while (itBegan != itEnd) {
  		cout << *itBegan << endl;
  		itBegan++;
  	}
  
  	//第二种遍历方式
  	for (vector::iterator it = v.begin(); it != v.end(); it++) {
  		cout << *it << endl;
  	}
  
  	//第三种方式
  	for_each(v.begin(),v.end(),myPrint);
  }
  
  int main() {
  
  	test01();
  
  	system("pause");
  
  	return 0;
  }

• vector存放自定义数据类型

  #include 
  #include 
  #include 
  #include 
  using namespace std;
  
  class Person{
  public:
  	Person(string name, int age) {
  		this->name = name;
  		this->age = age;
  	}
  	string name;
  	int age;
  };
  
  void test01() {
  	vector v;
  	Person p1("sad", 10);
  	Person p2("happy", 20);
  	Person p3("honey", 23);
  
  	//向容器中添加数据
  	v.push_back(p1);
  	v.push_back(p2);
  	v.push_back(p3);
  	
  	//遍历
  	for (vector::iterator it = v.begin(); it != v.end(); it++) {
  		cout << "姓名：" << (*it).name << endl;
  		cout << "年龄：" << (*it).age << endl;
  
  		cout << "姓名：" << it->name << endl;
  		cout << "年龄：" << it->age << endl;
  	}
  }
  
  void test02() {
  	vector v;
  	Person p1("sad", 10);
  	Person p2("happy", 20);
  	Person p3("honey", 23);
  
  	//向容器中添加数据
  	v.push_back(&p1);
  	v.push_back(&p2);
  	v.push_back(&p3);
  
  	//遍历
  	for (vector::iterator it = v.begin(); it != v.end(); it++) {
  		cout << "姓名：" << (*it)->name << endl;
  		cout << "年龄：" << (*it)->age << endl;
  	}
  }
  
  int main() {
  
  	//test01();
  	//test02();
  
  	system("pause");
  
  	return 0;
  }

• 容器嵌套容器

  #include 
  #include 
  #include 
  #include 
  using namespace std;
  
  void test01() {
  	//创建大容器
  	vector > v;
  
  	//创建小容器
  	vector v1;
  	vector v2;
  	vector v3;
  	vector v4;
  	
  	//向小容器中添加数据
  	for (int i = 0; i < 4; i++) {
  		v1.push_back(i + 1);
  		v2.push_back(i + 2);
  		v3.push_back(i + 3);
  		v4.push_back(i + 4);
  	}
  
  	//将小容器插入到大容器中
  	v.push_back(v1);
  	v.push_back(v2);
  	v.push_back(v3);
  	v.push_back(v4);
  
  	//通过大容器，把所数据都遍历一遍
  	for (vector>::iterator it = v.begin(); it != v.end(); it++) {
  		//遍历小容器
  		for (vector::iterator vit = (*it).begin(); vit!=(*it).end(); vit++) {
  			cout << *vit << " ";
  		}
  		cout << endl;
  	}
  }
  
  int main() {
  
  	test01();
  
  	system("pause");
  
  	return 0;
  }

string容器

string和char*

• char * 是一个指针
• string是一个类，类内部封装了char*，管理这个字符串，是一个char*的容器
• string类内部封装了很多成员方法
• string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责

string的构造函数

• string()：创建一个空字符串
• string(char* s)：使用字符串s初始化
• string(const string& s)：使用一个string对象初始化另一个对象
• string(int n, char c)：使用n个字符初始化

string的赋值 *** 作

• string& operator=(const char* s)：char*字符串赋值给当前字符串
• string& operator=(const string &s)：把字符串s赋给当前字符串
• string& operator=(char c)：字符赋值给当前字符串
• string& assign(const char* s)：把字符串s赋给当前字符串
• string& assign(const char* s, int n)：把字符串的前n个字符赋给当前字符串
• string& assign(const string &s)：把字符串s赋给当前字符串
• string& assign(int n, char c)：n个字符c赋给当前字符串

string字符串拼接

• string& operator+=(const char* str)：重载+=
• string& operator+=(const char c)：重载+=
• string& operator+=(const string& str)：重载+=
• string& append(const char* s)：把字符串s连接到当前字符串末尾
• string& append(const char* s, int n)：把字符串前n个字符连接到当前字符串末尾
• string& append(const string& s)：把字符串s连接到当前字符串末尾
• string& append(const string& s, int pos, int n)：将字符串s中从pos开始的n个字符连接到末尾

string查找和替换

• int find(const& string, int pos=0) const：查找str第一次出现的位置，从pos开始
• int find(const char* s, int pos=0) const：查找s第一次出现的位置，从pos开始
• int find(const char* s, int pos, int n) const：从pos开始查找s的前n个字符第一次出现的位置
• int find(const char c, int pos=0) const：查找字符c第一次出现的位置
• int rfind(const string& str, int pos=npos) cosnt：查找str最后一次出现的位置，从pos开始
• int rfind(const char* s, int pos=npos) const：查找s最后一次出现的位置，从pos开始
• int rfind(const char* s, int pos, int n) const：从pos开始查找s的前n个字符最后一次出现的位置
• int rfind(const char c, int pos=0) cosnt：查找字符c最后一次出现的位置
• string& replace(int pos, int n, cosnt string& str)：替换从pos开始的n个字符为str
• string& replace(int pos, int n, const char* s)：替换从pos开始的n个字符为s

string字符串比较

• 按ASCII码进行对比，=返回0，>返回1，<返回-1
• int compare(const string &s) const
• int compare(const char* s) const

string字符存取

• char& operator[](int n)：通过[]方式取字符
• char& at(int n)：通过at方法取字符

string插入和删除

• string& insert(int pos, const char* s)：插入字符串
• string& insert(int pos, const string& str)：插入字符串
• string& insert(int pos, int n, char c)：在指定位置插入n个字符
• string& erase(int pos, int n = npos)：删除从pos开始的n个字符

string子串

• string substr(int pos=0, int n=npos) const：返回由pos开始的n个字符组成的字符串

vector容器

基本概念

• vector和数组非常相似，也称为单端数组
• 不同之处在于数组是静态空间，而vector可以动态扩展
• 动态扩展：找更大的空间，将原数据拷贝到新空间，释放原空间

vector构造函数

• vector v：采用模板实现类实现，默认构造函数
• vector(v.begin(), v.end())：将v.begin()和end()区间中的元素拷贝给本身
• vector(n, elem)：将n个elem拷贝给本身
• vector(const vector &vec)：拷贝构造函数

vector赋值 *** 作

• vector& operator=(const vector &vec)：重载等号 *** 作符
• assign(beg, end)：将[beg,end]区间中的数据拷贝赋值给本身
• assign(n, elem)：将n个elem拷贝赋值给本身

vector容量和大小

• empty()：判断容器是否为空
• capacity()：容器的容量
• size()：返回容器中的元素个数
• resize(int num)：重新指定容器长度，容器变长用0填充新位置，容器变短超出的部分被删除
• resize(int num, elem)：容器变长可以选择elem值填充

vector插入和删除

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

vector数据存取

• at(int idx)：返回索引idx所指的数据
• operator[]：返回索引idx所指的数据
• front()：返回容器中第一个数据元素
• back()：返回容器中最后一个数据元素

vector排序

• sort(beg, end)：对beg和end区间的元素进行排序，默认升序

vector互换容器

• swap(vec)：将vec与本身的元素互换
• 我们可能会遇到容器容量（capacity）很大，但存储数据不多（size）的情况
• 可以利用swap()收缩内存
• 用法：vector(v).swap(v)
• 其中，vector(v)是创建匿名对象，该行执行完后会自动消除
• swap(v)表示，将匿名对象与容器v互换，将容量收缩为实际存储的大小

vector预留空间

• reserve(int len)：容器预留len个元素长度，预留位置不初始化，元素不可访问
• 减少vector在动态扩容时的扩展次数

deque容器（deque意为“双端队列”）

基本概念

• 双端数组，可以对头端进行插入删除 *** 作
• vector对于头部的插入删除效率低，而deque的效率相对高
• vector访问元素的速度会比deque快，这和两者的内部实现有关

内部工作原理

• deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据
• 中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续内存空间

 deque构造函数

• deque：默认构造函数
• deque(beg, end)：将[beg, end]区间中的元素拷贝给本身
• deque(n, elem)：将n个elem拷贝给本身
• deque(const deque& deq)：拷贝构造函数

deque赋值 *** 作

• deque& operator=(const deque &vec)：重载等号 *** 作符
• assign(beg, end)：将[beg,end]区间中的数据拷贝赋值给本身
• assign(n, elem)：将n个elem拷贝赋值给本身

deque容量和大小

• empty()：判断容器是否为空
• size()：返回容器中的元素个数
• resize(int num)：重新指定容器长度，容器变长用0填充新位置，容器变短超出的部分被删除
• resize(int num, elem)：容器变长可以选择elem值填充
• 相比vector，没有容量的概念

deque插入和删除

• push_back(ele)：尾部插入元素ele
• push_front(ele)：头部插入元素ele
• pop_back()：删除最后一个元素
• pop_front()：删除第一个元素
• insert(pos, ele)：迭代器指向位置pos插入元素ele
• insert(pos, count, ele)：迭代器指向位置pos插入count个元素
• insert(pos, beg, end)：在pos位置插入[beg, end]区间的数据
• erase(pos)：删除迭代器指向的元素
• erase(start, end)：删除迭代器从start到end之间的元素
• clear()：删除容器中所有元素

deque数据存取

• at(int idx)：返回索引idx所指的数据
• operator[]：返回索引idx所指的数据
• front()：返回容器中第一个数据元素
• back()：返回容器中最后一个数据元素

deque排序

• sort(beg, end)：对beg和end区间的元素进行排序，默认升序

stack容器

基本概念

• 栈是一种先进后出的数据结构，只有一个出口
• 栈不允许遍历

常用接口

• stack stk：采用模板类实现的默认构造函数
• stack(const stack& stk)：拷贝构造函数
• stack& operator=(const stack& stk)：重载等号 *** 作符
• push(elem)：向栈顶添加元素
• pop()：从栈顶移除第一个元素
• top()：返回栈顶元素
• empty()：判断堆栈是否为空
• size()：返回栈的大小

queue容器

基本概念

• 队列是一种先进先出的数据结构
• 允许从一端（队尾）新增元素（入队）
• 允许从另一端（队头）移除元素（出队）

常用接口

• quene que：采用模板类实现的默认构造函数
• quene(const quene& que)：拷贝构造函数
• quene& operator=(const quene& que)：重载等号 *** 作符
• push(elem)：往队尾添加元素
• pop()：从队头移除第一个元素
• front()：返回队头元素
• back()：返回队尾元素
• empty()：判断堆栈是否为空
• size()：返回栈的大小

list容器

基本概念

• 链表是一种物理存储单元非连续的存储结构，通过指针链接实现逻辑顺序
• 链表由一系列结点组成
• 结点分为存储数据的数据域、存储相邻结点地址的指针域
• STL中的链表是一个双向循环链表

优缺点

• 优点：可对任意位置快速插入或删除，采用动态内存分配避免数组的内存浪费与溢出问题
• 缺点：容器遍历速度没有数组快，占用空间比数组大

构造函数

• list lst：采用模板类实现的默认构造函数
• list(beg, end)：将[beg, end]区间中的元素拷贝给本身
• list(n, elem)：将n个elem拷贝给本身
• list(const list& lst)：拷贝构造函数

list赋值与交换

• list& operator=(const list& lst)：重载等号 *** 作符
• assign(beg, end)：将[beg,end]区间中的数据拷贝赋值给本身
• assign(n, elem)：将n个elem拷贝赋值给本身
• swap(lst)：将lst与本身元素互换

list大小 *** 作

• empty()：判断容器是否为空
• size()：返回容器中的元素个数
• resize(num)：重新指定容器长度，容器变长用0填充新位置，容器变短超出的部分被删除
• resize(num, elem)：容器变长可以选择elem值填充

list插入与删除

• push_back(ele)：在链尾插入元素ele
• push_front(ele)：在链头插入元素ele
• pop_back()：删除链表最后一个元素
• pop_front()：删除链表第一个元素
• insert(pos, ele)：迭代器指向位置pos插入元素ele，返回新数据的位置
• insert(pos, count, ele)：迭代器指向位置pos插入count个元素ele，无返回值
• insert(pos, beg, end)：在pos位置插入[beg, end]区间的数据
• erase(pos)：删除迭代器指向的元素
• erase(start, end)：删除迭代器从start到end之间的元素
• clear()：删除容器中所有元素
• remove(elem)：移除容器中所有与elem相匹配的元素

list数据存取

• front()：返回第一个元素
• back()：返回最后一个元素
• 不支持随机访问，不支持 [] 或 at()

list反转和排序

• reverse()：反转链表
• sort()：链表排序，默认升序
• 如何降序？

  //指定排序规则
  bool myCompare(int v1, int v2){
      //降序  第一个数 > 第二个数
      return v1 > v2;
  }
  //作为参数传入链表排序算法中
  L1.sort(myCompare);

对自定义数据排序

#include
using namespace std;
#include 
#include 

//list容器 排序案例 对于自定义数据类型 做排序

//按照年龄进行升序，如果年龄相同按照身高进行降序

class Person
{
public:
	Person(string name,int age,int height)
	{
		this->m_Name = name;
		this->m_Age = age;
		this->m_Height = height;
	}

	string m_Name; //姓名
	int m_Age;   //年龄
	int m_Height; // 身高
};


//指定排序规则
bool comparePerson(Person &p1,Person &p2)
{
	//按照年龄 升序
	if (p1.m_Age == p2.m_Age)
	{
		//年龄相同  按照身高降序
		return p1.m_Height > p2.m_Height;
	}
	else
	{
		return  p1.m_Age < p2.m_Age;
	}
	
}

void test01()
{
	listL; //创建容器

	//准备数据
	Person p1("刘备", 35, 175);
	Person p2("曹 *** ", 45, 180);
	Person p3("孙权", 40, 170);
	Person p4("赵云", 25, 190);
	Person p5("张飞", 35, 160);
	Person p6("关羽", 35, 200);

	//插入数据
	L.push_back(p1);
	L.push_back(p2);
	L.push_back(p3);
	L.push_back(p4);
	L.push_back(p5);
	L.push_back(p6);

	for (list::iterator it = L.begin(); it != L.end(); it++)
	{
		cout << "姓名： " << (*it).m_Name << " 年龄： " << it->m_Age << " 身高： " << it->m_Height << endl;
	}

	//排序
	cout << "---------------------------------" << endl;
	cout << "排序后：" << endl;

	L.sort(comparePerson);
	for (list::iterator it = L.begin(); it != L.end(); it++)
	{
		cout << "姓名： " << (*it).m_Name << " 年龄： " << it->m_Age << " 身高： " << it->m_Height << endl;
	}
}

int main() {

	test01();

	system("pause");

	return 0;
}

set/multiset容器

基本概念

• 所有元素会在插入时自动被排序
• set/multiset属于关联式容器，底层结构是用二叉树实现的

区别

• set不容许重复元素
• multiset容许有重复元素

构造和赋值

• set：默认构造函数
• set(const set& st)：拷贝构造函数
• set& operator=(const set& st)：重载等号 *** 作符

set大小和交换

• empty()：判断容器是否为空
• size()：返回容器中的元素个数
• swap(st)：交换两个集合容器

set插入和删除

• insert(elem)：插入元素elem
• erase(pos)：删除迭代器指向的元素
• erase(start, end)：删除迭代器从start到end之间的元素
• earse(elem)：删除容器中值为elem的元素
• clear()：删除容器中所有元素

set查找与统计

• find(key)：查找key是否存在，若存在返回迭代器，不存在则返回set.end()
• count(key)：统计key的个数，对于set而言只有0或1两种结果

set容器排序

• set容器默认规则为从小到大，掌握如何改变规则
• 利用仿函数，可以改变排序规则

• //仿函数
  class MyCompare{
  public:
      bool operator()(int v1, int v2){
          return v1 > v2;    //降序
      }    
  
  };
  //声明容器时，放入参数列表，容器就改为降序排序了
  set s;

pair对组创建

成对出现的数据，利用对组可以返回两个数据

两种创建方式

• pair p(value1, value2)
• pair p = make_pair(value1, value2)

map/multimap容器

基本概念

• map所有元素都是pair
• pair中的第一个元素为key（键值），起索引作用，第二个元素为value（实值）
• 所有元素会根据键值自动排序
• 关联式容器，底层用二叉树实现
• 根据key可以快速找到value

map和multimap区别

• map不允许重复key值
• multimap允许重复key值

map构造和赋值

• map mp：默认构造
• map(const map& mp)：拷贝构造
• map& operator=(const map& mp)：重载等号 *** 作符

map大小和交换

• empty()：判断容器是否为空
• size()：返回容器中的元素个数
• swap(st)：交换两个容器

map插入和删除

• insert(elem)：插入元素elem
• erase(pos)：删除迭代器指向的元素
• erase(start, end)：删除迭代器从start到end之间的元素
• earse(key)：删除容器中值为key的元素
• clear()：删除容器中所有元素

map查找与统计

• find(key)：查找key是否存在，若存在返回迭代器，不存在则返回map.end()
• count(key)：统计key的个数，对于map而言只有0或1两种结果

map容器排序

• map容器默认规则为从小到大，掌握如何改变规则
• 利用仿函数，可以改变排序规则

函数对象

概念

• 重载函数调用 *** 作符的类，其对象常称为函数对象
• 函数对象使用重载的()时，行为类似函数调用，也叫仿函数
• 本质上，函数对象是一个类，不是一个函数

特点

• 函数对象在使用时，可以像普通函数那样调用，可以有参数、返回值
• 函数对象超出普通函数的概念，函数对象可以有自己的状态
• 函数对象可以作为参数传递

谓词

概念

• 返回bool类型的仿函数称为谓词
• 如果operator()接受一个参数，称其为一元谓词
• 如果operator()接受两个参数，称其为二元谓词

内建函数对象

分类

• 算术仿函数
• 关系仿函数
• 逻辑仿函数

用法

• 这些仿函数所产生的对象，用法和一般函数完全相同
• 使用内建函数对象，需要引入头文件

算术仿函数

• template T plus：加法仿函数
• template T minus：减法仿函数
• template T multiplies：乘法仿函数
• template T divides：除法仿函数
• template T modulus：取模仿函数
• template T negate：取反仿函数

关系仿函数

• template bool equal_to：等于
• template bool not_equal_to：不等于
• template bool greater：大于
• template bool greater_equal：大于等于
• template bool less：小于
• template bool less_equal：小于等于

逻辑仿函数

• template bool logical_and：逻辑与
• template bool logical_or：逻辑或
• template bool logical_not：逻辑非