学习STL的一点笔记

一 . 容器

顺序容器

1) vector 头文件
   实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾    端增删元素具有较佳的性能。

2) deque   头文件
   也是个动态数组，随机存取任何元素都能在常数时间完成(但次于 vector)   。在两端增删元素具有较佳的性能。

3) list    头文件
双向链表，在任何位置增删元素都能在常数时间完成。不支持随机存取。
push_front: 在前面插入
pop_front:   删除前面的元素
sort: 排序 ( list 不支持 STL 的算法 sort)
remove: 删除和指定值相等的所有元素
unique: 删除所有和前一个元素相同的元素
merge:    合并两个链表，并清空被合并的那个
reverse:   颠倒链表

本类容器特有的函数：
begin 返回指向容器中第一个元素的迭代器
end     返回指向容器中最后一个元素后面的位置的迭代器
rbegin 返回指向容器中最后一个元素的迭代器
rend    返回指向容器中第一个元素前面的位置的迭代器
erase   从容器中删除一个或几个元素
clear   从容器中删除所有元素

front() :返回容器中第一个元素的引用
back() : 返回容器中最后一个元素的引用
push_back(): 在容器末尾增加新元素
pop_back(): 删除容器末尾的元素

关联容器

1) set/multiset:   头文件
   set 即集合。set中不允许相同元素，multiset中允许存在相同的元素。从 begin() 到 end()遍历一个 multiset对象，就是从小到大遍历各个元素。

2) map/multimap:   头文件

内部元素有序排列，新元素插入的位置取决于它的值，查找速度快
除了各容器都有的函数外，还支持以下成员函数：
find: 查找
lower_bound
upper_bound
count :计算等于某个值的元素个数
插入元素用 insert

容器适配器
1)stack :头文件
   栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入   序列的项。即按照后进先出的原则。
   stack 上可以进行以下操作：
push: 插入元素
pop: 弹出元素
top: 返回栈顶元素的引用

2) queue :头文件
   队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。按照先进先出的原则。
   同样也有push,pop,top函数， 但是push发生在队尾，pop,top发生在队头，先进先出

3）priority_queue :头文件
优先级队列。最高优先级元素总是第一个出列。
priority_queue 通常用堆排序技术实现，保证最大的元素总是在最前面。
即执行pop操作时，删除的是最大的元素,执行top操作时，返回的是最大元素的引用。默认的元素比较器是 less。

所有标准库容器共有的成员函数：
比较两个容器的运算符：    =, < , <= , > , >=, == , !=
empty : 判断容器中是否有元素
max_size: 容器中最多能装多少元素
size:   容器中元素个数
swap: 交换两个容器的内容

-------------------------------------------------------------------------------------------------------------
二 . 迭代器

容器    迭代器类别
vector    随机
deque    随机
list     双向
set/multiset   双向
map/multimap   双向

stack    不支持迭代器
queue    不支持迭代器
priority_queue   不支持迭代器

迭代器用于指向一类容器中的元素。有const 和非 const两种。
通过迭代器可以读取它指向的元素，通过非const迭代器还能修改其指向的元素。迭代器用法和指针类似。
定义一个容器类的迭代器的方法可以是：

容器类名::iterator   变量名;
或：
容器类名::const_iterator 变量名;

访问一个迭代器指向的元素：
* 迭代器变量名

-------------------------------------------------------------------------------------------------------------
三. 算法
1.容器操作
1).
fill ,fill_n: 将容器中某一区间的元素全部设为某值
比如：
vector v(100);
fill( v.begin(), v.end(), 5 ); //将全部元素设为5
vector vc(100);
fill_n(vc.begin(),5, ‘A’); //将 begin()及其后5个元素设为‘A’

2).
template
FwdIt remove(FwdIt first, FwdIt last, const T& val);
删除 [first,last)中所有和 val相等的元素，这里“删除”的意思
是用该区间后面的元素替换，后面的元素往前移动的意思，
因此该函数不会使容器里的元素真正减少。
返回值是迭代器，指向被修改后序列的终点，
即被修改后的序列是[first,fwdIt)
如果被删除的是[first,last)中的最后一个元素，那么就等于什么操作都没做，因为[first,last)里没有元素可以往前移,来替换被删除元素了，此时返回值指向 last的前一个元

素。如果[first,last)中没有元素等于val，那么 fdwIt 等于 last

3).
remove_copy
template
OutIt remove_copy(InIt first, InIt last, OutIt x, const T& val);
将 [first,last)中所有不等于 val 的元素，拷贝到另一容
器中从 x 开始的位置(会覆盖另一容器中原有的元素，
须确保另一容器足够长，否则会出错）
返回值是另一容器的迭代器，指向被拷贝序列的最后一个
元素的后面。如果操作在同一容器上进行，
则 [x, x + (last - first)) 不能和 [first, last) 有重叠，否则会出错。

2.数学算法
1)random_shuffle :
template
void random_shuffle(RanIt first, RanIt last);
template
void random_shuffle(RanIt first, RanIt last, Fun& f);
随机打乱[first,last) 中的元素，适用于能随机访问的容器

