STL的简单应用

迭代器

指向某个STL容器container中的元素的迭代器的类型一般为container::iterator

迭代器可以用来遍历容器

注意auto可以起到同样的效果

vector<int> data(10);

// 使用下标访问元素
for (int i = 0; i < data.size(); i++)
  cout << data[i] << endl;  

// 使用迭代器访问元素
for (vector<int>::iterator iter = data.begin(); iter != data.end(); iter++)
  cout << *iter << endl;  

for (auto iter = data.begin(); iter != data.end(); iter++)
  cout << *iter << endl; 

for (auto x : data)
  cout << x << endl; 

在 STL 的定义中，迭代器根据其支持的操作依次分为以下几类：

• InputIterator（输入迭代器）：只要求支持拷贝、自增和解引访问。
• OutputIterator（输出迭代器）：只要求支持拷贝、自增和解引赋值。
• ForwardIterator（向前迭代器）：同时满足 InputIterator 和 OutputIterator 的要求。
• BidirectionalIterator（双向迭代器）：在 ForwardIterator 的基础上支持自减（即反向访问）。
• RandomAccessIterator（随机访问迭代器）：在 BidirectionalIterator 的基础上支持加减运算和比较运算（即随机访问）。

“输入”指的是“可以从迭代器中获取输入”，而“输出”指的是“可以输出到迭代器”。
“输入”和“输出”的施动者是程序的其它部分，而不是迭代器自身。

相关函数

很多 STL 函数 都使用迭代器作为参数。

可以使用 next(it) 获取向前迭代器 it 的后继。

可以使用 prev(it) 获取双向迭代器 it 的前驱。

STL 容器 一般支持从一端或两端开始的访问，以及对 const 修饰符 的支持。例如容器的 begin() 函数可以获得指向容器第一个元素的迭代器， rbegin() 函数可以获得指向容器最后一个元素的反向迭代器， cbegin() 函数可以获得指向容器第一个元素的 const 迭代器， end() 函数可以获得指向容器尾端（“尾端”并不是最后一个元素，可以看作是最后一个元素的后继；“尾端”的前驱是容器里的最后一个元素，其本身不指向任何一个元素）的迭代器。

---

序列式容器

vector

vector的优点

• vector可以动态分配内存
  很多时候我们不能提前开好那么大的空间（eg：预处理 1~n 中所有数的约数）。尽管我们能知道数据总量在空间允许的级别，但是单份数据还可能非常大，这种时候我们就需要vector来把内存占用量控制在合适的范围内。vector还支持动态扩容，在内存非常紧张的时候这个特性就能派上用场了。
• vector 重写了比较运算符及赋值运算符
  vector重载了六个比较运算符，以字典序实现，这使得我们可以方便的判断两个容器是否相等（复杂度与容器大小成线性关系）。例如可以利用vector<char>实现字符串比较（当然，还是用std::string会更快更方便）。另外vector也重载了赋值运算符，使得数组拷贝更加方便。
• vector 便利的初始化
  由于vector重载了=运算符，所以我们可以方便的初始化。此外从C++11起vector还支持列表初始化（例如 vector data {1, 2, 3};）

// 1. 创建空vector; 常数复杂度
vector<int> v0;
// 1+. 这句代码可以使得向vector中插入前3个元素时，保证常数时间复杂度
v0.reserve(3);
// 2. 创建一个初始空间为3的vector，其元素的默认值是0; 线性复杂度
vector<int> v1(3);
// 3. 创建一个初始空间为3的vector，其元素的默认值是2; 线性复杂度
vector<int> v2(3, 2);
// 4. 创建一个初始空间为3的vector，其元素的默认值是1，
// 并且使用v2的空间配置器; 线性复杂度
vector<int> v3(3, 1, v2.get_allocator());
// 5. 创建一个v2的拷贝vector v4， 其内容元素和v2一样; 线性复杂度
vector<int> v4(v2);
// 6. 创建一个v4的拷贝vector v5，其内容是{v4[1], v4[2]}; 线性复杂度
vector<int> v5(v4.begin() + 1, v4.begin() + 3);
// 7. 移动v2到新创建的vector v6，不发生拷贝; 常数复杂度; 需要 C++11
vector<int> v6(std::move(v2));  // 或者 v6 = std::move(v2);

