使用方法"/>
C++ STL基本概念和使用方法
C++ STL基本概念和使用方法
- @[TOC](C++ STL基本概念和使用方法)
- 基本概念
- STL六大组件概述
- STL的优点
- STL的三大组件
- 容器
- 算法
- 迭代器
- 序列化容器
- string
- array
- vector
- deque
- list
- stack
- Queue
- 关联式容器
- set/multiset
- pair
- map\multimap
- @[TOC](C++ STL基本概念和使用方法)
- STL六大组件概述
- STL的优点
- STL的三大组件
- 容器
- 算法
- 迭代器
- 序列化容器
- string
- array
- vector
- deque
- list
- stack
- Queue
- 关联式容器
- set/multiset
- pair
- map\multimap
基本概念
长久以来，软件界一直希望建立一种可重复利用的东西，以及一种得以制造出”可重复运用的东西”的方法,让程序员的心血不止于随时间的迁移，人事异动而烟消云散，从函数(functions)，类别(classes),函数库(function libraries),类别库(class libraries)、各种组件，从模块化设计，到面向对象(object oriented )，到模式(pattern)的归纳整理，为的就是复用性的提升。
复用性必须建立在某种标准之上。但是在许多环境下，就连软件开发最基本的数据结构(data structures) 和算法(algorithm)都未能有一套标准。大量程序员被迫从事大量重复的工作，竟然是为了完成前人已经完成而自己手上并未拥有的程序代码，这不仅是人力资源的浪费，也是挫折与痛苦的来源。
为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹性、交互操作性(相互合作性,interoperability),诞生了STL。
STL(Standard Template Library,标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要出现在 c++中，但是在引入 c++之前该技术已经存在很长时间了。STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator),容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。STL(Standard Template Library)标准模板库,在我们 c++标准程序库中隶属于 STL 的占到了 80%以上。
STL六大组件概述
容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据，从实现角度来看，STL容器是一种class template。
算法：各种常用的算法，如sort、find、copy、for_each。从实现的角度来看，STL算法是一种function tempalte.
迭代器：扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将operator* , operator-> , operator++,operator–等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。
仿函数：行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的class 或者class template
适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。
空间配置器：负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte.
在C++标准中，STL被组织为下面的13个头文 件：<algorithm>、<deque>、<functional>、<iter>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack> 和<utility>。
STL的优点
- STL 是 C++的一部分，因此不用额外安装什么，它被内建在你的编译器之内。
- STL 的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但是这种分离使得 STL 变得非常通用。例如:在 STL 的 vector 容器中，可以放入元素、基础数据类型变量、元素的地址；STL 的 sort() 排序函数可以用来操作 vector,list 等容器。
- 使用时不用考虑实现过程
- STL 具有高可重用性，高性能，高移植性，跨平台的优点。
- 高可重用性：STL 中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。关于模板的知识，已经给大家介绍了。
- 高性能：如 map 可以高效地从十万条记录里面查找出指定的记录，因为 map 是采用红黑树的变体实现的。(红黑树是平横二叉树的一种)
- 高移植性：如在项目 A 上用 STL 编写的模块，可以直接移植到项目 B 上。
- 跨平台：如用windows的Visual Studio编写的代码可以在Mac OS的XCode上直接编译。
STL的三大组件
容器
容器，置物之所也。
研究数据的特定排列方式，以利于搜索或排序或其他特殊目的，这一门学科我们称为数据结构。几乎可以说，任何特定的数据结构都是为了实现某种特定的算法。STL容器就是将运用最广泛的一些数据结构实现出来。
常用的数据结构：数组(array),链表(list),树(tree)，栈(stack),队列(queue),集合(set),映射表(map),根据数据在容器中的排列特性，这些数据分为***序列式容器***和***关联式容器***两种。
-
序列式容器：即以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据，需要特殊说明的是，该类容器并不会自动对存储的元素按照值的大小进行排序。元素在容器中的位置是由元素进入容器的时间和地点来决定。Vector容器、Deque容器、List容器、Stack容器、Queue容器。
-
关联式容器非线性排列(二叉树)，在存储元素时会为每个元素在配备一个键，整体以键值对的方式存储到容器中，可以通过键值直接找到对应的元素，而无需遍历整个容器。另外，关联式容器在存储元素，默认会根据各元素键值的大小做升序排序。Set/multiset容器 Map/multimap容器。
算法
算法，问题之解法也。
以有限的步骤，解决逻辑或数学上的问题，这一门学科我们叫做算法(Algorithms).
广义而言，我们所编写的每个程序都是一个算法，其中的每个函数也都是一个算法，毕竟它们都是用来解决或大或小的逻辑问题或数学问题。STL收录的算法经过了数学上的效能分析与证明，是极具复用价值的，包括常用的排序，查找等等。特定的算法往往搭配特定的数据结构，数据结构是问题的载体，算法与数据结构相辅相成。
算法分为:质变算法和非质变算法。
- 质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
- 非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等
迭代器
迭代器(iterator)是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。在<>一书中提供了23中设计模式的完整描述，其中iterator模式定义如下：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。
迭代器的设计思维-STL的关键所在，STL的中心思想在于将数据容器(container)和算法(algorithms)分开，彼此独立设计，最后再一贴胶着剂将他们撮合在一起。从技术角度来看，容器和算法的泛型化并不困难，c++的class template和function template可分别达到目标，如果设计出两这个之间的良好的胶着剂，才是大难题。
迭代器的种类：
| 种类 | 功能 | 操作 |
|---|---|---|
| 输入迭代器 | 提供对数据的只读访问 | 只读，支持++、==、!= |
| 输出迭代器 | 提供对数据的只写访问 | 只写，支持++ |
| 前向迭代器 | 提供读写操作，并能向前推进迭代器 | 读写，支持++、==、!= |
| 双向迭代器 | 提供读写操作，并能向前和向后操作 | 读写，支持++、–， |
| 随机访问迭代器 | 提供读写操作，并能以跳跃的方式访问容器的任意数据，是功能最强的迭代器 | 读写，支持++、–、[n]、-n、<、<=、>、>= |
实例：
#include "main.h"
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;//STL 中的容器 算法 迭代器
void test01() {vector<int> v; //STL 中的标准容器之一 ：动态数组v.push_back(1); //vector 容器提供的插入数据的方法v.push_back(5);v.push_back(3);v.push_back(7);//迭代器vector<int>::iterator pStart = v.begin();//vector 容器提供了 begin()方法 返回指向第一个元素的迭代器vector<int>::iterator pEnd = v.end();//vector 容器提供了 end()方法 返回指向最后一个元素下一个位置的迭代器//通过迭代器遍历while (pStart != pEnd) {cout << *pStart << " ";pStart++;}cout << endl;//算法 count 算法 用于统计元素的个数int n = count(pStart, pEnd, 5);cout << "n:" << n << endl;
}class Teacher
{
public:Teacher(int age) :age(age) {};~Teacher() {};
public:int age;
};// STL 容器不单单可以存储基础数据类型，也可以存储类对象
void test02() {vector<Teacher> v; //存储 Teacher 类型数据的容器Teacher t1(10), t2(20), t3(30);v.push_back(t1);v.push_back(t2);v.push_back(t3);vector<Teacher>::iterator pStart = v.begin();vector<Teacher>::iterator pEnd = v.end();//通过迭代器遍历while (pStart != pEnd) {cout << pStart->age << " ";pStart++;}cout << endl;
}//存储 Teacher 类型指针
void test03() {vector<Teacher*> v;//存储 Teacher 类型指针Teacher* t1 = new Teacher(10);Teacher* t2 = new Teacher(20);Teacher* t3 = new Teacher(30);v.push_back(t1);v.push_back(t2);v.push_back(t3);//拿到容器迭代器vector<Teacher*>::iterator pStart = v.begin();vector<Teacher*>::iterator pEnd = v.end();//通过迭代器遍历while (pStart != pEnd) {cout << (*pStart)->age << " ";pStart++;}cout << endl;
}// 容器嵌套容器 难点(以容器作为元素插入到新的一个容器当中)
void test04() {vector<vector<int>> v; //容器中存储容器vector<int> v1, v2, v3;v1.push_back(1);v1.push_back(2);v2.push_back(10);v2.push_back(100);v3.push_back(100);v3.push_back(200);v.push_back(v1);v.push_back(v2);v.push_back(v3);//拿到容器迭代器vector<vector<int>>::iterator pStart = v.begin();vector<vector<int>>::iterator pEnd = v.end();//通过迭代器遍历while (pStart != pEnd) {vector<int> vTemp = *pStart; //获得迭代器当前指向的容器vector<int>::iterator tmpStart = vTemp.begin();vector<int>::iterator tmpEnd = vTemp.end();for (; tmpStart != tmpEnd; tmpStart++) {cout << *tmpStart << " ";}cout << endl;pStart++;}
}
int main() {//test01();//test02();//test03();test04();system("pause");return EXIT_SUCCESS;
}序列化容器
string
C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握，不适合大程序的开发，所以C++标准库定义了一种string类，定义在头文件。
String和c风格字符串对比：
Char是一个指针，String是一个类：string封装了char，管理这个字符串，是一个char型的容器。
String封装了很多实用的成员方法：查找find，拷贝copy，删除delete 替换replace，插入insert
不用考虑内存释放和越界： string管理char所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等。
构造函数
string(); //默认构造
string(const char* ptr); //char*指向的字符串
string(const string& right); //拷贝构造
string(string&& right); //移动构造
string(iter first,iter last); //以相同顺序复制[first，last)范围内的字符
string(const size_t count,const char c); //生成count个由字符c组成的序列
string(const char *ptr,size_t count); //char*指向的字符串，前count个字符
存储字符操作
ostream& operator<<(ostream& out,string& right); //直接输出string
char& operator[](size_t off); //获取off下标的字符(相对于首地址的偏移)
char& at(size_t off); //同上 但是越界会抛异常
char& front(); //获取头部元素
char& back(); //获取尾部元素
拼接操作
string&operator+=(const string& str);//重载+=操作符
string&operator+=(const char* str);//重载+=操作符
string&operator+=(const char c);//重载+=操作符
string& append(const char *s);//把字符串s连接到当前字符串结尾
string& append(const char *s, int n);//把字符串s的前n个字符连接到当前字符串结尾
string& append(const string&s);//同operator+=()
string& append(const string&s, int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
string& append(int n, char c);//在当前字符串结尾添加n个字符
查找和替换
int find(const string& str, 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) const;//查找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) const; //查找字符c最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s
比较
/*
compare函数在>时返回 1，<时返回 -1，==时返回 0。
比较区分大小写，比较时参考字典顺序，排越前面的越小。
大写的A比小写的a小。
*/
int compare(const string&s) const;//与字符串s比较
int compare(const char *s) const;//与字符串s比较
string子串
string substr(int pos = 0, int n = npos) const; //返回由pos开始的n个字符组成的字符串
string 的插入和删除
string& insert(int pos, const char* s); //插入字符串
string& insert(int pos, const string& str); //插入字符串
string& insert(int pos, int n, char c);//在指定位置插入n个字符c
string& erase(int pos, int n = npos);//删除从Pos开始的n个字符
string和c-style字符串转换
//string 转 char*
string str = "itcast";
const char* cstr = str.c_str();
//char* 转 string
char* s = "itcast";
string sstr(s);
在c++中存在一个从const char到string的隐式类型转换，却不存在从一个string对象到C_string的自动类型转换。对于string类型的字符串，可以通过c_str()函数返回string对象对应的C_string.
通常，程序员在整个程序中应坚持使用string类对象，直到必须将内容转化为char时才将其转换为C_string.
为了修改string字符串的内容，下标操作符[]和at都会返回字符的引用。但当字符串的内存被重新分配之后，可能发生错误.
array
array是一个容器，封装了固定大小的数组。
该容器是聚合类型，其语义与C风格数组的结构相同， T [ N ]作为其唯一的非静态数据成员。与c风格数组不同的是，它不会自动衰减为T*。(数组名不会自动转为数组首地址)
该容器将C风格数组的性能和可访问性与标准容器的优点相结合，比如知道自己的大小、支持赋值、随机访问迭代器等。
array没有构造函数，也没有私有或保护成员，**这就意味着它不会自动初始化。如果不对其初始化而直接获取其中的值，读出来的是野值 **。 可以使用聚合表达式（花括号）对其初始化。
array<int,5> arr = {1,2,3,4,5}; //如果花括号内元素个数小于数组容量，则会为剩余元素自动赋默认值。
可以用fill填充：
array<int,10> arr;
arr.fill(3); 把所有元素都设置为3
对于元素类型和数组大小相同的array，可以直接进行赋值.
元素访问
Ty& operator[](size_t i);
Ty& at(size_t i);
Ty& front();
Ty& back();
Ty* data(); //返回指向数组中第一个元素的指针
array容量大小
size_t size(); //返回数组大小
size_t max_size(); //返回数组大小
size_t empty(); //返回数组是否为空
修改
void fill(const Ty& val); //把所有元素都设置为val
void swap(array<Ty,?>& other); //交换两个array的数据，类型和大小必须一致
vector
vector 容器是 STL 中最常用的容器之一，它和 array 容器非常类似，都可以看做是对 C++普通数组的“升级版”。不同之处在于，array 实现的是静态数组（容量固定的数组），而 vector 实现的是一个动态数组，即可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间，整个过程无需人工干预。
vector尾部添加或移除元素非常快速。但是在中部或头部插入元素或移除元素比较费时
构造函数
vector();
vector(initializer_list<_Ty> list); //可以用聚合{}的方式初始化
vector(size_t size); //指定vector初始大小
vector(size_t size, const Ty& val); //指定大小，并把每个数据都设置为val
vector(Iter first, Iter last); //以相同顺序复制[first,last)范围内的元素
vector(const vector& _Right); //拷贝构造
vector(vector&& _Right); //移动构造vector<T> v; //采用模板实现类实现，默认构造函数v
vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素拷贝给本身。
vector(n, elem); //构造函数将n个elem拷贝给本身。元素访问
at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
operator[]; //返回索引idx所指的数据，越界时，运行直接报错
front(); //返回容器中第一个数据元素
back(); //返回容器中最后一个数据元素
Ty* data(); //返回指向数组中第一个元素的指针
vector容量相关
size_t size(); //获取vector有效元素个数
size_t max_size(); //可以存储的最大元素数量
size_t capacity(); //获取当前容量，自动扩容
void reserve(size_t n); //请求更改容量，如果n大于当前字符串的容量，则使容器将其容量增加到n个字符（或更大）,小于可能不予理会(与实现有关)
void resize(size_t n); //调整vector大小为n,n小于当前size，多余的数据会被丢掉
void resize(size_t n,const Ty& val); //如果n>size,剩下的用val填充
void clear(); //清空数据，长度变为0
bool empty(); //判断是否为空串，即size == 0
void shrink_to_fit(); //请求vector减小其容量到合适大小
vector修改
void push_back(const Ty& val); //在尾部插入元素
void push_back(Ty&& val); //同上
void emplace(Iter where,_Valty&& val); //效率比较高
void emplace_back(_Valty&& val)
void pop_back(); //删除尾部元素void assign(const size_t size, const Ty& val); //设置新的大小，并用val设置所有值void assign(Iter First, Iter Last); //以相同顺序复制[first,last)范围内的元素void assign(initializer_list<_Ty> Ilist); //同时赋值多个元素iter insert(iter _Where, const Ty& Val); //指定位置插入元素
iter insert(iter _Where, const size_t Count, const Ty& val); //指定位置插入，并且可以指定插入数量
iter insert(iter _Where, Iter First, Iter Last); //指定位置插入[first,last)之间的元素
iter insert(iter _Where, initializer_list<_Ty> Ilist);iterator erase(iter pos); //删除pos指向的元素
iterator erase(iter first,iterator last); //删除[first,last)范围内的字符
void swap(vector& str); //交换两个vector的内容
deque
deque是“double-ended queue”的缩写，和vector一样都是STL的容器，deque是双端数组，而vector是单端的。
deque在接口上和vector非常相似，在许多操作的地方可以直接替换。
deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。
deque 容器也可以根据需要修改自身的容量和大小。
和 vector 不同的是，deque 还擅长在序列头部添加或删除元素，所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是，deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。
Deque容器是连续的空间，至少逻辑上看来如此，连续现行空间总是令我们联想到array和vector,array无法成长，vector虽可成长，却只能向尾端成长，而且其成长其实是一个假象，事实上(1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间 三步骤，如果不是vector每次配置新的空间时都留有余裕，其成长假象所带来的代价是非常昂贵的。
Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。
既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。
Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。
deque构造函数
deque(); //默认构造
deque(size_t count); //指定size
deque(size_t count, Ty& val); //批量构造
deque(const deque& right); //拷贝构造
deque(deque&& right); //移动构造
deque(Iter first,Iter last); //区间构造
deque元素访问
Ty& operator[](size_t i);
Ty& at(size_t i);
Ty& front();
Ty& back();
deque容量相关
size_t size(); //获取有效元素个数
size_t max_size(); //可以存储的最大元素数量
void resize(size_t n); //调整大小为n,n小于当前size，多余的数据会被丢掉
void resize(size_t n,const Ty& val); //如果n>size,剩下的用val填充
void clear(); //清空数据，长度变为0
bool empty(); //判断是否为空串，即size == 0
void shrink_to_fit(); //请求减小其容量到合适大小
deque的修改
void push_back(const Ty& val); //在尾部插入元素
void push_back(Ty&& val); //同上
void push_front(const Ty& val); //在头部插入元素
void push_front(Ty&& val); //同上void emplace(Iter where,_Valty&& val); //效率比较高
void emplace_back(_Valty&& val);
void emplace_front(_Valty&& val)
void pop_back(); //删除尾部元素void assign(const size_t size, const Ty& val);//设置新的大小，并用val设置所有值void assign(Iter First, Iter Last); //以相同顺序复制[first,last)范围内的元素void assign(initializer_list<_Ty> Ilist); //同时赋值多个元素iter insert(iter _Where, const Ty& Val); //指定位置插入元素
iter insert(iter _Where, const size_t Count, const Ty& val);//指定位置插入，并且可以指定插入数量
iter insert(iter _Where, Iter First, Iter Last);//指定位置插入[first,last)之间的元素
iter insert(iter _Where, initializer_list<_Ty> Ilist);iterator erase(iter pos); //删除pos指向的元素
iterator erase(iter first,iterator last); //删除[first,last)范围内的字符void swap(vector& str); //交换两个vector的内容
list
list简介
list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。
List和vector是两个最常被使用的容器。
List容器是一个双向链表。
list容器的迭代器
List容器不能像vector一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。List迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。
由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterators.
List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至List元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。
list对象的默认构造
list();
list(size_t count);
list(size_t count,const Ty& val);
list(const list& right);
list(list&& right);
list(Iter first,Iter last);
list元素访问
Ty& front();
Ty& back();
list容量相关
bool empty();
size_t size();
size_t max_size();
void resize(size_t n); //调整大小为n,n小于当前size，多余的数据会被丢掉
void resize(size_t n,const Ty& val); //如果n>size,剩下的用val填充
list添加元素
void push_back(Ty& val);
void push_front(Ty& val);
void emplace_back(Args&&... args);
void emplace_front(Args&&... args);
Iter emplace(Iter pos,Args&&...args);void assign(const size_t size, const Ty& val);//设置新的大小，并用val设置所有值
void assign(Iter First, Iter Last); //以相同顺序复制[first,last)范围内的元素
void assign(initializer_list<_Ty> Ilist); //同时赋值多个元素iter insert(iter _Where, const Ty& Val); //指定位置插入元素
iter insert(iter _Where, Ty&& Val); //指定位置插入元素
iter insert(iter _Where, const size_t Count, const Ty& val);//指定位置插入，并且可以指定插入数量
iter insert(iter _Where, Iter First, Iter Last);//指定位置插入[first,last)之间的元素
iter insert(iter _Where, initializer_list<_Ty> Ilist);
list删除元素
iterator erase(iter pos); //删除pos指向的元素
iterator erase(iter first,iterator last); //删除[first,last)范围内的字符void pop_front();
void pop_back();void clear();
当使用一个容器的insert或者erase函数通过迭代器插入或删除元素"可能"会导致迭代器失效，因此我们为了避免危险，应该获取insert或者erase返回的迭代器，以便用重新获取的新的有效的迭代器进行正确的操作
lis<int> ls;
for (int i = 0; i < 10; i++)
{ls.push_back(i);
}
list<int>::iter it;
for (it = ls.begin(); it != ls.end(); it++)
{if (*it == 5){it=ls.erase(it);}cout << *it << " ";
}
list的其他操作
void splice (Iter position, list& x);
void splice (Iter position, list&& x);
void splice (Iter position, list& x, Iter i);
void splice (Iter position, list&& x, Iter i);
void splice (Iter position, list& x,Iter first, Iter last);
void splice (Iter position, list&& x,Iter first, Iter last);removeremove_ifuniquemergesortreverse
stack
Stack简介
stack是堆栈容器，是一种“先进后出”的容器。
stack是简单地装饰deque容器而成为另外的一种容器。
#include
tack是一种先进后出(First In Last Out,FILO)的数据结构，它只有一个出口，形式如图所示。stack容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。Stack所有元素的进出都必须符合”先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。Stack不提供遍历功能，也不提供迭代器。
stack对象的默认构造
stack采用模板类实现， stack对象的默认构造形式： stack stkT;
stack stkInt; //一个存放int的stack容器。
stack stkFloat; //一个存放float的stack容器。
stack stkString; //一个存放string的stack容器。
…
//尖括号内还可以设置指针类型或自定义类型。
stack元素获取与删除
stack.push(elem); //往栈头添加元素stack.pop(); //从栈头移除第一个元素stack.top(); //返回最栈顶元素
stack对象的拷贝构造与赋值
stack(const stack &stk); //拷贝构造函数
stack& operator=(const stack &stk); //重载等号操作符
stack的大小
stack.empty(); //判断堆栈是否为空
stack.size(); //返回堆栈的大小
Queue
Queue简介
queue是队列容器，是一种“先进先出”的容器。
queue是简单地装饰deque容器而成为另外的一种容器。
#include
Queue是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口，queue容器允许从一端新增元素，从另一端移除元素。Queue所有元素的进出都必须符合”先进先出”的条件，只有queue的顶端元素，才有机会被外界取用。Queue不提供遍历功能，也不提供迭代器。
queue对象的默认构造
queue采用模板类实现，queue对象的默认构造形式：queue<T> queT; 如：
queue<int> queInt; //一个存放int的queue容器。
queue<float> queFloat; //一个存放float的queue容器。
queue<string> queString; //一个存放string的queue容器。
//尖括号内还可以设置指针类型或自定义类型。
queue的数据存取
queue.push(elem); //往队尾添加元素
queue.pop(); //从队头移除第一个元素
queue.back(); //返回最后一个元素
queue.front(); //返回第一个元素
queue对象的拷贝构造与赋值
queue(const queue &que); //拷贝构造函数
queue& operator=(const queue &que); //重载等号操作符
queue的大小
queue.empty(); //判断队列是否为空
queue.size(); //返回队列的大小
关联式容器
set/multiset
set是一个***集合***容器，其中所包含的元素是***唯一***的，集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
set采用***红黑树***变体的数据结构实现，红黑树属于平衡二叉树。在插入操作和删除操作上比vector快。
set不可以直接存取元素。（不可以使用at.(pos)与[]操作符）。
multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。
不可以直接修改set或multiset容器中的元素值，因为该类容器是自动排序的。如果希望修改一个元素值，必须先删除原有的元素，再插入新的元素。
#include
set/multiset对象的默认构造
set<int> setInt; //一个存放int的set容器。
set<float> setFloat; //一个存放float的set容器。
set<string> setString; //一个存放string的set容器。multiset<int> mulsetInt; //一个存放int的multi set容器。
multiset<float> multisetFloat; //一个存放float的multi set容器。
multiset<string> multisetString; //一个存放string的multi set容器。
set的插入
set.insert(elem); //在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。
Set集合的元素排序
set<int,less<int> > setIntA; //该容器是按升序方式排列元素。set<int,greater<int>> setIntB; //该容器是按降序方式排列元素。
set 相当于 set<int,less>。
less与greater中的int可以改成其它类型，该类型主要要跟set容纳的数据类型一致。
疑问1： less<>与greate< >是什么？
疑问2：如果set<>不包含int类型，而是包含自定义类型，set容器如何排序？
要解决如上两个问题，需了解容器的函数对象，也叫伪函数，英文名叫functor。
使用stl提供的函数对象。
set<int,greater<int>> setIntB;
setIntB.insert(3);
setIntB.insert(1);
setIntB。insert(5);
setIntB.insert(2);
此时容器setIntB就包含了按顺序的5,3,2,1元素
函数对象functor的用法
尽管函数指针被广泛用于实现函数回调，但C++还提供了一个重要的实现回调函数的方法，那就是函数对象。
functor，翻译成函数对象，伪函数，算符，是重载了“()”操作符的普通类对象。从语法上讲，它与普通函数行为类似。
greater<>与less<>就是函数对象。
下面举出greater的简易实现原理。
class greater
{
public:bool operator()(const int& iLeft, const int& iRight){return iLeft > iRight; //如果是实现less<int>的话，这边是写return (iLeft<iRight);}
};
容器就是调用函数对象的operator()方法去比较两个值的大小。
仿函数练习
学生包含学号，姓名属性，现要求任意插入几个学生对象到set容器中，使得容器中的学生按学号的升序排序。
解：
#include<iostream>
#include<set>
using namespace std;
//学生类
class CStudent
{
public:CStudent(int iID, string strName){m_iID = iID;m_strName = strName;}//private:int m_iID; //学号string m_strName; //姓名
};
//为保持主题鲜明，本类不写拷贝构造函数，不类也不需要写拷贝构造函数。但大家仍要有考虑拷贝构造函数的习惯。
//函数对象
struct StuFunctor
{bool operator()(const CStudent& stu1,const CStudent& stu2) const{return (stu1.m_iID < stu2.m_iID);}
};int main()
{set<CStudent, StuFunctor> setStu;setStu.insert(CStudent(3, "小张"));setStu.insert(CStudent(1, "小李"));setStu.insert(CStudent(5, "小王"));setStu.insert(CStudent(2, "小刘"));for (auto i : setStu){cout << i.m_iID << " ";}return 0;
}
set对象的拷贝构造与赋值
set(const set &st); //拷贝构造函数
set& operator=(const set &st); //重载等号操作符
set.swap(st); //交换两个集合容器
set的大小
set.size(); //返回容器中元素的数目
set.empty();//判断容器是否为空
set的删除
set.clear(); //清除所有元素
set.erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
set.erase(beg,end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
set.erase(elem); //删除容器中值为elem的元素。
set的查找
set.find(elem); //查找elem元素，返回指向elem元素的迭代器。
set.count(elem); //返回容器中值为elem的元素个数。对set来说，要么是0，要么是1。对multiset来说，值可能大于1。
set.lower_bound(elem); //返回第一个>=elem元素的迭代器。
set.upper_bound(elem); // 返回第一个>elem元素的迭代器。
set.equal_range(elem); //返回一对迭代器，这两个迭代器分别用于发现set中其键大于指定键的第一个元素，以及集中其键等于或大于指定键的第一个元素。
以上函数返回两个迭代器，而这两个迭代器被封装在pair中。
pair
对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。
pair的使用
pair译为对组，可以将两个值视为一个单元。
pair<T1,T2>存放的两个值的类型，可以不一样，如T1为int，T2为float。T1,T2也可以是自定义类型。
pair.first是pair里面的第一个值，是T1类型。
pair.second是pair里面的第二个值，是T2类型。
小结
- 容器set/multiset的使用方法；红黑树的变体，查找效率高，插入不能指定位置，插入时自动排序。
- functor的使用方法:类似于函数的功能，可用来自定义一些规则，如元素比较规则。
- pair的使用方法: 对组，一个整体的单元，存放两个类型(T1,T2，T1可与T2一样)的两个元素。
map\multimap
map是标准的关联式容器，一个map是一个键值对序列，即(key,value)对。它提供基于key的快速检索能力。
map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。
map可以直接存取key所对应的value，支持[]操作符，如map[key]=value。
multimap与map的区别：map支持唯一键值，每个键只能出现一次；而multimap中相同键可以出现多次。multimap不支持[]操作符。
#include
Map的特性是，所有元素都会根据元素的键值自动排序。Map所有的元素都是pair,同时拥有实值和键值，pair的第一元素被视为键值，第二元素被视为实值，map不允许两个元素有相同的键值。
我们可以通过map的迭代器改变map的键值吗？答案是不行，因为map的键值关系到map元素的排列规则，任意改变map键值将会严重破坏map组织。如果想要修改元素的实值，那么是可以的。
Map和list拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。
Multimap和map的操作类似，唯一区别multimap键值可重复。
Map和multimap都是以红黑树为底层实现机制。
map/multimap对象的默认构造
map<T1,T2> mapTT;
multimap<T1,T2> multimapTT;
map的插入与迭代器
map.insert(…); //往容器插入元素，返回pair<iter,bool>
在map中插入元素的三种方式：
假设 map<int, string> mapStu;
一、通过pair的方式插入对象
mapStu.insert( pair<int,string>(3,“小张”) );
二、通过pair的方式插入对象
mapStu.inset(make_pair(-1, “校长-1”));
三、通过value_type的方式插入对象
mapStu.insert( map<int,string>::value_type(1,“小李”) );
四、通过数组的方式插入值
mapStu[3] = “小刘";
mapStu.at(4) = “小王"；
map<int, string> chess;chess.insert(pair<int,string>(1,"将"));chess.insert(make_pair(2, "士"));chess.insert(map<int, string>::value_type(3, "像"));chess.at(3) = "马";chess[4] = "車";
前三种方法，采用的是insert()方法，该方法***返回值为pair<iter,bool>***
第四种方法非常直观，但存在一个性能的问题。插入3时，先在mapStu中查找主键为3的项，若没发现，则将一个键为3，值为初始化值的对组插入到mapStu中，然后再将值***修改***成“小刘”。若发现已存在3这个键，则修改这个键对应的value。
string strName = mapStu[2]; //取操作或插入操作
只有当mapStu存在2这个键时才是正确的取操作，否则会自动插入一个实例，键为2，值为初始化值。
函数对象functor的用法
map<T1,T2,less<T1> > mapA; //该容器是按键的升序方式排列元素。未指定函数对象，默认采用less<T1>函数对象。
map<T1,T2,greater<T1>> mapB; //该容器是按键的降序方式排列元素。
less<T1>与greater<T1> 可以替换成其它的函数对象functor。
可编写自定义函数对象以进行自定义类型的比较，使用方法与set构造时所用的函数对象一样。
map对象的拷贝构造与赋值
map(const map &mp); //拷贝构造函数
map& operator=(const map &mp); //重载等号操作符
map.swap(mp); //交换两个集合容器map的大小
map.size(); //返回容器中元素的数目
map.empty();//判断容器是否为空
map的删除
map.clear(); //删除所有元素
map.erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
map.erase(beg,end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
map.erase(keyElem); //删除容器中key为keyElem的对组。
map的查找
map.find(key); //查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回map.end();
map.count(keyElem); //返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
map.equal_range(keyElem); //返回容器中key与keyElem相等的上下限的两个迭代器。上限是闭区间，下限是开区间，如[beg,end)。
以上函数返回两个迭代器，而这两个迭代器被封装在pair中。
#define _CRT_SECURE_NO_WARNINGS#include<iostream>
#include<map>
#include<string>
#include<vector>
usingnamespace std;//multimap 案例
//公司今天招聘了 5 个员工，5 名员工进入公司之后，需要指派员工在那个部门工作
//人员信息有: 姓名 年龄 电话 工资等组成
//通过 Multimap 进行信息的插入 保存 显示
//分部门显示员工信息 显示全部员工信息#define SALE_DEPATMENT 1 //销售部门
#define DEVELOP_DEPATMENT 2 //研发部门
#define FINACIAL_DEPATMENT 3 //财务部门
#define ALL_DEPATMENT 4 //所有部门//员工类
class person{
public:string name;//员工姓名int age;//员工年龄double salary;//员工工资string tele;//员工电话
};//创建5个员工
void CreatePerson(vector<person>& vlist){string seed ="ABCDE";for(int i =0; i <5; i++){person p;p.name ="员工";p.name += seed[i];p.age = rand()%30+20;p.salary = rand()%20000+10000;p.tele ="010-8888888";vlist.push_back(p);}}//5名员工分配到不同的部门
void PersonByGroup(vector<person>& vlist, multimap<int, person>& plist){int operate =-1;//用户的操作for(vector<person>::iterator it = vlist.begin(); it != vlist.end(); it++){cout <<"当前员工信息:"<< endl;cout <<"姓名："<< it->name <<" 年龄:"<< it->age <<" 工资:"<< it->salary <<" 电话："<< it->tele << endl;cout <<"请对该员工进行部门分配(1 销售部门, 2 研发部门, 3 财务部门):"<< endl;scanf("%d",&operate);while(true){if(operate == SALE_DEPATMENT){//将该员工加入到销售部门plist.insert(make_pair(SALE_DEPATMENT,*it));break;}elseif(operate == DEVELOP_DEPATMENT){plist.insert(make_pair(DEVELOP_DEPATMENT,*it));break;}elseif(operate == FINACIAL_DEPATMENT){plist.insert(make_pair(FINACIAL_DEPATMENT,*it));break;}else{cout <<"您的输入有误，请重新输入(1 销售部门, 2 研发部门, 3 财务部门):"<< endl;scanf("%d",&operate);}}}cout <<"员工部门分配完毕!"<< endl;cout <<"***********************************************************"<< endl;}//打印员工信息
void printList(multimap<int, person>& plist,int myoperate){if(myoperate == ALL_DEPATMENT){for(multimap<int, person>::iterator it = plist.begin(); it != plist.end(); it++){cout <<"姓名："<< it->second.name <<" 年龄:"<< it->second.age <<" 工资:"<< it->second.salary <<" 电话："<< it->second.tele << endl;}return;}multimap<int, person>::iterator it = plist.find(myoperate);int depatCount = plist.count(myoperate);int num =0;if(it != plist.end()){while(it != plist.end()&& num < depatCount){cout <<"姓名："<< it->second.name <<" 年龄:"<< it->second.age <<" 工资:"<< it->second.salary <<" 电话："<< it->second.tele << endl;it++;num++;}}
}//根据用户操作显示不同部门的人员列表
void ShowPersonList(multimap<int, person>& plist,int myoperate){switch(myoperate){case SALE_DEPATMENT:printList(plist, SALE_DEPATMENT);break;case DEVELOP_DEPATMENT:printList(plist, DEVELOP_DEPATMENT);break;case FINACIAL_DEPATMENT:printList(plist, FINACIAL_DEPATMENT);break;case ALL_DEPATMENT:printList(plist, ALL_DEPATMENT);break;}
}//用户操作菜单
void PersonMenue(multimap<int, person>& plist){int flag =-1;int isexit =0;while(true){cout <<"请输入您的操作((1 销售部门, 2 研发部门, 3 财务部门, 4 所有部门, 0退出)："<< endl;scanf("%d",&flag);switch(flag){case SALE_DEPATMENT:ShowPersonList(plist, SALE_DEPATMENT);break;case DEVELOP_DEPATMENT:ShowPersonList(plist, DEVELOP_DEPATMENT);break;case FINACIAL_DEPATMENT:ShowPersonList(plist, FINACIAL_DEPATMENT);break;case ALL_DEPATMENT:ShowPersonList(plist, ALL_DEPATMENT);break;case0:isexit =1;break;default:cout <<"您的输入有误，请重新输入!"<< endl;break;}if(isexit ==1){break;}}}int main(){vector<person> vlist;//创建的5个员工 未分组multimap<int, person> plist;//保存分组后员工信息//创建5个员工CreatePerson(vlist);//5名员工分配到不同的部门PersonByGroup(vlist, plist);//根据用户输入显示不同部门员工信息列表 或者 显示全部员工的信息列表PersonMenue(plist);system("pause");return EXIT_SUCCESS;
}
更多推荐
C++ STL基本概念和使用方法
发布评论