标签：vector string 迭代 STL 元素 C++ 详解字符串 include

STL是提高C++编写效率的一个利器。
——闫学灿

一.string

参考文章

介绍

C语言中，字符串是以\0结尾的一些字符的集合，为了操作方便，C标准库中提供了一些str系列的库函数，但是这些库函数与字符串是分离开的，不太符合OOP（面向对象）的思想，而且底层空间需要用户自己管理，稍不留神可能还会越界访问。
C++中就引入了string类，它可以看做是一个管理字符串的数据结构。
string是表示字符串的字符串类
该类的接口与常规容器的接口基本相同，再添加了一些专门用来操作string的常规操作。
string在底层实际是：basic_string 模板类的别名。
实现为：typedef basic_string<char, char_traits, allocator> string;
不能操作多字节或者变长字符的序列。

头文件及命名空间

#include<string>
using namespace std;

定义 string 变量

例1

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s1;
    string s2 = "c plus plus";
    string s3 = s2;
    string s4 (5, 's');
    return 0;
}

变量 s1 只是定义但没有初始化，编译器会将默认值赋给 s1，默认值是""，也即空字符串。
变量 s2 在定义的同时被初始化为"c plus plus"。与C风格的字符串不同，string 的结尾没有结束标志'\0'。
变量 s3 在定义的时候直接用 s2 进行初始化，因此 s3 的内容也是"c plus plus"。
变量 s4 被初始化为由 5 个's'字符组成的字符串，也就是"sssss"。
从上面的代码可以看出，string 变量可以直接通过赋值操作符=进行赋值。
string 变量也可以用C风格的字符串进行赋值，例如，s2 是用一个字符串常量进行初始化的，而 s3 则是通过 s2 变量进行初始化的。

例2

string str1("hello world");    // hello world
string str2  = "hello world";  // hello world
string str3(str2);             // hello world
string str4 = str3;            // hello world
string str5(5,'d');            // ddddd
string str6(str2, 6);          // world，从str2的第6个字符开始到结束，拷贝到str6中
string str7(str2, 0, 5);       // hello, 从str2的第0个字符开始拷贝5个字符到str7中
char buff[] = "hello sorld";
string str8(buff, 5);          // hello, 拷贝buff的前5个字符到str8中

得到长度

可以调用 string 类提供的 length() 函数。如下所示：

string s = "http://c.biancheng.net";
int len = s.length();
cout<<len<<endl;

输出结果为22。由于 string 的末尾没有'\0'字符，所以 length() 返回的是字符串的真实长度，而不是长度 +1。

输入与输出

**string **类重载了输入输出运算符，可以像对待普通变量那样对待 string 变量
也就是用>>进行输入，用<<进行输出。
请看下面的代码：

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    cin>>s;  //输入字符串
    cout<<s<<endl;  //输出字符串
    return 0;
}

运行结果：

http://c.biancheng.net http://vip.biancheng.net↙
http://c.biancheng.net

虽然我们输入了两个由空格隔开的网址，但是只输出了一个，这是因为输入运算符>>默认会忽略空格，遇到空格就认为输入结束，所以最后输入的http://vip.biancheng.net没有被存储到变量 s。

访问字符串中的字符

string 字符串也可以像C风格的字符串一样按照下标来访问其中的每一个字符。
string 字符串的起始下标仍是从 0 开始。
请看下面的代码：

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s = "1234567890";
    for(int i=0,len=s.length(); i<len; i++){
        cout<<s[i]<<" ";
    }
    cout<<endl;
    s[5] = '5';
    cout<<s<<endl;
    return 0;
}

运行结果：

1 2 3 4 5 6 7 8 9 0

1234557890

本例定义了一个 string 变量 s，并赋值 "1234567890"，之后用 for 循环遍历输出每一个字符。借助下标，除了能够访问每个字符，也可以修改每个字符，s[5] = '5';就将第6个字符修改为 '5'，所以 s 最后为 "1234557890"。

字符串的拼接