元素访问

1. at()
v.at(pos)返回容器中下标为pos的引用。如果数组越界抛出 std::out_of_range类型的异常。
2. operator[](重载了[]，使得vector可以和普通数组一样的形式访问元素)
   v[pos]返回容器中下标为pos的引用。不执行越界检查。注意如果下标所在的位置并没有被赋值，则不要这样使用
3. front()
v.front()返回首元素的引用。
4. back()
v.back()返回末尾元素的引用。
5. data()
v.data()返回指向数组第一个元素的指针。

vector的迭代器

1. begin()/cbegin()
   返回指向首元素的迭代器，其中begin = front 。

2. end()/cend()
   返回指向数组尾端占位符的迭代器，注意是没有元素的。

3. rbegin()/rcbegin()
   返回指向逆向数组的首元素的逆向迭代器，可以理解为正向容器的末元素。

4. rend()/rcend()
   返回指向逆向数组末元素后一位置的迭代器，对应容器首的前一个位置，没有元素。

以上列出的迭代器中，含有字符 c 的为只读迭代器，你不能通过只读迭代器去修改 vector 中的元素的值。如果一个 vector 本身就是只读的，那么它的一般迭代器和只读迭代器完全等价。只读迭代器自 C++11 开始支持。

vector常用函数

• 与长度相关
  • empty()返回一个bool值，即v.begin() == v.end()，true为空， false为非空。
  • size()返回容器长度（元素数量），即std::distance(v.begin(), v.end())。
  • resize()改变vector的长度，多退少补。补充元素可以由参数指定。
  • max_size()返回容器的最大可能长度。
• 与容量相关
  • reserve()使得 vector 预留一定的内存空间，避免不必要的内存拷贝。
  • capacity()返回容器的容量，即不发生拷贝的情况下容器的长度上限。
  • shrink_to_fit()使得vector的容量与长度一致，多退但不会少。
• 增删/修改元素
  • clear()清除所有元素
  • insert()支持在某个迭代器位置插入元素、可以插入多个。复杂度与pos距离末尾长度成线性而非常数的
  • erase()删除某个迭代器或者区间的元素，返回最后被删除的迭代器。复杂度与insert一致。
  • push_back()在末尾插入一个元素，均摊复杂度为常数，最坏为线性复杂度。
  • pop_back()删除末尾元素，常数复杂度。
  • swap()与另一个容器进行交换，此操作是常数复杂度而非线性的。

vector实现细节

vector 的底层其实仍然是定长数组，它能够实现动态扩容的原因是增加了避免数量溢出的操作。首先需要指明的是 vector 中元素的数量（长度）n与它已分配内存最多能包含元素的数量（容量）N是不一致的， vector 会分开存储这两个量。当向 vector 中添加元素时，如发现$n>N$，那么容器会分配一个尺寸为 2N的数组，然后将旧数据从原本的位置拷贝到新的数组中，再将原来的内存释放。尽管这个操作的渐进复杂度是$O(n)$ ，但是可以证明其均摊复杂度为$O(1)$。而在末尾删除元素和访问元素则都仍然是$O(1)$的开销。 因此，只要对 vector 的尺寸估计得当并善用resize()和 reserve()，就能使得 vector 的效率与定长数组不会有太大差距

array(C++11)

std::array是 STL 提供的内存连续的、固定长度的数组数据结构。其本质是对原生数组的直接封装。

array实际上是 STL 对数组的封装。它相比 vector 牺牲了动态扩容的特性，但是换来了与原生数组几乎一致的性能（在开满优化的前提下）。因此如果能使用 C++11 特性的情况下，能够使用原生数组的地方几乎都可以直接把定长数组都换成array，而动态分配的数组可以替换为 vector 。

