【C++】STL 初步
大道至简，不要重复造轮子。
What’s STL?
STL 是 Standard Template Library 的简称，中文名标准模板库，惠普实验室开发的一系列软件的统称。它是由 Alexander Stepanov、Meng Lee 和 David R Musser 在惠普实验室工作时所开发出来的。从根本上说，STL 是一些“容器”的集合，这些“容器”有 list,vector,set,map 等，STL 也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL 的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL 现在是 C++ 的一部分，因此不用安装额外的库文件。
简而言之，一些我们常用的 Data Structure 在 STL 中都有，它的意义是让我们不用“重复造轮子”，就能实现效率很高的数据结构，所以非常方便，使用时只需在最前面写上头文件，例如 #include<algorithm>。
algorithm
The header <algorithm> defines a collection of functions especially designed to be used on ranges of elements.
A range is any sequence of objects that can be accessed through iterators or pointers, such as an array or an instance of some of the STL containers. Notice though, that algorithms operate through iterators directly on the values, not affecting in any way the structure of any possible container (it never affects the size or storage allocation of the container).
头文件：#include<algorithm>
常用函数：
sort(arr,arr+n[,cmp])：sorts an array in ascending order（默认按<排序）
or sort(v.begin(),v.end()[,cmp])（v 为 vector 容器）
How to sort in descending order? sort() takes a third parameter that is used to specify the order in which elements are to be sorted. We can pass “greater()” function to sort in descending order. This function does comparison in a way that puts greater element before.
e.g. sort(arr,arr+n,greater<int>());
How to sort in particular order? We can also write our own comparator function and pass it as a third parameter.
e.g.bool cmp(int a,int b){return a > b;} sort(arr,arr+n,cmp);
reverse(arr,arr+n)：Reverses the order of the elements in the range [first,last).
or reverse(v.bigen(),v.end())
max(a,b)：(std::)Returns the largest of a and b. If both are equivalent, a is returned.
min(a,b)：(std::)Returns the smallest of a and b. If both are equivalent, a is returned.
swap(a,b)：(std::)Exchanges the values of a and b.
fill(first,last,value)：(std::)Assigns val to all the elements in the range [first,last).
__gcd(m,n)：最大公因数
lower_bound(first,last,val)：前闭后开区间进行二分查找，返回大于或等于 val 的第一个元素位置。如果所有元素都小于 val，则返回 last 的位置
upper_bound(first,last,val)：前闭后开区间进行二分查找，返回大于 val 的第一个元素位置。如果所有元素都小于 val，则返回 last 的位置
vector
Vectors are same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container. Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators. In vectors, data is inserted at the end. Inserting at the end takes differential time, as sometimes there may be a need of extending the array. Removing the last element takes only constant time because no resizing happens. Inserting and erasing at the beginning or in the middle is linear in time.
头文件：#include<vector>
声明/定义：vector<T> v;
常用成员函数：
push_back(g)：push the elements into a vector from the back
pop_back()：pop or remove elements from a vector from the back
insert(iterator it,const T& x)：inserts new elements before the element at the specified position
erase(pos)：remove elements from a container from the specified position or range
clear()：remove all the elements of the vector container
begin()：Returns an iterator pointing to the first element in the vector
end()：Returns an iterator pointing to the theoretical element that follows the last element in the vectorrbegin()：Returns a reverse iterator pointing to the last element in the vector (reverse beginning). It moves from last to first elementrend()：Returns a reverse iterator pointing to the theoretical element preceding the first element in the vector (considered as reverse end)cbegin()：Returns a constant iterator pointing to the first element in the vector.cend()：Returns a constant iterator pointing to the theoretical element that follows the last element in the vector.crbegin()：Returns a constant reverse iterator pointing to the last element in the vector (reverse beginning). It moves from last to first elementcrend()：Returns a constant reverse iterator pointing to the theoretical element preceding the first element in the vector (considered as reverse end)
string
A way to represent sequence of characters as an object of class. This class is called std:: string. String class stores the characters as a sequence of bytes with a functionality of allowing access to single byte character.
std:: string vs Character Array
A character array is simply an array of characters can terminated by a null character. A string is a class which defines objects that be represented as stream of characters.
Size of the character array has to allocated statically, more memory cannot be allocated at run time if required. Unused allocated memory is wasted in case of character array. In case of strings, memory is allocated dynamically. More memory can be allocated at run time on demand. As no memory is preallocated, no memory is wasted.
There is a threat of array decay in case of character array. As strings are represented as objects, no array decay occurs.
Implementation of character array is faster than std:: string. Strings are slower when compared to implementation than character array.
Character array do not offer much inbuilt functions to manipulate strings. String class defines a number of functionalities which allow manifold operations on strings.
总结：char数组是静态的（这样可能会浪费内存），string是动态的（这样更耗时间）；string类提供多种多样的成员函数。
头文件：#include<string>
声明/定义：string str;
常用成员函数：
getline(cin,str)：store a stream of characters as entered by the user in the object memory
pushu_back(str)：input a character at the end of the string
pop_back()：(C++11)delete the last character from the string
begin()：Returns an iterator to the first element of the string（返回第一个迭代器）
end()： Returns an iterator to the theoretical element that follows last element of the string（返回最后一个迭代器后的假想迭代器）
rbegin()：Returns a reverse iterator pointing at the end of string.
rend()：Returns a reverse iterator pointing at beginning of string.（配合上一个使用实现字符串反转）
length()：Return length of string.（返回字符串长度）
clear()：Clear string.（清空字符串）
empty()：Test if string is empty.（若字符串为空返回true，否则返回false）
find(g)：Find content in string.（若找到返回相应第一个迭代器，否则返回string::nops）
rfind(g)：Find last occurrence of content in string.（若找到返回相应最后一个迭代器，否则返回string::nops）
substr(pos,len)：Generate substring.
常用操作符：
string::operator[]：Get character of string.（相当于char数组下标用法）
string::operator+=：Append to string.（在字符串后添加）
set
Sets are a type of associative containers in which each element has to be unique, because the value of the element identifies it. The value of the element cannot be modified once it is added to the set, though it is possible to remove and add the modified value of that element.
简而言之，回想数学上学的set（集合），集合中的每一个元素必须唯一。
一旦将元素添加到集合中，就无法修改该元素的值，但可以删除并添加该元素的修改值。
头文件：#include<set>
声明/定义：set<T> s;
常用成员函数：
insert(T x)：将x添加到集合中
erase(iterator position)： Removes the element at the position pointed by the iterator（删除迭代器对应元素）
erase(const g)： Removes the value ‘g’ from the set（删除元素g）
clear()：Removes all the elements from the set（清空集合，删除所有元素，常用于初始化）
find(const g)：Returns an iterator to the element ‘g’ in the set if found, else returns the iterator to end（若找到元素则返回对应迭代器，否则返回end()）
count(const g)：Returns 1 or 0 based on the element g is present in the set or not.（若 g 在集合中，返回1，否则返回0）
begin()：Returns an iterator to the first element in the set（返回第一个迭代器）
end()： Returns an iterator to the theoretical element that follows last element in the set（返回最后一个迭代器后的假想迭代器）
size()：Returns the number of elements in the set（返回元素个数）
empty()：Returns whether the set is empty （若集合为空返回true，否则返回false）
map
Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have same key values.
Map就是映射，一个键（key）对应一个值（value）。
这样查找的时候可以很方便地采用下标的形式，如 m['K'] 就可以在 O(log(n)) 的时间找到 key 为 k 对应的 value。
头文件：#include<map>
声明/定义：map<T1,T2> m;（其中第一个模板对应key的数据类型，第二个模板对应value的数据类型）
常用成员函数：
erase(iterator position)： Removes the element at the position pointed by the iterator（删除迭代器对应元素）
erase(const g)： Removes the value ‘g’ from the map（删除元素g）
clear()：Removes all the elements from the map（清空映射，删除所有元素，常用于初始化）
find(const g)：Returns an iterator to the element ‘g’ in the map if found, else returns the iterator to end（若找到元素则返回对应迭代器，否则返回end()）
size()：Returns the number of elements in the map（返回元素个数）
empty()：Returns whether the map is empty （若映射为空返回true，否则返回false）
常用操作符：
map::operator[]：常用于插入、查询，若查询一个不存在的key，会抛出异常。
stack
头文件：#include<stack>
声明/定义：stack<T> s;
常用成员函数：
empty()：Returns whether the stack is empty, O(1)（若栈为空返回true，否则返回false）size()：Returns the size of the stack, O(1)（返回元素个数）top()：Returns a reference to the top most element of the stack, O(1)（返回栈顶元素）push(g)：Adds the element ‘g’ at the top of the stack, O(1)（将g压栈）pop()：Deletes the top most element of the stack, O(1)（栈顶出栈）
queue
头文件：#include<queue>
声明/定义：queue<T> que;定义一个队列；priority_queue<T> pq;定义一个优先级队列
常用成员函数：
empty()： Returns whether the queue is empty（若队列为空返回true，否则返回false）
size()：Returns the size of the queue（返回元素个数）
top()：Returns a reference to the top most element of the priority_queue（返回优先队列队头元素）
front()：返回 queue 队头元素
push(g)：Adds the element ‘g’ at the end of the queue（将g放入队列）
pop()：Deletes the first element of the queue（将队头删除）
优先级队列默认先出最大的，那么怎么改变排序方式呢，我一般这样写：
priority_queue<T,vector<T>,greater<T> > pq;（此时需要<vector>头文件）
或者把第三个模板改成自己定义的结构体，重载运算符()，如：
struct cmp1
{
bool operator()(int a,int b)
{
return a > b;
}
};
priority_queue<int, vector<int>,c mp1> pq;
Others
Why we should avoid using std::endl
为什么我们要尽量避免使用std::endl
It is a common practice to use std::endl to print newlines while using cout. For small programs with very little I/O operations this practice is acceptable, but if the bulk of I/O operations increase, then the efficiency of the program is compromised.
每次使用相当于执行这样的操作：
cout << '\n' << std::flush;
Flushing of buffers is an Operating System task. Each time the buffer is flushed, a request has to be made to the OS and these requests are comparatively expensive. Furthermore, we don’t really need to flush the buffer every time we write something to the stream, since the buffers get flushed automatically when they get full. In the rare cases we do need to perform flushing, we can explicitly specify the operation using either cout.flush() or by inserting std::flush into the stream.
每次刷新会有很大的开销，而在极少数情况下我们需要执行刷新。
提高 cin / cout 效率
在 main() 函数一开始写上：
ios::sync_with_stdio(false);
cin.tie(0);
这样，cin、cout 和 scanf、printf 效率就能相差无几了。
不过，这样就不能混用 cin、cout 和 scanf、printf 了。
建议参见
本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/10/27/sth-about-stl/