STL常用知识点

STL(标准模版本库)常用知识点总结

vector(向量)用法

1.定义

使用vector，需要添加头文件#include <vector>。
单独定义一个vector: vector<typename> name;
相当于是一维数组name[SIZE]，只不过长度可以变化，和一维数组一样，typename可以是任何数据类型，例如int、char、double、结构体、也可以是STL标准容器，例如vector、set、queue，需要注意的是，如果typename也是一个STL容器，定义的时候需要在>>符号之间加上空格。因为C++ 11之前标准的编译器会把它视为移位操作。如果typename是vector，如vector<vector<int> > name。

二维数组是一维是一个数组的数组，vector数组也是一样的，Arrayname[]中的每一个元素都是一个vector，可以看成两个维都可变的二维数组。定义vector数组 vector<typename> Arrayname[arraySizw];（例如vector<int> vi[100]这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是一个vector容器，与vector<vector<int> >name不同的是，这种写法一维长度已经固定为arraySize,另一维才是变长。

• vector<int> a(10); //定义了10个整型元素的向量（尖括号中为元素类型名，它可以是任何合法的数据类型），但没有给出初值，其值是不确定的。
• vector<int> a(10,1); //定义了10个整型元素的向量,且给出每个元素的初值为1
• vector<int> a(b); //用b向量来创建a向量，整体复制性赋值
• vector<int> a(b.begin(),b.begin+3); //定义了a值为b中第0个到第2个（共3个）元素
• int b[7]={1,2,3,4,5,9,8}; vector<int> a(b,b+7); //从数组中获得初值

2.基本操作

• a.pop_back(); //删除a向量的最后一个元素
• a.push_back(5); //在a的最后一个向量后插入一个元素，其值为5
• a.back(); //返回a的最后一个元素
• a.front(); //返回a的第一个元素
• a[i]; //返回a的第i个元素，当且仅当a[i]存在
• a.clear(); //清空a中的元素
• a.empty(); //判断a是否为空，空则返回ture,不空则返回false
• a.assign(b.begin(), b.begin()+3); //b为向量，将b的0~2个元素构成的向量赋给a
• a.assign(4,2); //是a只含4个元素，且每个元素为2
• a.erase(a.begin()+1,a.begin()+3); //删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+3（不包括它）用于删除指定位置元素
• a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4用于向指定位置插入元素
• a.insert(a.begin()+1,3,5); //在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5
• a.insert(a.begin()+1,b+3,b+6); //b为数组，在a的第1个元素（从第0个算起）的位置插入b的第3个元素到第5个元素（不包括b+6），如b为1,2,3,4,5,9,8 ，插入元素后为1,4,5,9,2,3,4,5,9,8
• a.size(); //返回a中元素的个数；
• a.capacity(); //返回a在内存中总共可以容纳的元素个数
• a.resize(10); //将a的现有元素个数调至10个，多则删，少则补，其值随机
• a.resize(10,2); //将a的现有元素个数调至10个，多则删，少则补，其值为2
• a.reserve(100); //将a的容量（capacity）扩充至100，也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才显得有意义，因为这将避免内存多次容量扩充操作（当a的容量不足时电脑会自动扩容，当然这必然降低性能）
• a.swap(b); //b为向量，将a中的元素和b中的元素进行整体性交换
• a==b; //b为向量，向量的比较操作还有!=,>=,<=,>,<
• find() 函数来查找指定值的元素，或者使用迭代器来遍历查找。

①使用 find() 函数查找：
	vector<int> myVector = { 100,200,300,400,500,600 };
	vector<int>::iterator it = find(myVector.begin(), myVector.end(), 500);
	//输出内容为：目标元素的索引为: 4
	if (it != myVector.end()) {
		cout << "目标元素的索引为: " << distance(myVector.begin(), it) <<endl;
	}
	else {
		cout << "没有找到" <<endl;
	}