有了 string 类，我们可以使用 + 或 += 运算符来直接拼接字符串，非常方便
再也不需要使用C语言中的 strcat()、strcpy()、malloc() 等函数来拼接字符串了
再也不用担心空间不够会溢出了。
用+来拼接字符串时，
- 运算符的两边可以都是 string 字符串
- 也可以是一个 string 字符串和一个C风格的字符串
- 还可以是一个 string 字符串和一个字符数组
- 或者是一个 string 字符串和一个单独的字符
请看下面的例子：

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s1 = "first ";
    string s2 = "second ";
    char *s3 = "third ";
    char s4[] = "fourth ";
    char ch = '@';
    string s5 = s1 + s2;
    string s6 = s1 + s3;
    string s7 = s1 + s4;
    string s8 = s1 + ch;
    
    cout<<s5<<endl<<s6<<endl<<s7<<endl<<s8<<endl;
    return 0;
}

运行结果：

first second

first third

first fourth

first @

string 字符串的增删改查

C++ 提供的 string 类包含了若干实用的成员函数，大大方便了字符串的增加、删除、更改、查询等操作。

插入字符串

insert() 函数可以在** string 字符串中指定的位置插入**另一个字符串，它的一种原型为：

string& insert (size_t pos, const string& str);

pos 表示要插入的位置，也就是下标；str 表示要插入的字符串，可以是** string 字符串，也可以是C风格的字符串**。
**insert() **函数的第一个参数有越界的可能，如果越界，则会产生运行时异常

例1

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s1, s2, s3;
    s1 = s2 = "1234567890";
    s3 = "aaa";
    s1.insert(5, s3);
    cout<< s1 <<endl;
    s2.insert(5, "bbb");
    cout<< s2 <<endl;
    return 0;
}

运行结果：

12345aaa67890

12345bbb67890

删除字符串

erase() 函数可以删除 string 中的一个子字符串。
它的一种原型为：

string& erase (size_t pos = 0, size_t len = npos);

pos 表示要删除的子字符串的起始下标，len 表示要删除子字符串的长度。
如果**不指明 len **的话，那么直接删除从 pos 到字符串结束处的所有字符（此时 len = str.length - pos）。
有读者担心，在 pos 参数没有越界的情况下， len 参数也可能会导致要删除的子字符串越界。但实际上这种情况不会发生，erase() 函数会从以下两个值中取出最小的一个作为待删除子字符串的长度：
- len 的值；
- 字符串长度减去 pos 的值。
说得简单一些，待删除字符串最多只能删除到字符串结尾。

例1

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s1, s2, s3;
    s1 = s2 = s3 = "1234567890";
    s2.erase(5);
    s3.erase(5, 3);
    cout<< s1 <<endl;
    cout<< s2 <<endl;
    cout<< s3 <<endl;
    return 0;
}

运行结果：

1234567890
12345
1234590

提取子字符串

substr() 函数用于从 string 字符串中提取子字符串
它的原型为：

string substr (size_t pos = 0, size_t len = npos) const;

pos 为要提取的子字符串的起始下标，len 为要提取的子字符串的长度。
系统对substr() 参数的处理和erase()类似：
- 如果 pos 越界，会抛出异常；
- 如果 len 越界，会提取从 pos 到字符串结尾处的所有字符。

例1

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s1 = "first second third";
    string s2;
    s2 = s1.substr(6, 6);
    cout<< s1 <<endl;
    cout<< s2 <<endl;
    return 0;
}

first second third
second

字符串查找

string 类提供了几个与字符串查找有关的函数

find() 函数

find() 函数用于在 string 字符串中查找子字符串出现的位置
它其中的两种原型为：

size_t find (const string& str, size_t pos = 0) const;
size_t find (const char* s, size_t pos = 0) const;

第一个参数为待查找的子字符串，它可以是 string 字符串，也可以是C风格的字符串。
第二个参数为开始查找的位置（下标）；如果不指明，则从第0个字符开始查找。
find()函数最终返回的是子字符串第一次出现在字符串中的起始下标。
如果没有查找到子字符串，那么会返回 string::npos，它是 string 类内部定义的一个静态常成员，用来表示 size_t 类型所能存储的最大值。

例1

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s1 = "first second third";
    string s2 = "second";
    int index = s1.find(s2,5);
    if(index < s1.length())
        cout<<"Found at index : "<< index <<endl;
    else
        cout<<"Not found"<<endl;
    return 0;
}

运行结果：

Found at index : 6

转换为C风格的字符串

