ACM算法

STL 容器

常用的数据结构:

3.2.什么是STL算法

STL算法是用来操作容器中数据的模板函数，STL提供了大约100个实现算法的模板函数。

例如，STL用sort()对一个vector中的数据进行排序，用find()搜索一个list中的对象。

正是由于采用模板函数设计（即泛型设计），STL算法具有很好的通用性，例如排序算法sort()不仅可以

对内置数据类型的数据（如int数据）排序，也可以对自定义的结构体数据排序，不仅可以递增排序，
也可以按照程序员指定的方式排序（如递减），从而简化代码，提高算法设计效率。

3.什么是STL迭代器

简单地说，STL迭代器用于访问容器中的数据对象。每个容器都有自己的迭代器，只有容器自己知道如何

访问自己的元素。迭代器像C/C++中的指针，算法通过迭代器来定位和操作容器中的元素。

常用的迭代器如下：

iterator:指向容器中存放元素的迭代器，用于正向遍历容器中的元素
const_iterator:指向容器中存放元素的常量迭代器，只能读取容器中的元素
reverse_iterator:指向容器中存放元素的反向迭代器，只能反向遍历容器中的元素
const_reverse_iterator:指向容器中存放元素的常量反向迭代器，只能读取容器中的元素

迭代器的常用运算如下：

++ ： 正向移动迭代器
-- : 反向移动迭代器
*： 返回迭代器所指的元素值

二、常用的STL容器

STL容器很多，每一个容器就是一个类模板，大致分为顺序容器、适配器容器和关联容器3种类型。

1.顺序容器

顺序容器按照线性次序的位置存储数据，即第1个元素，第2个元素，依次类推。

STL提供的顺序容器有vector、string、deque和list。

1）vector(向量容器)

    它是一个向量类模板。向量容器相当于数组，它存储具有相同数据类型的一组元素，
    
    如下图所示为vector容器v的一般存储方式，可以从末尾快速地插入与删除元素，
    快速地随机访问元素，但是在序列中间插入、删除元素较慢，因为需要移动插入或删除位置后面地所有元素。
    如果初始分配的空间不够，当超过空间大小时会重新分配更大的的空间（通常按两倍大小扩展），
    此时需要进行大量的元素复制，从而增加性能开销。

//定义vector容器的几种方式如下：
vector<int> v1;                     // 定义元素为int的向量v1
vector<int> v2(10);                 // 指定向量v2的初始大小为10个int元素
vector<double> v3(10, 1.23);        // 指定v3的10个初始元素的初值为1.23
vector<int> v4(a, a + 5);           // 用数组 a[0, 4] 共5个元素初始化v4

    vector提供了一系列成员函数，vector的主要成员函数如下：

empty()：判断当前向量是否为空
size()：返回当前向量容器中的实际元素个数
[]：返回指定下标的元素
reserve(n)：为当前向量容器预分配n个元素的存储空间
capacity()：返回当前向量容器在重新进行内存分配以前所能容纳的元素个数
resize(n)：调整当前向量容器的大小，使其可以容纳n个元素
push_back()：在当前向量容器尾部添加一个元素
insert(pos, elem)：在pos位置插入元素elem，即将元素elem插入到迭代器pos指定的元素之前
front()：获取当前容器的第一个元素
back()：获取当前容器的最后一个元素
erase()：删除当前向量容器中某个迭代器或者迭代器区间指定的元素
clear()：删除当前容器的所有元素
begin()：引用容器的第一个元素
end()：引用容器的最后一个元素后面的一个位置
rbegin()：引用容器的最后一个元素
rend()：引用容器的第一个元素前面的一个位置

2）string(字符串容器)

string是一个保存字符序列的容器，下图所示为string容器s的一般存储方式，
它的所有元素为字符类型，类似vector[HTMLREMOVED]，因此除了有字符串的一些常用操作外，
还包含了所有序列容器的操作。常用操作包括增加，删除，查找，修改，输入，输出等。
//创建string容器的几种方式如下：