// 1. 创建空array，长度为3; 常数复杂度
std::array<int, 3> v0;
// 2. 用指定常数创建array; 常数复杂度
std::array<int, 3> v1{1, 2, 3};

v0.fill(1);  // 填充数组

// 访问数组
for (int i = 0; i != arr.size(); ++i) cout << arr[i] << " ";

deque

std::deque 是 STL 提供的双端队列数据结构。能够提供线性复杂度的插入和删除，以及常数复杂度的随机访问。

元素访问/迭代器

与vector一致，详见上

deque常用函数

• clear() 清除所有元素
• insert() 支持在某个迭代器位置插入元素、可以插入多个。复杂度与pos与两端距离较小者成线性 。
• erase() 删除某个迭代器或者区间的元素，返回最后被删除的迭代器。复杂度与 insert() 一致。
• push_front() 在头部插入一个元素，常数复杂度。
  pop_front() 删除头部元素， 常数复杂度 。
• push_back() 在末尾插入一个元素，常数复杂度。
• pop_back() 删除末尾元素，常数复杂度。
• swap() 与另一个容器进行交换，此操作是常数复杂度而非线性的。

list

std::list是 STL 提供的双向链表数据结构。能够提供线性复杂度的随机访问，以及常数复杂度的插入和删除。

forward_list(C++11)

std::forward_list是 STL 提供的单向链表数据结构，相比于std::list减小了空间开销。

---

关联式容器

set

set是关联容器，含有键值类型对象的已排序集，搜索、移除和插入拥有对数复杂度。set内部通常采用红黑树实现。

和数学中的集合相似，set中不会出现值相同的元素。如果需要有相同元素的集合，需要使用multiset。multiset的使用方法与set的使用方法基本相同。

插入/删除

• insert(x)将元素x插入到set中(若不是multiset，则在没有等价元素时才插入)。
• erase(x)删除值为x的所有元素，返回删除元素的个数。
• erase(pos)删除迭代器为pos的元素，要求迭代器必须合法。
• erase(first,last)删除迭代器在$[first,last)$范围内的所有元素。
• clear()清空set。

insert 函数的返回值
insert 函数的返回值类型为pair<iterator, bool>，其中iterator是一个指向所插入元素（或者是指向等于所插入值的原本就在容器中的元素）的迭代器，而 bool 则代表元素是否插入成功，由于 set 中的元素具有唯一性质，所以如果在 set 中已有等值元素，则插入会失败，返回 false，否则插入成功，返回 true；map 中的 insert 也是如此。

迭代器

• begin()/cbegin()返回指向首元素的迭代器，其中 *begin = front 。
• end()/cend()返回指向数组尾端占位符的迭代器，注意是没有元素的。
• rbegin()/rcbegin()返回指向逆向数组的首元素的逆向迭代器，可以理解为正向容器的末元素。
• rend()/rcend()返回指向逆向数组末元素后一位置的迭代器，对应容器首的前一个位置，没有元素。

以上列出的迭代器中，含有字符 c 的为只读迭代器，你不能通过只读迭代器去修改 set 中的元素的值。如果一个 set 本身就是只读的，那么它的一般迭代器和只读迭代器完全等价。只读迭代器自 C++11 开始支持。

查询操作

• count(x)返回 set 内键为 x 的元素数量。
• find(x)在 set 内存在键为 x 的元素时会返回该元素的迭代器，否则返回 end() 。
• lower_bound(x)返回指向首个大于等于给定键的元素的迭代器。如果不存在这样的元素，返回end()。
• upper_bound(x)返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回end()。
• empty()返回容器是否为空。
• size()返回容器内元素个数。