虽然 C++ 提供了 string 类来替代C语言中的字符串
但是在实际编程中，有时候必须要使用C风格的字符串（例如打开文件时的路径）
为此，string 类为我们提供了一个转换函数 c_str()，该函数能够将 string 字符串转换为C风格的字符串，并返回该字符串的 const 指针（const char*）。
请看下面的代码：

//为了使用C语言中的 fopen() 函数打开文件，必须将 string 字符串转换为C风格的字符串。
string path = "D:\\demo.txt";
FILE *fp = fopen(path.c_str(), "rt");

二.vector

介绍

简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。
vector是变长数组，支持随机访问，不支持在任意位置O(1)插入。
为了保证效率，元素的增删一般应该在末尾进行。
容器特性
- 顺序序列：
  - 顺序容器中的元素按照严格的线性顺序排序。
  - 可以通过元素在序列中的位置访问对应的元素。
- 动态数组
  - 支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。
  - 操供了在序列末尾相对快速地添加/删除元素的操作。
- 能够感知内存分配器的（Allocator-aware）
  - 容器使用一个内存分配器对象来动态地处理它的存储需求。
优缺点
- 优点
  - 使用的时候无须声明上限，随着元素的增加，vector的长度会自动增加；
  - vector类提供额外的方法来增加、删除元素，比数组操作高效。
- 缺点
  - 时间：运行速度与数组相比较慢。
  - 空间：clear()无法清空内存

头文件及命名空间

#include <vector>
using namespace std;

vector的初始化

例1

#include<iostream>
#include<vector>
using namespace std;
//vector的初始化
int main()
{
	vector<int> vec1;
	vector<float> vec2(3);
	vector<char> vec3(3,'a');
	vector<char> vec4(vec3);
	return 0 ;
}

例子展示了几种不同的vector的初始化方法。可以看到在4个vector的初始化中，用<>指定了vector中的不同元素类型。
- 第一个是空的整形vector，我们没有给他添加任何元素。
- 第二个初始化了一个有3个元素的vector，由于并没有指定初始值，将会使用编译器默认的初始值。
- 第三个初始化了含有3个a的字符vector，括号中第二个值代表着所有元素的指定值。
- 第四个vector通过拷贝vec3中的元素初始化vec4，它们的元素会一模一样。

例2


//整形数组
 vector <int> vec = { 1,2,3,4,5};
//char型数组
 vector <char> vec1 = {'h','e','l' ,'l' ,'o' };
 //字符串数组
 vector <string> vec1 = {"Hello","world"};

例3

vector<int> vec(a.begin(),a.begin+1);//把a的从开始到第二个赋值给vec

添加与插入元素

//在vector的末尾插入新元素
vec.push_back(1);

//在迭代器的前面插入新元素
vector<int>::iterator it;
it=vec.begin();
vec.insert(it,5);//在第一个元素前面插入5

//在vector中加入3个1元素，同时清除掉以前的元素
vec.assign(3,1);//现在vector中只有3个1

删除与清空元素

//删除最后一个元素
vec.pop_back();

//删除指定位置的元素
vec.erase(vec.begin());//删除第一个位置的元素值

//清除所有元素
vec.clear();

//判断该数组是否为空
vec.empty();

判空与得到大小

size()函数返回vector的实际长度（包含的元素个数）
empty()函数返回一个bool类型，表明vector是否为空。空则返回ture，不空则返回false
二者的时间复杂度都是O(1)。
所有的STL容器都支持这两个方法，含义也相同。

访问元素

利用下标进行访问

像数组一样利用下标进行访问

vector<int> a;
for(int i=0;i<a.size();i++)
{
     cout<<a[i];
}

利用迭代器进行访问

迭代器就像STL容器的“指针”，可以用星号*操作符解除引用。
一个保存int的vector的迭代器声明方法为：
```
  `vector<int>::iterator it;`
```
vector的迭代器是“随机访问迭代器”
可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。
可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。

例1

vector<int>::iterator it;
for(it=a.begin();it!=a.end();it++)
{
   cout<<*it;
}

特殊访问

begin()/end()

begin()函数返回指向vector中第一个元素的迭代器。
例如a是一个非空的vector，则*a.begin()与a[0]的作用相同。
所有的容器都可以视作一个“前闭后开”的结构
end()函数返回vector的尾部，即第n个元素再往后的“边界”。
*a.end()与a[n]都是越界访问，其中n=a.size()。
下面两份代码都遍历了vectora，并输出它的所有元素。