②使用迭代器遍历查找：
	vector<int> myVector = { 100,200,300,400,500,600 };
	bool found = false;
	int valueToFind = 300;
	//输出内容为：目标元素的索引为: 2
	for (vector<int>::iterator it = myVector.begin(); it != myVector.end(); ++it) {
		if (*it == valueToFind) {
			cout << "目标元素的索引为: " << distance(myVector.begin(), it) << endl;
			found = true;
			break;
		}
	}
	if (!found) {
		cout << "没有找到" << endl;
	}

• 访问方法

cout<<"直接利用数组："; 
for(int i=0;i<10;i++)//方法一 
{
    cout<<obj[i]<<" ";
}
cout<<endl; 
cout<<"利用迭代器：" ;
//方法二，使用迭代器(iterator)将容器中数据输出 
vector<int>::iterator it;//声明一个迭代器(类似一个指针)，来访问vector容器，作用：遍历或者指向vector容器的元素 
for(it=obj.begin();it!=obj.end();it++)
{
    cout<<*it<<" ";
}

• 定义五行六列二维数组

//法一
vector<vector<int> > obj(5); //定义二维动态数组大小5行 
    for(int i =0; i< obj.size(); i++)//动态二维数组为5行6列，值全为0 
    { 
        obj[i].resize(6); 
    } 
//法二
vector<vector<int> > obj(5, vector<int>(6)); //定义二维动态数组5行6列 

几种重要的算法，使用时需要包含头文件：#include

• sort(a.begin(),a.end()); // 对a中的从a.begin()（包括它）到a.end()（不包括它）的元素进行从小到大排列
• reverse(a.begin(),a.end()); // 对a中的从a.begin()（包括它）到a.end()（不包括它）的元素倒置，但不排列，如a中元素为1,3,2,4,倒置后为4,2,3,1
• copy(a.begin(),a.end(),b.begin()+1); // 把a中的从a.begin()（包括它）到a.end()（不包括它）的元素复制到b中，从b.begin()+1的位置（包括它）开始复制，覆盖掉原有元素
• find(a.begin(),a.end(),10); // 在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，若存在返回其在向量中的位置

set(集合)用法

1.定义

使用set需要添加头文件，#include <set>
单独定义set<typename> name,typename可以是任何类型，结构体、STL标准容器也可以
set<Type> s(s1) //定义一个set容器，并用容器s1来初始化
set<Type> s(b, e) //b和e分别为迭代器的开始和结束的标记
set<Type> s(s1.begin(), s1.begin()+3) //用容器s1的第0个到第2个值初始化s
set<Type> s(a, a + 5) //将a数组的元素初始化vec向量，不包括a[4]
set<Type> s(&a[1], &a[4]) //将a[1]~a[4]范围内的元素作为s的初始值

• 每个元素的键值都唯一，不允许两个元素有相同的键值。
• 所有元素都会根据元素的键值自动排序（默认从小到大）。
• set 中的元素不像 map 那样可以同时拥有实值(value)和键值(key)，只能存储键，是单纯的键的集合。
• set 中元素的值不能直接被改变。
• set 支持大部分的map的操作，但是 set 不支持下标的操作，而且没有定义mapped_type类型。

2.基本操作

• set只能通过迭代器iterator访问，除string和vector外的STL容器都不支持*(it+i)的访问形式
• s.begin() //返回指向第一个元素的迭代器
• s.end() //返回指向最后一个元素的迭代器
• s.clear() //清除所有元素
• s.count(值) //返回某个值元素的个数
• s.empty() //如果集合为空，返回true，否则返回false
• s.equal_range() //返回集合中与给定值相等的上下限的两个迭代器
• s.erase() //删除集合中的元素
• s.find(k) //返回一个指向被查找到元素的迭代器
• s.insert() //在集合中插入元素,并自动排序和去重
• s.lower_bound(k) //返回一个迭代器，指向键值大于等于k的第一个元素
• s.upper_bound(k) //返回一个迭代器，指向键值大于k的第一个元素
• s.max_size() //返回集合能容纳的元素的最大限值
• s.rbegin() //返回指向集合中最后一个元素的反向迭代器
• s.rend() //返回指向集合中第一个元素的反向迭代器
• s.size() //集合中元素的数目
• erase(iterator) ：删除定位器iterator指向的值,iterator为迭代器，可通过find函数查找
• erase(first,second)：删除定位器first和second之间的值
• erase(key_value)：删除键值key_value的值，key_value为所需要删除元素的值
• find用法返回set中对应值为value的迭代器