lower_bound 和 upper_bound 的时间复杂度
set 自带的lower_bound和upper_bound的时间复杂度为$O(logn)$。
但使用algorithm库中的lower_bound和upper_bound函数对 set 中的元素进行查询，时间复杂度为$O(n)$。

map

map是有序键值对容器，它的元素的键是唯一的。搜索、移除和插入操作拥有对数复杂度。map通常实现为红黑树。

你可能需要存储一些键值对，例如存储学生姓名对应的分数Tom 0， Bob 100，Alan 100。但是由于数组下标只能为非负整数，所以无法用姓名作为下标来存储，这时即可使用 STL 中的map。

map 重载了operator[]，可以用任意定义了operator <的类型作为下标（在 map 中叫做 key，也就是索引）：

map<Key, T> yourMap;

其中Key是键的类型，T是值的类型，下面是使用map的实例：

map<string, int> mp;

map的插入/删除

• 可以直接通过下标访问来进行查询或插入操作。例如mp["Alan"]=100。
• 通过向map中插入一个类型为pair<Key, T>的值可以达到插入元素的目的，例如mp.insert(pair<string,int>("Alan",100));；
• erase(key) 函数会删除键为key的所有元素。返回值为删除元素的数量。
• erase(pos) 删除迭代器为pos的元素，要求迭代器必须合法。
• erase(first,last) 删除迭代器在$[first,last)$范围内的所有元素。
• clear() 函数会清空整个容器。

在利用下标访问 map 中的某个元素时，如果 map 中不存在相应键的元素，会自动在 map 中插入一个新元素，并将其值设置为默认值（对于整数，值为零；对于有默认构造函数的类型，会调用默认构造函数进行初始化）。当下标访问操作过于频繁时，容器中会出现大量无意义元素，影响 map 的效率。因此一般情况下推荐使用 find() 函数来寻找特定键的元素。

map的查询操作

• count(x) 返回容器内键为 x 的元素数量。复杂度为 （关于容器大小对数复杂度，加上匹配个数）。
• find(x) 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回 end() 。
• lower_bound(x) 返回指向首个大于等于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 end() 。
• upper_bound(x) 返回指向首个大于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 end() 。
• empty() 返回容器是否为空，若空则为真返回true，非空返回false。
• size() 返回容器内元素个数。

对关联式容器的遍历

对于任意关联式容器，使用迭代器遍历容器的时间复杂度均为$O(n)$。
需要注意的是，对map的迭代器解引用后，得到的是类型为pair<Key, T>的键值对。

set<int> s;
typedef set<int>::iterator si;
for (si it = s.begin(); it != s.end(); it++) cout << *it << endl;

for (auto it = s.begin(); it != s.end(); it++) cout << *it << endl;

for (auto x: s) cout << x << endl;

multimap

• multimap 容器的成员函数 insert() 可以插入一个或多个元素，而且插入总是成功。这个函数有很多的版本都可以插入单个元素，它们都会返回一个指向插入元素的迭代器:

  multimap<string, string〉 pets; // Element is pair{pet_type, pet_name}
  auto iter = pets.insert (std::pair<string, string>{string{"dog"}, string{"Fang"}});
  iter = pets.insert(iter, std::make_pair("dog", "Spot")); // Insert Spot before Fang
  pets.insert(std::make_pair("dog", "Rover"));// Inserts Rover after Fang
  pets.insert (std::make_pair ("cat", "Korky"));// Inserts Korky before all dogs
  pets.insert ({{ "rat", "Roland"}, {"pig", "Pinky" }, {"pig", "Perky"}});//Inserts list elements

• 如果使用multimap容器，几乎可以肯定它会包含键重复的元素；否则，就应该使用map。一般来说，我们想访问给定键对应的所有元素。成员函数equal_range()就可以做到这一点。它会返回一个封装了两个迭代器的pair对象，这两个迭代器所确定范围内的元素的键和参数值相等。例如：

  auto pr = people.equal_range("Ann");
  // pr->first==people.lower_bound()    pr->second==people.upper_bound() 
  if(pr.first != people.end())
  {
      for (auto iter = pr.first ; iter != pr.second; ++iter)
          std:cout << iter->first << " is " << iter->second << std::endl;
  }