for (int i = 0; i < a.size(); i ++) 
    cout << a[i] << endl;

for (vector<int>::iterator it = a.begin(); it != a.end(); it ++) 
    cout << *it << endl;

front()/back()

front()函数返回vector的第一个元素，等价于*a.begin() 和 a[0]。
back()函数返回vector的最后一个元素，等价于*--a.end() 和 a[a.size() – 1]。

用vector创建动态二维数组

//利用vector数组
//n行m列，即a[n][m]
cin>>n>>m;
vector<vector <int> >a(n);
for(int i=0;i<n;i++)
{
	a[i].resize(m);
}

算法

1.reverse()翻转元素

使用reverse()将vector元素翻转：需要头文件 #include

//将元素翻转，即逆序排列
reverse(a.begin(), a.end());

使用reverse()也可以翻转一个数组，元素存放在下标1~n

reverse(a + 1, a + 1 + n);

2.unique() 去重元素

使用 unique()去重：需要头文件 #include
返回去重之后的尾迭代器
仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。
该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。
把一个vector去重，并得到去重后的元素个数：

int m = unique(a.begin(), a.end()) – a.begin();

也可以把一个数组去重，元素存放在下标1~n
返回去重之后的尾指针
把一个数组去重，并得到去重后的元素个数：

int m = unique(a + 1, a + 1 + n) – (a + 1);

3.sort()排序元素

sort()函数详情可跳转至：

C++中sort()函数详解

使用 sort ()排序：需要头文件 #include
默认是按升序排列，即从小到大：

sort(vec.begin(),vec.end());

可以通过重写排序比较函数按照降序比较：

bool cmp(const int &a,const int &b)
{
    return a>b;
}
sort(vec.begin(),vec.end(),Comp);

4.lower_bound()/upper_bound() 二分查找

两个迭代器（指针）指定的部分应该是提前排好序的。
lower_bound() 的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。
upper_bound() 的用法和lower_bound()大致相同，唯一的区别是查找第一个大于x的元素。
在**有序 **vector 中查找小于等于x的最大整数（假设一定存在）：

int y = *--upper_bound(a.begin(), a.end(), x);

在有序int数组（元素存放在下标1~n）中查找大于等于x的最小整数的下标：

int y = lower_bound(a + 1, a + 1 + n, x) – a;

三.stack

介绍

stack 翻译为栈，是 STL 中实现的一个后进先出的容器。

头文件及命名空间

#include <stack>
using namespace std;

stack常用操作

stack<int> q;	//声明，以int型为例
int x;
q.push(x);		//将x压入栈顶
q.top();		//返回栈顶的元素
q.pop();		//删除栈顶的元素
q.size();		//返回栈中元素的个数
q.empty();		//检查栈是否为空,若为空返回true,否则返回false

例1

#include<iostream>
#include<stack>
using namespace std;
int main()
{
	stack<int>  q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	
	cout<<"q.size "<<q.size()<<endl;
	cout<<"q.top "<<q.top()<<endl;   //输出栈顶元素 
	
	q.pop();	//删除栈顶元素
			
	cout<<"q.size "<<q.size()<<endl;  
	cout<<"q.top "<<q.top()<<endl;
	
	return 0; 
}

运行结果：

清空stack

清空stack没有现成函数
可以采用以下方法：

//遍历出栈
stack<int> s;
while(!s.empty()) s.pop();
// stack操作的是堆内存，所以要一个一个弹出。

或

//使用swap()
stack<int> s;
stack<int>().swap(s);
// swap相当于交换了s和一个空临时stack的内容，然后临时stack再结束生命周期
//但由于操作的是堆空间，其实还是一个一个释放空间。

四.queue

介绍

queue 翻译为队列，在 STL 中主要则是实现了一个先进先出的容器。

头文件及命名空间

#include<queue>
using namespace std;

queue常用操作

queue<int> q;	//声明，以int型为例
int x;
q.push(x);		//在队尾插入一个元素x
q.front() 	    //返回队列中的第一个元素
q.back()        //返回队列中最后一个元素
q.pop();		//删除队列第一个元素
q.size();		//返回队列中元素个数
q.empty();		//检查队列是否为空,若为空返回true,否则返回false