string()：建立一个空串
string(const string& str)：用字符串str建立当前字符串
string(const string& str, size_type idx)：用字符串str起始于idx的字符建立当前字符串
string(const string& str, size_type idx, size_type num)：用字符串str起始于idx的num个字符建立当前字符串
string(const char* cstr)：用C-字符串cstr建立当前字符串
string(const char* cstr, size_type len)：用C-字符串cstr开头的len个字符建立当前字符串
string(size_type num, char c)：用num个字符c建立当前字符串

//示例：

char cstr[] = "China! Great Wall";      // C-字符串
string s1(cstr);                        // s1:China! Great Wall
string s2(s1);                          // s2:China! Great Wall
string s3(cstr, 7, 11);                 // s3:Great Wall
string s4(cstr, 6);                     // s4:China!
string s5(5, 'A');                      // s5:AAAAA

//常用函数：

empty()：判断当前字符串是否为空
size()：返回当前字符串的实际字符个数
length()：返回当前字符串的实际字符个数
[idx]：返回当前字符串位于idx位置的元素，idx从0开始
at(idx)：返回当前字符串位于idx位置的元素
append(cstr)：在当前字符串末尾添加一个字符串str
insert(size_type idx, string str)：在当前字符串的idx处插入一个字符串str
find(string s, size_type pos)：从前字符串的pos位置开始查找s的第一个位置，找到返回位置，未找到返回-1
replace(size_type idx, size_type len, string str)：将当前字符串中起始于idx的len个字符用str替换
substr(size_type idx)：返回当前字符串起始于idx的子串
substr(size_type idx, size_type len)：返回当前字符串起始于idx的长度为len的子串
erase()：删除字符串的所有字符
clear()：删除字符串的所有字符
erase(size_type idx)：删除字符串从idx开始的所有字符

3）deque(双端队列容器)

双端队列容器由若干个块构成，每个块中元素的地址是连续的，块之间的地址是不连续的。

可以从前面或后面快速的插入与删除元素，并可以快速的随机访问元素，但在中间位置插入和删除元素较慢。

定义deque的几种方式：

deuqe<int> dq1;                                 // 定义元素为int的双端队列dq1
deque<int> dq2(10);                             // 指定dq2的初始大小为10个int元素
deque<double> dq3(10, 1.23);                    // 指定dq3的10个初始元素的初值为1.23
deque<int> dq4(dq2.degin(), dq2.end());         // 用dq2 的所有元素初始化dq4

empty()：判断双端队列是否为空
size()：返回双端队列的元素个数
front()：取队头元素
back()：取队尾元素
push_front(elem)：在队头插入元素elem
push_back(elem)：在队尾插入元素elem
pop_front(elem)：删除队头一个元素
pop_back(elem)：删除队尾一个元素
erase()：从双端队列中删除一个或几个元素
clear()：删除双端队列的所有元素
begin()：引用容器的第一个元素
end()：引用容器的最后一个元素后面的一个位置
rbegin()：引用容器的最后一个元素
rend()：引用容器的第一个元素前面的一个位置

4）list（链表容器）

可从任何地方快速插入与删除。每个节点通过指针链接，不能随机访问元素，为了访问特定的元素，
必须从第一个元素位置（表头）开始，随指针从一个元素到下一个元素，直到找到。

//定义list的几种方式：

list<int> l1;                   // 定义元素为int的链表l1
list<int> l2(10);               // 指定链表l2的初始大小为10个int元素
list<double> l3(10, 1.23);      // 指定dq3的10个初始元素的初值为1.23
list<int> l4(a, a + 5);         // 用数组 a[0,·· 4] 共5个元素初始化l4