multiset

可以看作是允许有重复元素的set

---

自定义比较方式

set在默认情况下的比较函数为<（如果是非内置类型需要重载<运算符）。然而在某些特殊情况下，我们希望能自定义set内部的比较方式。

这时候可以通过传入自定义比较器来解决问题。

具体来说，我们需要定义一个类，并在这个类中重载()运算符（注意不是重载>或者<）。

一般来说，在sort()中若要重载是重载<运算符，在定义数据类型如set,map,vector时重载()运算符

例如，我们想要维护一个存储整数，且较大值靠前的set，可以这样实现：

struct cmp {
  bool operator()(int a, int b) { return a > b; }
};
set<int, cmp> s;

对于其他关联式容器，可以用类似的方式实现自定义比较，这里不再赘述。

map默认是按照Key的值来从小到大排序的(即使重载好像也只能重载Key的比较方式)，例如：

#include <map>
#include <string>
#include <iostream>
using namespace std;
// 自己编写的Compare，实现按照字符串长度进行排序
struct CmpByKeyLength {  
  bool operator()(string k1, string k2) {  
    return k1.length() < k2.length();  
  }  
};  
int main(){
  map<string, int, CmpByKeyLength > mapStudent;  //这里注意要换成自己定义的compare
  mapStudent["LiMin"]=90;
  mapStudent["ZiLinMi"]=72;
  mapStudent["BoB"]=79;
  map<string, int>::iterator iter=mapStudent.begin();
  for(iter=mapStudent.begin();iter!=mapStudent.end();iter++){
      cout<<iter->first<<" "<<iter->second<<endl;
  }
  return 0;
}

map 中不会存在键相同的元素， multimap 中允许多个元素拥有同一键。 multimap 的使用方法与 map 的使用方法基本相同。正是因为 multimap 允许多个元素拥有同一键的特点， multimap 并没有提供给出键访问其对应值的方法。

---

无序关联式容器

自C11标准起，四种基于哈希实现的无序关联式容器正式纳入了C的标准模板库中，分别是unordered_set，unordered_multiset，unordered_map，unordered_multimap。

它们与相应的关联式容器在功能，函数等方面有诸多共同点，而最大的不同点则体现在普通的关联式容器一般采用红黑树实现，内部元素按特定顺序进行排序；而这几种无序关联式容器则采用哈希方式存储元素，内部元素不以任何特定顺序进行排序，所以访问无序关联式容器中的元素时，访问顺序也没有任何保证。

采用哈希存储的特点使得无序关联式容器 在平均情况下大多数操作（包括查找，插入，删除）都能在常数时间复杂度内完成，相较于关联式容器与容器大小成对数的时间复杂度更加优秀。

无序关联式容器与相应的关联式容器在用途和操作中有很多共同点，这里不再赘述

制造哈希冲突
在最坏情况下，对无序关联式容器进行一些操作的时间复杂度会与容器大小成线性关系。
在哈希函数确定的情况下，可以构造出数据使得容器内产生大量哈希冲突，导致复杂度达到上界。
在标准库实现里，每个元素的散列值是将值对一个质数取模得到的，更具体地说，是这个列表中的质数（g++ > 6及以前版本的编译器，这个质数一般是$126271$，g++ 7及之后版本的编译器，这个质数一般是$107897$）。
因此可以通过向容器中插入这些模数的倍数来达到制造大量哈希冲突的目的。

自定义哈希函数

使用自定义哈希函数可以有效避免构造数据产生的大量哈希冲突。

要想使用自定义哈希函数，需要定义一个结构体，并在结构体中重载()运算符，像这样：

struct my_hash {
  size_t operator()(int x) const { return x; }
};