清空queue

C++中的queue自身是不支持clear()操作的，
但是双端队列deque是支持clear()操作的。
有以下方法清空queue：

//遍历出队列
queue<int> q;
while (!q.empty()) q.pop();

或

//使用swap()
queue<int> q;
queue<int>().swap(q);

五.priority_queue

介绍

priority_queue 又称为优先队列，其底层是用堆来进行实现的。
在优先队列中，队首元素一定是当前队列中优先级最高的那一个。
在优先队列中，优先级高的元素先出队列，并非按照先进先出的要求
可以以O(log n) 的效率查找一个队列中的最大值或最小值，其中是最大值还是最小值是根据创建的优先队列的性质来决定的。

头文件及命名空间

与queue相同

#include<queue>
using namespace std;

模板参数

优先队列有三个参数，其声明形式为：

priority_queue< type, container, function >

这三个参数，后面两个可以省略，第一个不可以。
其中：
1. type：数据类型；
2. container：实现优先队列的底层容器；
3. function：元素之间的比较方式；
对于container，要求必须是数组形式实现的容器，例如vector、deque，而不能使list。
在STL中，默认情况下（不加后面两个参数）是以vector为容器，以 operator< 为比较方式
所以在只使用第一个参数时，优先队列默认是一个大顶堆，每次输出的堆顶元素是此时堆中的最大元素。

priority_queue常用操作

和循环队列queue不一样的是，优先队列没有front()和back()函数
而只能通过**top()**函数来访问队首元素，也就是优先级最高的元素。

priority_queue <int> q;
int x;
q.push(x);		//在队尾插入一个元素x
q.top() 	    //返回优先队列的队顶元素
q.pop();		//删除队列第一个元素
q.size();		//返回队列中元素个数
q.empty();		//检查队列是否为空,若为空返回true,否则返回false

priority_queue 内元素优先级的设置

大顶堆与小顶堆(以int型为例)

需要注意的是，如果使用less和greater，需要头文件：

#include <functional>

大顶堆（降序）

//构造一个空的优先队列（此优先队列默认为大顶堆）
priority_queue<int> big_heap;

或

priority_queue<int,vector<int>,less<int> > big_heap;

小顶堆（升序）

//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;

六.deque

介绍

deque容器为一个给定类型的元素进行线性处理
它就像是vector和queue的结合。
- 与vector相比，deque在头部增删元素仅需要O(1)的时间；
- 与queue相比，deque像数组一样支持随机访问。
像向量一样，它能够快速地随机访问任一个元素，并且能够高效地插入和删除容器的尾部元素。
但它又与vector不同，deque支持高效插入和删除容器的头部元素，因此也叫做双端队列。

deque和vector的联系

区别

deque 两端都能快速安插元素和移除元素（vector 只在尾端逞威风)。
访问元素时 deque 内部结构会多一个间接过程，所以元素的访问和迭代器的动作会稍稍慢一些。
deque没有所谓的capacity观念
- 因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。
- 换句话说，像vector那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque中是不会发生的。
- 也因此，deque没有必要提供所谓的空间预留（reserved）功能。
虽然deque也提供Random Access Iterator，但它的迭代器并不是普通指针
- 其复杂度和vector不可同日而语
- 这当然涉及到各个运算层面
- 因此，除非必要，我们应尽可能选择使用vector而非deque
- 对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，将vector排序后（利用STL的sort算法），再复制回deque。

相同点

在中段安插、移除元素的速度相对较慢，因为所有元素都需移动以腾出或填补空间。
迭代器属于 random-access iterator (随机访问迭代器)。

容器的选择

以下情形最好采用 deque：
- 你需要在两端安插和移除元素(这是 deque 的拿手好戏)。
- 无须指向(refer to)容器内的元素。
- 要求“不再使用的元素必须释放”(不过 C++ standard 对此无任何保证)。

1、强调快速随机访问，则vector比list好得多。
2、已知要存储元素的个数，vector好于list。
3、强调增删且不要在两端插入修改元素，则list显然要比vector好。
4、除非我们需要在容器首部插入和删除元素，deque好于vector。

头文件及命名空间

#include<deque>
using namespace std;