//返回一个指向被查找到元素的迭代器，如果没找到则返回end()
#include <iostream>
#include <set>
using namespace std;
int main(){
     int a[] = {4,5,6};
     set<int> s(a,a+3);
     set<int>::iterator it;
     if((it=s.find(4))!=s.end())
         cout<<*it<<endl;
     return 0;
}
输出结果：4

• insert() 的用法

insert(key_value)：将key_value插入到set中 ，返回值是pair\<set::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置；若key_value已经在set中，则iterator表示的key_value在set中的位置。  
inset(first,second);将定位器first到second之间的元素插入到set中，返回值是void.
#include <iostream>
#include <set>
using namespace std;
int main(){
     int a[] = {1,2,3};
     set<int> s;
     set<int>::iterator it;
     s.insert(a,a+3);
     for(it=s.begin(); it!=s.end(); ++it)
         cout<<*it<<" ";
     cout<<endl;
     pair<set<int>::iterator,bool> pr;
     pr=s.insert(5);
     if(pr.second)
         cout<<*pr.first<<endl;
     cout<<"插入数值之后的set中有："<<endl;
	 for(it=s.begin(); it!=s.end(); ++it)
		cout<<*it<<" ";
	 cout<<endl;
     return 0;
}
输出结果：
1 2 3
5
插入数值之后的set中有：
1 2 3 5

• lower_bound()、upper_bound() 的用法

lower_bound(key_value) ：返回第一个大于等于key_value的定位器
upper_bound(key_value)：返回第一个大于key_value的定位器
#include <iostream>
#include <set>
using namespace std;
int main(){
     set<int> s;
     s.insert(1);
     s.insert(3);
     s.insert(4);
     s.insert(6);
     cout<<*s.lower_bound(1)<<endl;
     cout<<*s.lower_bound(2)<<endl;
     cout<<*s.upper_bound(3)<<endl;
     return 0;
}
输出结果
1
3
4

• equal_range() 的用法

equal_range()：返回一对定位器，分别表示第一个大于等于给定关键值的元素和第一个大于给定关键值的元素，这个返回值是一个pair类型。如果这一对定位器中哪个返回失败，就会等于end()的值
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main(){
	set<int> s;
	set<int>::iterator it;
	for(int i=1; i<=5; ++i)
		s.insert(i); //向set中加入数据
	for(it=s.begin(); it!=s.end(); ++it)
		cout<<*it<<" ";  //输出set中的数据
	cout<<endl;
	pair<set<int>::const_iterator,set<int>::const_iterator> pr;
	pr=s.equal_range(3);
	cout<<"第一个大于等于3的数是："<<*pr.first<<endl;
	cout<<"第一个大于3的数是： "<<*pr.second<<endl;
	return 0;
}
输出结果：
1 2 3 4 5
第一个大于等于3的数是：3
第一个大于3的数是：4

• 补充
  set中元素唯一，处理不唯一情况用multiset
  只去重不排序用unordered_set

string用法

1.定义

使用string，需要添加#include<string>,// 注意这里不是string.h，string.h是C字符串头文件