2） count:
template
size_t count(InIt first, InIt last, const T& val);
计算[first,last) 中等于val的元素个数

3) count_if
template
size_t count_if(InIt first, InIt last, Pred pr);
计算[first,last) 中符合pr(e) == true 的元素 e的个数

4）min_element:
template
FwdIt min_element(FwdIt first, FwdIt last);
返回[first,last) 中最小元素的迭代器,以 “< ”作比较器
template
FwdIt min_element(FwdIt first, FwdIt last, Pred pr);
返回[first,last) 中最小元素的迭代器, 以 pr 作比较器

5）max_element:
template
FwdIt max_element(FwdIt first, FwdIt last);
返回[first,last) 中最大(不小）元素的迭代器,以 “< ”作比较器
template
FwdIt max_element(FwdIt first, FwdIt last, Pred pr);
返回[first,last) 中最大(不小)元素的迭代器, 以 pr 作比较器

6）accumulate
template
T accumulate(InIt first, InIt last, T val);
对 [first,last)区间中的每个迭代器 I ,
执行 val = val + * I;
返回 val
template
T accumulate(InIt first, InIt last, T val, Pred pr);
对 [first,last)区间中的每个迭代器 I ,
执行 pr(val, *I), 返回 val

7）for_each
template
Fun for_each(InIt first, InIt last, Fun f);
对[first,last)中的每个元素 e ,执行 f(e) , 要求 f(e)不能改变e

3.排序和查找算法

1)find
template
                 InIt find(InIt first, InIt last, const T& val);
The template function determines the lowest value of N in the
range [0, last - first) for which the predicate *(first + N) == val
is true. It then returns first + N. If no such value exists, the
function returns last. It evaluates the predicate once, at most,
for each N.

2) find_if
template
              InIt find_if(InIt first, InIt last, Pred pr);
The template function determines the lowest value of N in
the range [0, last - first) for which the predicate
pred(*(first + N)) is true. It then returns first + N. If no
such value exists, the function returns last. It evaluates the
predicate once, at most, for each N.

3) binary_search 折半查找，要求容器已经有序
template
           bool binary_search(FwdIt first, FwdIt last, const T& val);
template
bool binary_search(FwdIt first, FwdIt last, const T& val, Pred pr);
The first template function determines whether a value of N
exists in the range [0, last - first) for which *(first + N) has equivalent ordering to val,
where the elements designated by iterators in the range [first, last)
form a sequence ordered by operator<. If so, the function returns true.
If no such value exists, it returns false.

4) lower_bound,uper_bound, equal_range

lower_bound：
   template
FwdIt lower_bound(FwdIt first, FwdIt last, const T& val);
template
FwdIt lower_bound(FwdIt first, FwdIt last, const T& val, Pred pr);
要求[first,last)是有序的，
查找[first,last)中的,最小的位置 FwdIt,使得[first,FwdIt) 中所有的元素都比 val 小

upper_bound:
template
    FwdIt upper_bound(FwdIt first, FwdIt last, const T& val);
template
FwdIt upper_bound(FwdIt first, FwdIt last, const T& val, Pred pr);
要求[first,last)是有序的，
查找[first,last)中的,最大的位置 FwdIt,使得[FwdIt,last) 中所有的元素都比 val 大

5)equal_range
template
pair equal_range(FwdIt first, FwdIt last, const T& val);
template
pair equal_range(FwdIt first, FwdIt last, const T& val, Pred pr);
要求[first,last)是有序的，
返回值是一个pair, 假设为 p, 则
[first,p.first) 中的元素都比 val 小
[p.second,last)中的所有元素都比 val 大

6)sort
template
                                         void sort(RanIt first, RanIt last);
template
                                       void sort(RanIt first, RanIt last, Pred pr);
The first template function reorders the sequence designated
by iterators in the range [first, last) to form a sequence ordered by operator<. Thus, the elements are sorted in ascending order.
The function evaluates the ordering predicate X < Y at most ceil((last - first) * log(last - first)) times.
The second template function behaves the same, except that it replaces operator<(X, Y) with pr(X, Y).
sort 实际上是快速排序，时间复杂度 O(n*log(n));
平均性能最优。但是最坏的情况下，性能可能非常差。

如果要保证“最坏情况下”的性能，那么可以使用
stable_sort,实际上是归并排序，特点是能保持相等元素之间
的先后次序.在有足够存储空间的情况下，复杂度为 n * log(n)，否则复杂度为 n * log(n) * log(n)

stable_sort 用法和 sort相同
排序算法要求随机存取迭代器的支持，所以list 不能使用排序算法，要使用list::sort 。此外还有其他排序算法：
partial_sort : 部分排序，直到 前 n 个元素就位即可
nth_element : 排序，直到第 n个元素就位，并保证比第n个元素小的元素都在第 n 个元素之前即可
partition: 改变元素次序，使符合某准则的元素放在前面.

请路过的各位朋友指教：）