deque操作

声明与初始化

#include<deque>
deque<type> deq;                   //声明一个元素类型为 type 的双端队列 deq
deque<type> deq(nSize);            //声明含有 nSize 个默认初始化元素的 deq
deque<type> deq(nSize, value)      //声明含有 nSize 个值为 value 的元素的deq
deque<type> deq(MyDeque);          //复制MyDeque到deq
deque<type> deq(first, last);      //使用迭代器first，last范围内的元素初始化deq

常用成员函数

deq[nPos];              //访问双向队列中 nPos 位置上的元素
deq.front();            //返回第一个元素
deq.back();             //返回最后一个元素
deq.push_front(x);      //把元素 x 插入到 deq 的头部
deq.pop_front();        //弹出 deq 的第一个元素
deq.push_back(x);       //把元素 x 插入到 deq 的尾部
deq.pop_back();         //弹出 deq 的最后一个元素

deque插入操作

insert(pos,elem);     //在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);   //在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);  //在pos位置插入[beg,end)区间的数据，无返回值。

deque删除和清空操作

erase(beg,end);    //删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);        //删除pos位置的数据，返回下一个数据的位置。
clear();           //移除容器的所有数据

七.pair

介绍

pair是将2个数据组合成一个数据，当需要这样的需求时就可以使用pair。
- STL中的map就是将key和value放在一起来保存。
- 另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair
pair 实际上可以看作一个内部有两个元素的结构体，且这两个元素的类型是可以指定的
如下面的短代码所示：

struct pair 
{
    typeName1 first;
    typeName2 second;
};

头文件及命名空间

#include <utility>
using namespace std;

由于 map 的内部实现中涉及 pair，因此添加 map 头文件时会自动添加 utility 头文件
此时如果需要使用 pair，就不需要额外再去添加 utility 头文件了。
因此，记不住 utility拼写时，可以偷懒地用 map 头文件来代替 utility 头文件：

#include <map>
using namespace std;

声明与初始化

pair<int, double> p1; //使用默认构造函数
pair<int, double> p2(1, 2.4); //用给定值初始化
pair<int, double> p3(p2); //拷贝构造函数

生成新的pair对象

可以利用make_pair()创建新的pair对象

例1

pair<int, double> p1;
p1 = make_pair(1, 1.2);
cout << p1.first <<' '<< p1.second << endl;

运行结果：

1 1.2

访问两个元素（通过first和second）

访问两个元素操作可以通过first和second访问

例1

pair<int ,double> p1;
p1.first = 1; 
p1.second = 2.5; 
cout<<p1.first<<' '<<p1.second<<endl;

运行结果：

1 2.5

临时构建一个 pair

方法一

将类型定义写在前面，后面用小括号内两个元素的方式
如下：

pair<string,int>("haha",5);

方法二

使用自带的** make_pair() **函数
如下：

make_pair("haha",5)

pair大小比较

utility头文件中除了提供创建 pair 对象的方法之外，还为 pair 对象重载了六个运算符
这六个运算符是：<、<=、>、>=、==、!=
其运算规则是：
- 对于进行比较的 2 个 pair 对象，先以 first 的大小作为标准
- 只有当** first 相等**时才去判别 second 的大小。
对于进行比较的 2 个 pair 对象，其对应的键和值的类型必须相同，否则将没有可比性，
同时编译器提示没有相匹配的运算符，即找不到合适的重载运算符。

pair的常见用途

代替二元结构体

pair用来代替二元结构体及其构造函数，可以节省编码时间。

作为 map 的键值

作为 map 的键值对来进行插入

例1

#include<iostream>
#include<string>
#include <map>
using namespace std;
int main()
{
    map<string,int> mp;
    mp.insert (make pair("heihei",5));
    mp.insert(pair<string,int>("haha",10));
    for(map<string,int>::iterator it=mp.begin();it!= mp.end();it++)
    {
        cout << it->first <<""<< it->second << endl;
    }
    return 0;
}

运行结果：

haha 10
heihei 5

八.set

C++ STL中标准关联容器set, multiset, map, multimap，
内部采用的是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。
RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。

介绍

set 就是集合，STL的 set 用红黑树(二叉树)实现
集合中的每个元素只出现一次(参照数学中集合的互斥性)
并且是排好序的(默认按键值升序排列)
访问元素的时间复杂度是O (log ⁡n)