empty()：判断链表是否为空
size()：返回链表的元素个数
push_back()：在链表尾部插入元素
pop_back()：删除链表的最后一个元素
remove()：删除链表中所有指定值的元素
erase()：从链表中删除一个或几个元素
unique()：删除链表中相邻的重复元素
clear()：删除链表的所有元素
insert(pos, elem)：在pos位置插入元素elem
insert(pos, n, elem)：在pos位置插入n个元素elem
reverse()：反转链表
sort()：对链表中的元素排序
begin()：引用容器的第一个元素
end()：引用容器的最后一个元素后面的一个位置
rbegin()：引用容器的最后一个元素
rend()：引用容器的第一个元素前面的一个位置

2.关联容器

关联容器中的每个元素有一个key（关键字），通过key来存储和读取元素。这些关键字可能与元素在容器中的位置无关，所以关联容器不提供顺序容器中的front(), push_front(), back(), push_back()以及pop_back()操作。

1）set(集合容器)/multiset(多重集合容器)

set和multiset都是集合类模板，其元素称为关键字。set的关键字是唯一的，multiset的关键字可以不唯一，

而且默认情况下会对元素按关键字自动升序排列，所以查找速度较快。

empty()：判断容器是否为空
size()：返回容器中的实际元素个数
insert()：插入元素
erase()：从容器中删除一个或几个元素
clear()：删除所有元素
count(k)：返回容器中关键字k出现的次数
find(k)：如果存在k, 返回该元素的迭代器，否则返回end()值
upper_bound()：返回一个迭代器，指向关键字大于k的第一个元素
upper_bound()：返回一个迭代器，指向关键字不小于k的第一个元素
begin()：用于正向迭代，返回容器的第一个元素
end()：用于正向迭代，返回容器的最后一个元素后面的一个位置
rbegin()：用于反向迭代，返回容器的最后一个元素
rend()：用于反向迭代，返回容器的第一个元素前面的一个位置

2）映射(map)/多重映射(multimap)

set和multiset都是映射类模板，映射是实现关键字与值关系的存储结构，可以使用一个关键字key来访问相应的数据值value。set/multiset中的key和value都是key类型，而set/multiset中的key和value是一个pair类结构。

    pair类结构的声明如下：

struct pair {
    T first;
    T second;
}

pair有两个分量（二元组），first为第一个分量（在map对应key），second为第二个分量（在map对应value）。

empty()：判断容器是否为空
size()：返回容器中的实际元素个数
map[key]：返回关键字key的元素的引用，如果不存在，则以key为关键字插入一个元素（不适合multimap）
insert(elem)：插入一个元素elem并返回该元素的位置
clear()：删除所有元素
count()：容器中指定关键字的元素个数（map中只有1或0）
find()：在容器中查找元素
begin()：用于正向迭代，返回容器的第一个元素
end()：用于正向迭代，返回容器的最后一个元素后面的一个位置
rbegin()：用于反向迭代，返回容器的最后一个元素
rend()：用于反向迭代，返回容器的第一个元素前面的一个位置

3.适配器容器

适配器容器是指基于其他容器实现的容器。

1）stack(栈容器)

后进先出。默认底层容器是deque.
stack容器只有一个出口，即栈顶，可以在栈顶插入（进栈）和删除（出栈）元素，而不允许顺序遍历。

empty()：判断栈是否为空
size()：返回栈的实际元素个数
push(elem)：元素elem进栈
top()：返回栈顶
pop()：元素出栈

2）queue(队列容器)

先进先出，不允许顺序遍历

empty()：判断队列是否为空
size()：返回队列的实际元素个数
front()：返回队头元素
back()：返回队尾元素
push(elem)：元素elem进队
pop()：元素出队

3）priorityqueue(优先队列容器)

优先队列是一种受限访问操作的存储结构，元素可以以任意顺序进入优先队列。

empty()：判断优先队列是否为空
size()：返回优先队列的实际元素个数
push(elem)：元素elem进队
top()：获取队头元素
pop()：元素出队