c++ STL

1.【STL概论】

目标	提升复用性
尝试	函数(functions)，类别(classes)，到函数库(function libraries)，类别库(class libraries)、各种组件，从模块化设计，到面向对象(object oriented )
目标	建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹性、交互操作性(相互合作性,interoperability)
结果	STL诞生

1.1【STL基本概念】

容器(container)
算法(algorithm)
迭代器(iterator)

1.2【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.

STL六大组件的交互关系，容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数。

2. string

2.1【函数】

//定义
    string s0 ("abcdefghijklmn");
	string s1;
	string s2 (s0);
	string s3(s0,3);
	string s4 (s0,3, 4);
	string s5 ("let us learn string");
	string s6 ("let us learn string",6);
	string s7 (10, 'x');    
	string s8 (s0.begin(), s0.begin()+7);

总结：

• string(直接输入数组/已有数组名）
• string(数组，开始的下标，取几个）
• string(数组开始的位置，数组结束的位置）
• string(几个，字符）

//操作
    =,assign() //赋以新值
    swap() //交换两个字符串的内容
    +=,append(),push_back() //在尾部添加字符
	
//增删替换
    insert() //插入字符
    insert(要被插入的地方，插入的字符）
    erase() //删除字符
    clear() //删除全部字符
    replace() //替换字符

总结：

• replace(替换的下标，多少个字符被替换，替换的字符）
• replace(替换的字符的开始位置，替换字符的最后一个位置的后一个位置，替换字符）
• replace(替换字符的下标，多少个字符被替换，替换成多少遍个，替换字符）
• erase（要删除的位置）
• erase（要删除的第一个字符位置，要删除的最后一个字符的后一个位置）

//大小
    size(),length() //返回字符数量
    capacity() //返回重新分配之前的字符容量
    reserve() //保留一定量内存以容纳一定数量的字符
	
//其他操作
    copy() //将某值赋值为一个C_string
    c_str() //将内容以C_string返回
    data() //将内容以字符数组形式返回
    substr() //返回某个子字符串

2.2【函数总结】

string	构造	添加	删除	替换	查找(find,rfind)	比较
普遍	string s； string s("a b c"); string s(n,'c'); string s(s1);	+= append(n,'c'); push_back()	s.clear(); s.pop_back()		find("a b c"); find_first(last)_of("a b") find_first(last)_not_of("a b")	compare(s) compare("a b")
location		insert(index,'c'); insert(index,s2); insert(index,"abc");			find('c'(,index));
pos,n	string s(s1,pos,n);		erase(pos(,n));	replace(pos,n,(a,)"a b c");		compare(pos,n,s);
first,last	string s(s1,first,last);		erase(first,last);	replace(first,last,"a b c");
大小	size(); length(); capacity(); max_size(); empty();
遍历	for(0 - length()) s[i] for(0 - length()) s.at(i) string::iterator i for(begin()-end()) *i;

【注意】
注1)：last大多为该元素的前一个，而非本元素。即[first,last);
注2)：().end不是最后一个元素，而是\0
注3)：cout << s[1] << endl;没毛病；但是cout << s.begin() << endl;有错，要加*。
注4)：c中那样的(a[i]=‘1’；)赋值方法是错的。下标只能用来获取已经存在的元素。
注5)：注意begin()与front()异同

【其他函数】
resize()
reserve()
swap()
reverse (first,last);

2.3【getline()用法】

形式	头文件< istream >中输入流成员函数	头文件< string >中普通函数
语法结构	getline(str,size(,delim));	getline(cin,str,(,delim));
意义	从istream中读取字符保存在str对应的数组中 结束标志：字符个数到达size || 字符读取到delim	读取的istream是作为参数传进函数的。 读取的字符串保存在string类型的str中

2.4 【sprintf、strcpy及memcpy】

区别在于实现功能以及操作对象不同。

	操作对象	目的
strcpy	字符串	拷贝字符串
sprintf	任意基本类型的数据	基本数据类型向字符串的转换
memcpy	任意数据类型	内存拷贝

利弊_单论拷贝字符串：
strcpy 是最合适的选择：效率高且调用方便。
sprintf 要额外指定格式符并且进行格式转化，麻烦且效率不高。
memcpy 虽然高效，但是需要额外提供拷贝的内存长度这一参数，易错且使用不便；（可以用来实现对结构或者数组的拷贝，目的是高效或者使用方便）

2.5 【size、length、capacity】

size()=length()——string的有效字符个数
capactiy()——string的容量
如果 value值为空，则capactiy()==0;否则，capacity() 初始值为32，根据string 存储的量的变化而变化。初始值=32，步长=32；

3. vector

说明：
连续存放：为了支持快速的随机访问，vector容器的元素以连续方式存放，每一个元素都紧挨着前一个元素存储。
增长原理：重新分配空间、拷贝元素、撤销旧空间
改进：自增长：每当vector容器不得不分配新的存储空间时，会以加倍当前容量的分配策略实现重新分配。

3.1 【size，capacity，reserve】

size()——指当前拥有的元素个数；
capacity()——指当前(容器必须分配新存储空间之前)可以存储的元素个数。
reserve()成员可以用来控制容器的预留空间。

3.2【函数总结】

vector	构造	赋值	添加	删除	大小
普遍	vector a(n(,num)); voctora={1,2,3};		push_back();	a.clear();	size(); capacity(); max_size(); empty();
vectora(b);	assign(n,elem);		a.pop_back()
location			insert(position,(n,)elem);	erase(location);
first,last	vector a(b,b+n); 注意：这里和string不一样，不是a(b.begin(),b.end())	assign(b.first,b.last)	insert(position,b.first,b.last)	erase(first,last);
pos,n	为什么vector不用这招了呢？

【2021.10.16错误修正】 上面表格里的第二列，vector(b,b+n)的用法并不是那样。 b,b+5 是用于数组，因为b为数组名，即数组地址 b.begin()是用于map型数据，此时b.begin()是迭代器，也是可以用的。 所以该单元格可以是vector a(b,b+n);也可以是vector a(b.begin(),b.begin()+2);取决于b的类。

【其他函数】

sort（first,last);
reverse(first,last);
copy(a.first,a.last,b.first);
find(first,last,elem);
swap(b);

4. deque

4.1【deque和vector的差别】

vector	单项开口	连续的内存空间
deque	双向开头	动态的分段连续空间

4.2 【容器实现原理】

vector的假象成长	deque的成长：
(1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间	(1)配置一段连续定量的空间 (2)串接在deque的头端或者尾端

4.3【deque原理】

中央控制：缓冲区：deque采取一块所谓的map，其中每一个元素都是一个指针，指向一段连续性内存空间。
优点：避开了重新配置空间，复制，释放的轮回
缺点：迭代器架构复杂。

4.4 【使用场景】

首尾两端都能快速的安插、删除元素，因此需要在两端安插、删除元素时，最好采用deque。
存在元素时，deque的内部结构会多一个间接过程，操作元素的效率会比vector低一些。所以可以尽量使用vector。如：对deque进行的排序操作，为了最高效率，可将deque先完整的复制到一个vector中，对vector容器进行排序，再复制回deque.

4.5 【函数总结】

deque	构造	赋值	添加	删除	大小
普遍	deque c;		push_back(elem)	pop_back()	size(); max_size(); resize(n(,elem)); empty();
deque c(c2);		push_front(elem)	pop_front()
dequec(n,elem);	assign(n,elem);		clear();
location			insert(position,(n,)elem);(n个)	erase(location);
first,last	deque c(first,last);	assign(first,last);	insert(position,b.first,b.last);	erase(first,last);

【其他函数】
swap();
【注意】
deque不提供容量操作：capacity()和reverse()。
deque直接提供函数完成首尾元素的插入和删除。

5 map

• Map提供一对一的数据处理能力
• map以红黑树为底层实现机制，红黑树具有对数据自动排序的功能，会根据键值（key）自动排序。
• map不允许相同键值存在，不能通过迭代器修改键值，只能修改实质值。
• key和value可以具有不同的数据类型，可以分别用pair的两个公有函数first和second访问。

5.1 【函数总结】

map	pair创建	构造	赋值	添加	删除	大小
普遍	pair

【注意】
d[index]访问map中不存在的值，将会在map中插入访问的key值，并给value默认初始化值。
map的迭代器只有++，–功能，没有+1，-1的功能（即不能it+=1），这点和vector等容器不一样
insert的前三种方法：插入时如果key已经存在，将会插入失败。
insert的第四种方法：如果key存在，对应value将会被新插入的值覆盖。

所以牵涉到一个问题：即
判断是否插入成功

pair < map<int,int>::iterator,bool> j
j = d.insert(pair<int, int>(10, 10))

j.second 如果是1，则插入成功

5.2【遍历】

//方法一
for(iter=d.begin();iter!=d.end;iter++)
{
cout<<iter->first<<"="<<iter->second<<" ";
}

//方法二
for (auto it:mymap)  it就是一个pair
{
    cout << "key:" << it.first << "value:" << it.second << endl;
}

5.3【其他函数】

count(key) //确定key是否存在，存在返回1，不存在返回0
find(key) // 找到则返回该关键字的迭代器，否则返回指向end的迭代器

lower_bound() 返回键值>=给定元素的第一个位置
upper_bound() 返回键值>给定元素的第一个位置
equal_range() 返回特殊条目的迭代器对，即pair< lower_bound(),upper_bound() >

key_comp() 返回比较元素key的函数
swap()
value_comp() 返回比较元素value的函数

6 set

• set是STL中一种标准关联容器。
• 底层实现机制是平衡的搜索树——红黑树实现，插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝，所以效率比较高。
• 支持集合的交(set_intersection),差(set_difference) 并(set_union)，对称差(set_symmetric_difference) 等一些集合上的操作。
• set里面的元素是有序的且唯一的，如果需要集合中的元素允许重复那么可以使用multiset。

6.1 【总结】

set	构造	添加	删除	大小
普遍	setd; setd={1,2}; setd(d2);	d.insert(elem);	clear(); erase(key);	size(); empty(); max_size()
location			erase(position);
first,last	setd(first,last);	d.insert(first,last);	erase(first,last);

【注意】
不能直接修改容器内数据，所以只能删除某元素再插入要修改的数值。
迭代器：双向访问迭代器，不支持随机访问，支持星号解除引用，仅支持"++“，”–"这两个算术操作
在multiset中s.erase(x)会删除所有值为x的元素

6.2【其它函数】

（其实跟map差不多）
s.find() 查找一个元素，如果容器中不存在该元素，返回值等于s.end()
s.count()
s.lower_bound() 返回第一个大于或等于给定关键值的元素
s.upper_bound() 返回第一个大于给定关键值的元素
s.equal_range() 返回一对定位器，分别表示 第一个大于或等于给定关键值的元素 和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于s.end()

6.3【set的交，并，补】

（假如有两个集合a,b）

//并集
set_union(a.first, a.last, b.first, b.last, std::inserter(c,c.end()));
//交集
set_intersection(a.first, a.last, b.first, b.last, std::inserter(d,d.end()));
//差集
set_difference(a.first, a.last, b.first, b.last, std::inserter(e,e.end()));

【copy】
copy(a.first, a.last, b.first, b.last, std::inserter(s,s.end()));
意义：可以用于类型的转换

6.4 【应用举例】：数据去重（考点copy）

①构造set
如果是从外部读入的，先储存到数组a[]或者vector
用构造函数或者insert转移到set中
②set还原到vector
copy(s.begin(),s.end(),std::back_inserter(v));

【应用举例2】：【多串数据去重】（考点：copy+set的交并补）
①使用应用1的做法把数据初始化到集合a,b,c内
②按需对abc求交并补。

参考：

C++：什么是STL？
stl之string类用法详细总结
字符串的拷贝可以使用sprintf、strcpy 及 memcpy 函数，这些函数有什么区别
deque用法详解
https://blog.csdn.net/sinat_37158899/article/details/79328104
https://blog.csdn.net/w55100/article/details/99459029
https://blog.csdn.net/qq_40692109/article/details/104318986
https://blog.csdn.net/bat603/article/details/1456141