1. string s; // 生成一个空字符串s
2. string s(str) ; // 拷贝构造函数生成str的复制品
3. string s(str, stridx); // 将字符串str内”始于位置stridx”的部分当作字符串的初值
4. string s(str, stridx, strlen) ; // 将字符串str内”始于stridx且长度顶多strlen”的部分作为字符串的初值
5. string s(cstr) ; // 将C字符串（以NULL结束）作为s的初值
6. string s(chars, chars_len) ; // 将C字符串前chars_len个字符作为字符串s的初值。
7. string s(num, ‘c’) ; // 生成一个字符串，包含num个c字符
8. string s(“value”); string s=“value”; // 将s初始化为一个字符串字面值副本
9. string s(begin, end); // 以区间begin/end(不包含end)内的字符作为字符串s的初值
10. s.~string(); //销毁所有字符，释放内存
11. string串要取得其中某一个字符，和传统的C字符串一样，可以用s[i]的方式取得。比较不一样的是如果s有三个字符，传统C的字符串的s[3]是’\0’字符，但是C++的string则是只到s[2]这个字符而已。C风格字符串
    用”“括起来的字符串常量，C++中的字符串常量由编译器在末尾添加一个空字符；末尾添加了‘\0’的字符数组，C风格字符串的末尾必须有一个’\0’。C字符数组及其与string串的区别
    char ch[ ]={‘C’, ‘+’, ‘+’}; //末尾无NULL
    char ch[ ]={‘C’, ‘+’, ‘+’, ‘\0’}; //末尾显式添加NULL
    char ch[ ]=”C++”; //末尾自动添加NULL字符 若[ ]内数字大于实际字符数，将实际字符存入数组，其余位置全部为’\0’。
12. 输入输出整个字符串只能用cin和cout,用printf输出需要用c_str()将string类型转为字符数组进行输出，如

string str="abcd"
printf("%s\n",str.c_str());//将string型str使用c_str()变为字符数组

操作	string	字符阵列
声明字符串	string s;	char s[100]
取得第i个字符串	s[i]	s[i]
字符串长度	s.length();s.size();	strlen(s)不计\0
读取一行	getline(cin,s);	get(s);
设成字符串	s=”TCGS”;	strcpy(s,”TCGS”);
字符串相加	s=s+”TCGS”,s+=”TCGS”	strcat(s,”TCGS”);
字符串比较	s==”TCGS”	strcmp(s,”TCGS”)

2.string对象的操作

string s;
1)  s.empty();  // s为空串 返回true
2)  s.size();  // 返回s中字符个数 类型应为：string::size_type
3)  s[n];  // 从0开始相当于下标访问
4)  s1+s2;  // 把s1和s2连接成新串 返回新串 
5)  s1=s2;  // 把s1替换为s2的副本
6)  v1==v2;  // 比较，相等返回true
7)  `!=, <, <=, >, >=`  惯有操作 任何一个大写字母都小于任意的小写字母,比较规则是字典序
string s1(“hello”);
string s3=s1+”world”;  //合法操作
string s4=”hello”+”world”;  //非法操作：两个字符串字面值相加

3.字符串操作函数

1. =, s.assign() // 赋以新值

s.assign(str,1,3); // 如果str是"iamangel" 就是把"ama"赋给字符串 
s.assign(str,2,string::npos); // 把字符串str从索引值2开始到结尾赋给s 
s.assign("nico",5); // 把’n’ ‘I’ ‘c’ ‘o’ ‘\0’赋给字符串 
s.assign(5,'x'); // 把五个x赋给字符串

2. swap() // 交换两个字符串的内容
3. +=, s.append(), s.push_back() // 在尾部添加字符
4. s.insert() // 插入字符

insert(pos,string) //在pos位置插入字符串string
str.insert(3,str2)//往str[3]处插入str2
insert(it,it2,it3)//串[it2,it3)将备插在it位置上

5. s.erase() // 删除字符

str.erase(it)//删除单个元素
str.erase(first,last)//删除[first,last)区间内所有元素
str.erase(str.begin()+2,str.end()-1)
str.erase(pos,length)//pos为需要开始删除的起始位置，length为删除的字符个数

6. s.clear() // 删除全部字符
7. s.replace() // 替换字符
8. • // 串联字符串
9. ==,!=,<,<=,>,>=,compare() // 比较字符串
10. size(),length() // 返回字符数量,两个等效
11. max_size() // 返回字符的可能最大个数
12. s.empty() // 判断字符串是否为空
13. s.capacity() // 返回重新分配之前的字符容量
14. reserve() // 保留一定量内存以容纳一定数量的字符
15. [ ], at() // 存取单一字符
16. >>,getline() // 从stream读取某值 ’
17. **<< // 将谋值写入stream ’**
18. copy() // 将某值赋值为一个C_string
19. c_str() // 返回一个指向正规C字符串(C_string)的指针 内容与本string串相同 有’\0’
20. data() // 将内容以字符数组形式返回 无’\0’
21. s.substr(pos,len) // 返回pos号开始，长度为len的子字符串