头文件及命名空间

#include <set>
using namespace std;

set常用操作

set<int> q;     //以int型为例 默认按键值升序
set<int,greater<int>> p;  //降序排列 
int x;

q.insert(x);	//将x插入q中
q.erase(x);		//删除q中的x元素,返回0或1,0表示set中不存在x
q.clear();		//清空q

q.empty();		//判断q是否为空，若是返回1，否则返回0
q.size();		//返回q中元素的个数

q.find(x);		//在q中查找x，返回x的迭代器，若x不存在，则返回指向q尾部的迭代器即 q.end()
q.lower_bound(x); //返回一个迭代器，指向第一个键值不小于x的元素
q.upper_bound(x); //返回一个迭代器，指向第一个键值大于x的元素
q.count(x)        //返回集合s中等于x的元素个数

q.rend();		  //返回第一个元素的的前一个元素迭代器
q.begin();		  //返回指向q中第一个元素的迭代器

q.end();		 //返回指向q最后一个元素下一个位置的迭代器
q.rbegin();		 //返回最后一个元素的迭代器

s.insert(x)把一个元素x插入到集合s中
- 时间复杂度为O(logn)。
- 在set中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。
erase()
- 设it是一个迭代器，s.erase(it) 从s中删除迭代器it指向的元素，时间复杂度为O(logn)
- 设x是一个元素，s.erase(x)从s中删除所有等于x的元素，时间复杂度为O(k+logn)，其中k是被删除的元素个数。
s.find(x) 在集合s中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回s.end()。时间复杂度为O(logn)。
lower_bound/upper_bound这两个函数的用法与find类似，但查找的条件略有不同
- 时间复杂度为 O(logn)
- s.lower_bound(x) 查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
- s.upper_bound(x) 查找大于x的元素中最小的一个，并返回指向该元素的迭代器。
count() 用来查找set中某个某个键值出现的次数。
- 时间复杂度为O(k +logn)，其中k为元素x的个数。
- 这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次
- 这样就变成了判断某一键值是否在set出现过了
begin()/end()返回集合的首、尾迭代器
- 时间复杂度均为O(1)。
- s.begin() 是指向集合中最小元素（默认）的迭代器。
- s.end() 是指向集合中最大元素（默认）的下一个位置的迭代器。
- 换言之，就像vector一样，是一个“前闭后开”的形式。
- 因此--s.end()是指向集合中最大元素（默认）的迭代器。

set的迭代器

set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”
支持星号*解除引用，仅支持++和--两个与算术相关的操作。
设it是一个迭代器，例如set<int>::iterator it;
- it++，则it会指向“下一个”元素。这里的下一个元素是指在元素从小到大排序（默认）的结果中，排在it下一名的元素。
- 同理，it--，则 it 将会指向排在“上一个”的元素。
--s.end()是指向集合中最大元素（默认）的迭代器

九.multiset

介绍

头文件set主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集合”
即前者的元素不能重复，而后者可以包含若干个相等的元素。
set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同。
set和multiset的最大区别：set支持去重， multiset不支持

头文件及命名空间

multiser的头文件及命名空间与set相同

#include <set>
using namespace std;

十.map

介绍

map是 stl 的一个关联容器，它提供一对一的hash。
- 第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
- 第二个可能称为该关键字的值(value)；
map容器是一个键值对key-value的映射
其内部实现是一棵以key为关键码的红黑树。
map的key和value可以是任意类型，其中key必须定义小于号运算符。
map内部是自动排序的，map的排序默认按照key从小到大进行排序

头文件及命名空间

#include <map>
using namespace std;

声明

map<key_type, value_type> name;
如下：

map<long long, bool> vis;
map<string, int> hash;
map<pair<int, int>, vector<int>> test;

插入操作

用insert函数插入pair

如下：

mapStudent.insert(pair<int, string>(000, "student_zero"));

insert函数插入value_type数据

如下：

mapStudent.insert(map<int, string>::value_type(001, "student_one"));

用"array"方式插入

如下：

mapStudent[123] = "student_first";
mapStudent[456] = "student_second";

方法比较