当然，为了确保哈希函数不会被迅速破解（例如 Codeforces 中对使用无序关联式容器的提交进行 hack），可以试着在哈希函数中加入一些随机化函数（如时间）来增加破解的难度。

struct my_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }

  // 针对 std::pair<int, int> 作为主键类型的哈希函数
  size_t operator()(pair<uint64_t, uint64_t> x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x.first + FIXED_RANDOM) ^
           (splitmix64(x.second + FIXED_RANDOM) >> 1);
  }
};

写完自定义的哈希函数后，就可以通过unordered_map<int, int, my_hash> my_map;或者 unordered_map<pair<int, int>, int, my_hash> my_pair_map;的定义方式将自定义的哈希函数传入容器了。

---

容器适配器

stack

STL 栈 (std::stack) 是一种后进先出(Last In, First Out)的容器适配器，仅支持查询或删除最后一个加入的元素（栈顶元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

stack（栈）的定义

#include <stack>
using std::stack;

stack<TypeName> s;  // 使用默认底层容器 deque，数据类型为 TypeName
stack<TypeName, Container> s;  // 使用 Container 作为底层容器

stack<TypeName> s2(s1);  // 以 s1 为模板定义一个栈 s2

常用函数

以下均为常数复杂度

• top() 访问栈顶元素（如果栈为空，此处会出错）
• push(x) 向栈中插入元素 x
• pop() 删除栈顶元素
• size() 查询容器中的元素数量
• empty() 询问容器是否为空，空时返回true

queue

STL 队列 (std::queue) 是一种先进先出 (First In, First Out) 的容器适配器，仅支持查询或删除第一个加入的元素（队首元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

queue（队列）的定义

#include <queue>
using std::queue

queue<TypeName> q;  // 使用默认底层容器 deque，数据类型为 TypeName
queue<TypeName, Container> q;  // 使用 Container 作为底层容器

queue<TypeName> q2(q1);  // 以 q1 为模板定义一个队列 q2

常用函数

以下函数均为常数复杂度

• front() 访问队首元素（如果队列为空，此处会出错）
• push(x) 向队列中插入元素 x
• pop() 删除队首元素
• size() 查询容器中的元素数量
• empty() 询问容器是否为空，空时返回true

priority_queue

优先队列是一种特殊的队列，具有一定性质的元素，按照该性质的大小决定踢出队列的顺序。优先队列是由堆实现的，默认是大顶堆

priority_queue（优先队列）的定义

#include <queue>  // std::priority_queue
// 本文里的所有优先队列都会加上命名空间
// 如果不想加命名空间，需要使用：using std::priority_queue;
// 不推荐直接使用 using namespace std;
std::priority_queue<T, Container, Compare> q;
/*
 * T: 储存的元素类型
 * Container:
 * 储存的容器类型，且要求满足顺序容器的要求、具有随机访问迭代器的要求 且支持
 * front() / push_back() / pop_back() 三个函数， 标准容器中 std::vector /
 * std::deque 满足这些要求。 Compare: 默认为严格的弱序比较类型
 * priority_queue 是按照元素优先级大的在堆顶，根据 operator <
 * 的定义，默认是大根堆， 我们可以利用
 * greater<T>（若支持），或者自定义类的小于号重载实现排序。
 * 注意：只支持小于号重载而不支持其他比较符号的重载。
 */
// 构造方式 ：
std::priority_queue<int> q1;
std::priority_queue<int, vector<int>> q2;
// C++11 前，请使用 vector<int> >，空格不可省略
std::priority_queue<int, deque<int>, greater<int>> q3;
// 注意：不可跳过容器参数直接传入比较类

常用函数

• top() 访问顶部元素 常数复杂度
• empty() 检查底层的容器是否为空 常数复杂度
• size() 返回底层容器的元素数量 常数复杂度
• push() 插入元素，并对底层容器排序 最坏$O(n)$均摊$O(log(n))$
• pop() 删除顶部元素 最坏$O(log(n))$