s.substr(); // 返回s的全部内容 
s.substr(11); // 从索引11往后的子串 
s.substr(5,6); // 从索引5开始6个字符

22. begin() end() // 提供类似STL的迭代器支持
23. rbegin() rend() // 逆向迭代器
24. get_allocator() // 返回配置器
25. string::npos//常数，本身值为-1，无符号整型，也可以是4294967285，作为find函数失配时的返回值。
26. find() //str.find(str2,pos)，从str的pos号位开始匹配str2,str2是str子串时返回第一次出现位置，不是子串返回string:npos，无pos从头开始。
27. replace() //str.replace(pos,len,str2)把str从pos号位开始，长度为len的子串替换为str2,str.replace(it1,it2,str2)把str的迭代器[it1，it2)范围的子串替换为str2
28. 字符串流stringstream操作
    Iostream标准库支持内存中的输入输出，只要将流与存储在程序内存中的string对象捆绑起来即可。此时，可使用iostream输入和输出操作符读写这个stream对象。

• string s

>>操作符 // 用于从istream对象中读入输入
is >> s;  // 从输入流is中读取一个以空白字符分割的字符串，写入s
<<操作符 // 用于把输出写到ostream对象中
os << s; // 将s写到输出流os中
getline(is, s);  // 从输入流is中读取一行字符，写入s，直到遇到分行符或到了文件尾
istream // 输入流 提供输入操作
ostream // 输出流 提供输出操作

• stringstream特定的操作

stringstream strm; // 创建自由的stringstream对象
stringstream strm(s); // 创建存储s的副本的stringstream对象，s是stringstream类型
strm.str(); // 返回strm中存储的string类型对象
strm.str(s); // 将string类型的s复制给strm 返回void

• string到int的转换
  stringstream通常是用来做数据转换的，在多次转换中使用同一个stringstream对象，每次转换前要使用clear()方法。

与其他类型间的转换一样大同小异
string result=”10000”;  
int n=0;
stream<<result;
stream>>n;  // n等于10000

29. C字符串、string串、stringstream之间的关系

• string转换成const char *

如果要将字面值string直接转换成const char *类型。string有2个函数可以运用：一个是.c_str()，一个是data成员函数。 c_str()函数返回一个指向正规C字符串的指针，内容与本string串相同。这是为了与C语言兼容，在C语言中没有string类型，故必须通过string类对象的成员函数c_str()把string 对象转换成C中的字符串样式。注意：一定要使用strcpy()函数等来操作方法c_str()返回的指针

string str = "Hello World";
const char *ch1 = str.c_str();
const char *ch2 = str.data();
此时，ch1与ch2的内容将都是”Hello World”。但是只能转换成const char*，如果去掉const编译不能通过。

• string转换成char *

C++提供的由C++字符串得到对应的C_string的方法是使用data()、c_str()和copy()，其中

1. data()以字符数组的形式返回字符串内容，但并不添加’\0’。
2. c_str()返回一个以’\0’结尾的字符数组，返回值是const char*。
3. copy()则把字符串的内容复制或写入既有的c_string或字符数组内。
   C++字符串并不以’\0’结尾。我的建议是在程序中能使用C++字符串就使用，除非万不得已不选用c_string。
   如果要转换成char*，可以用string的一个成员函数strcpy实现。

string str = "Hello World";
int len = str.length();
char *data = new char[len+1];  //这里+1还是不+1需要注意
strcpy(data, str.c_str());  // const char *data = new char[len+1];  strcpy(data, str);
此时，data中的内容为”Hello World”使用c_str()要么str赋给一个const指针，要么用strcpy()复制。

• char *转换成string