以上三种用法，虽然都可以实现数据的插入，但是它们是有区别的
当然第一种和第二种在效果上是完成一样的
用insert()函数插入数据，在数据的插入上涉及到集合的唯一性这个概念
即当map中有这个关键字时，insert()操作是不能再插入数据的
但是用数组方式就不同了，它可以覆盖以前该关键字对应的值

访问元素

通过下标进行访问

h[key] 返回key映射的value的引用，时间复杂度为O(logn)。
[]操作符是map最吸引人的地方：
- 可以很方便地通过h[key]来得到key对应的value
- 还可以对h[key]进行赋值操作，改变key对应的value

通过迭代器进行访问

map可以使用it->first来访问键，使用it->second访问值
如下：

#include<map>
#include<iostream>
using namespace std;
int main()
{
   map<char,int>maps;
   maps['d']=10;
   maps['e']=20;
   maps['a']=30;
   maps['b']=40;
   maps['c']=50;
   maps['r']=60;
   for(map<char,int>::iterator it=maps.begin();it!=maps.end();it++)
   {
       cout<<it->first<<" "<<it->second<<endl;
   }
   return 0;
}

运行结果：
J6T}_BY1KLJ%9L$SZ`WGA6N.png

删除与清空元素

从map中删除元素的函数是erase()，该函数有如下的三种形式：
- size_t erase( const key_type& key );
  - 根据key来进行删除
  - 返回删除的元素数量，在map里结果非0即1
- iterator erase( iterator pos )
  - 删除迭代器指向位置的键值对
  - 并返回一个指向下一元素的迭代器
- iterator erase( const_iterator first, const_iterator last );
  - 删除一定范围内的元素
  - 并返回一个指向下一元素的迭代器
如下：

//用关键字刪除
int n = mapStudent.erase("123"); //如果刪除了會返回1，否則返回0

//迭代器刪除
iter = mapStudent.find("123");
mapStudent.erase(iter);

//用迭代器范围刪除 
mapStudent.erase(mapStudent.begin(), mapStudent.end());//等同于mapStudent.clear()

清空元素：maps.clear()

查找元素

find()函数有两种形式：
- iterator find (const key_type& k);
- const_iterator find (const key_type& k) const;
返回键是key的映射的迭代器
若存在，返回指向该key的迭代器
若不存在，则返回迭代器的尾指针，即** mymap.end()**，即 -1
如下

map<string,int>::iterator it;
it=maps.find("123");

map的得到大小与判空

在往map里面插入了数据，我们怎么知道当前已经插入了多少数据呢，可以用size()函数
用法如下：

int nSize = mapStudent.size();

判断其是否为空函数：maps.empty()

查找关键字出现的次数

count(k) 查找关键字k出现的次数，如果不存在则为0
函数形式：size_type count (const key_type& k) const;

标签：vector,string,迭代,STL,元素,C++,详解,字符串,include
From： https://www.cnblogs.com/zhengzirui/p/16951303.html

C++中STL容器详解

一.string

参考文章

介绍

头文件及命名空间

定义 string 变量

例1

例2

得到长度

输入与输出

访问字符串中的字符

字符串的拼接

string 字符串的增删改查

插入字符串

例1

删除字符串

例1

提取子字符串

例1

字符串查找

find() 函数

例1

转换为C风格的字符串

二.vector

介绍

头文件及命名空间

vector的初始化

例1

例2

例3

添加与插入元素

删除与清空元素

判空与得到大小

访问元素

利用下标进行访问

利用迭代器进行访问

例1

特殊访问

begin()/end()

front()/back()

用vector创建动态二维数组

算法

1.reverse()翻转元素

2.unique() 去重元素

3.sort()排序元素

4.lower_bound()/upper_bound() 二分查找

三.stack

介绍

头文件及命名空间

stack常用操作

例1

清空stack

四.queue

介绍

头文件及命名空间

queue常用操作

清空queue

五.priority_queue

介绍

头文件及命名空间

模板参数

priority_queue常用操作

priority_queue 内元素优先级的设置

大顶堆与小顶堆(以int型为例)

大顶堆（降序）

小顶堆（升序）

六.deque

介绍

deque和vector的联系

区别

相同点

容器的选择

头文件及命名空间

deque操作

声明与初始化

常用成员函数

deque插入操作

deque删除和清空操作

七.pair

介绍