string类型能够自动将C风格的字符串转换成string对象：
string str;
const char *pc = “Hello World”;
str = pc;
printf(“%s\n”, str); //此处出现错误的输出
cout<<str<<endl;
不过这个是会出现问题的。有一种情况我要说明一下。当我们定义了一个string类型之后，用printf(“%s”,str);输出是会出问题的。这是因为“%s”要求后面的对象的首地址。但是string不是这样的一个类型。所以肯定出错。
用cout输出是没有问题的，若一定要printf输出。那么可以这样：
printf(“%s”,str.c_str());

• char[ ] 转换成string

这个与char*的情况相同，也可以直接赋值，但是也会出现上面的问题，需要同样的处理。

• 字符数组转化成string类型：

char ch [] = "ABCDEFG";
string str(ch); //也可string str = ch;
或者
char ch [] = "ABCDEFG";
string str;
str = ch; //在原有基础上添加可以用str += ch;

• string转换成char[ ]
  string对象转换成C风格的字符串：
  const char *str = s.c_str();
  这是因为为了防止字符数组被程序直接处理c_str()返回了一个指向常量数组的指针。 由于我们知道string的长度可以根据length()函数得到，又可以根据下标直接访问，所以用一个循环就可以赋值了，这样的转换不可以直接赋值。

string str = "Hello World";
int len=str.length();
char ch[255]={};
for( int i=0;i<str.length();i++)
ch[i] = str[i];
ch[len+1] = '\0';
printf("%s\n", ch);
cout<<ch<<endl;

• stringstream与string间的绑定

stringstream strm;
string s;
strm<<s;  // 将s写入到strm
strm>>s;  // 从strm读取串写入s
strm.str(); // 返回strm中存储的string类型对象
strm.str(s); // 将string类型的s复制给strm 返回void
char* cstr;  // 将C字符数组转换成流
string str(cstr);
stringstream ss(str);

map(映射)用法

1.定义

头文件，#include<map>
单独定义一个map<typename1,typename2> mp;
map和其他STL容器在定义上有点不一样，因为map需要确定映射前的类型(键key)和映射后的类型(值value),所以需要在<>内填写两个类型，其中第一个是键的类型，第二个是值的类型。如果是int型映射到int型，就相当于是普通的int型数组。

字符串到整数型的映射，必须使用string而不能用char数组。
map<string,int> mp;
这是因为char数组作为数组，是不能被作为键值的。如果想用字符串做映射，必须使用string。
map的键和值也可以是STL容器，如map<set<int>,string> mp;

2.map容器内元素的访问

• 通过下标访问
  和访问普通数组一样，例如对一个定义为map<char,int> mp的map来说，就可以直接使用mp[‘c’]的方式来访问它对应的整数。应注意，map中键的值是唯一的。
• 通过迭代器访问
  map迭代器的定义和其他STL容器的迭代器定义方式相同：
  ma<typename1,typename2>::itrator it;
  map迭代器使用方式和其他STL容器有所不同，因为map的每一对映射都有两个typename，这决定了必须能通过一个it来同时访问键和值。事实上，,map可以使用it->first来访问键，使用it->second来访问值。map会以键从小到大的顺序自动排序，这是由于map内部是红黑树实现的(set也是)，在建立的过程中会自动实现从小到大的排序功能。

3.map常用函数解析

1. find(key) // 返回键为key 的映射的迭代器，如map<char,int>::itrator it=mp.find(‘b’)
2. erase() // mp.erase(it) it为需要删除的元素的迭代器;mp.erase(key) key为需要删除元素的键;mp.erase(first,last) first为要删除区间的起始迭代器，last为需要删除区间的末尾迭代器的下一个地址。
3. size() //获取map中映射的对数
4. clear() //清空map中所有元素

queue(队列)用法

1.定义

添加头文件 #include<queue>
queue<typename>name;//typename可以是任意基本数据类型或容器

2.queue容器内元素的访问

由于队列(queue)本身就是一种先进先出的限制性数据结构，因此在STL中只能通过front()来访问队首元素，或是通过back()来访问队尾元素。

3.queue常用函数解析

1. push(x)//将x进行入队
2. pop(x)//令队首元素出队
3. empty()//检测queue是否为空
4. size()//返回queue内元素的个数

priority_queue(优先队列)用法