Collection

Collection & Iterator

集合：Collection 定义为可以容纳若干个其他对象的一个对象。

迭代器：Iterator 定义为对集合（容器）内的元素进行遍历的类型，它能按某种顺序遍历容器内存储的数据，而不暴露底层的实现。

STL

Standard Template Library (STL) 是 C++ 提供的一类标准库的统称，包括一部分的输入输出库、常用的数据结构库、常用的简单算法库。

使用 STL 的好处

• 提升开发效率
  • STL 中的容器已经经过大量实践的磨练
• 提升可读性
  • 在自己的代码中省略数据结构的具体实现
• 提升稳定性（robustness 鲁棒性）
  • 新标准中可能使用新的实现，而开发过程中不需要关心这些
• 好用

STL 中的常用内容

• pair<Tp1, Tp2> 保存两种类型的对象
• 常用容器
  • vector<Tp> 变长数组
  • list<Tp>, forward_list<Tp> 双向链表、单向链表
  • queue<Tp>, deque<Tp> 队列、双端队列
  • set<Tp>, multiset<Tp>, map<Key, Val> 维护数字集合、键值对集合
• 常用算法
  • sort() 排序
  • reverse(), random_shuffle() 翻转数组、打乱数组

注意：

• 所有的容器、函数都声明在命名空间 std 下，使用 using namespace std; 来引入 std 空间。
• 容器的迭代器定义在各个容器下，例如 vector<int> 的迭代器类型为 vector<int>::iterator。

如何选择各个容器

• 首先考虑使用 vector，除非有不能使用的情况
• 如果数据中有很多小段元素，同时空间开销有影响，那么不要使用 list 和 forward_list。
• 如果需要在序列中间插入元素，考虑使用 list 和 forward_list。
• 如果需要在序列头尾插入元素，考虑使用 deque。

样例学习：Vector

vector 就是可以变化长度的数组，默认在尾部插入 / 删除元素，支持在任何一个位置插入 / 删除元素

通过特殊的内存管理策略，vector 插入的用时可以均摊到线性级别，代替基本的数组使用。

Vector 操作

定义一个 vector：

std::vector<Elem> c1, c2(n), c3(n, Elem(3)), c4(c2);

常用方法：

c1.size() // number of items
c1.empty() // whether the container is empty
c1.begin() // first position
c1.end() // the position after the last position
c1.front() // first item
c1.back() // last item

修改内容：

c1.push_back(v) // insert behind the last position
c1.pop_back() // delete the last item
c1.insert(pos, v) // insert before the pos-th position (indexed from 0)
c1.erase(pos) // delete the pos-th position (indexed from 0)
c1[pos] = v // modify the pos-th item
c1.clear() // clear all items
c1.swap(c2) // swap 2 vectors

更多内容：std::vector - cppreference.com

Iterator 操作

按顺序输出 vector 中元素：

for(std::vector<Elem>::iterator it = c2.begin(); it != c2.end(); it++)
    std::cout << *it << ' ';

修改开头元素的值：

std::vector<Elem>::iterator it = c2.begin();
*it = Elem(10);

样例学习：Map

map 像是拓展数组，在方括号中可以使用拓展的字面量（string等），允许我们化简一些操作；同时它的大小和插入键值对的个数正相关，对于离散的值域可以使用 map 来压缩存储空间。

一般的 map 使用红黑树实现，所以需要它的键类型有定义好的 < 运算符，同时能与 std::hash 兼容，以便在需要时可以与其他使用哈希的容器或算法一起使用。

Map 操作

定义一个 map：

std::map<std::string, double> price;

然后我们就可以用 string 作为“下标”，访问和修改对应的 float 值。

price["snapple"] = 0.75;
price["cookie"] = 1.5;
std::string item;
double total = 0;
while(std::cin >> item) total += price[item];

常用功能：

price.find("snapple") // return the iterator with key "snapple", or price.end() if the key doesn't occur 
price.count("snapple") // return the times the key "snapple" occurs

Iterator 操作

找到某个键的键值对，修改值：

std::map<std::string, double>::iterator it = price.find("snapple");// Attention! Maybe it's price.end()
if(it != price.end()) it->second = 1.125;

找到键的前驱和后继：

std::map<long long, int> tags{{10, 1}, {100, 2}, {1000, 3}, {10000, 4}, {10000000000, 10}};
std::map<long long, int>::iterator it = tags.find(2000);
std::cout << it->first << " " << it->second << std::endl; // it should be "10000 4"
it++;
std::cout << it->first << " " << it->second << std::endl; // it should be "10000000000 10"
it--; it--;
std::cout << it->first << " " << it->second << std::endl; // it should be "1000 3"

更多内容：std::map - cppreference.com

For-Each Loop

C++11 标准中引入了基于范围的 For 循环（Range-based For Loop），允许我们以更简单的方式遍历容器内元素。

以 vector 为例：

std::vector<int> val;
std::cin >> n;
val.resize(n);
for(auto& x: val) std::cin >> x;

这段代码输入一个 n 和 n 个整数，存储在 val 里。

以 map 为例：

std::map<std::string, double> price;
// Assume we've inserted a lot of name-price pairs
for(auto [key, value]: price){
    std::cout << key << ": " << value << std::endl;
}

这段代码遍历 price 中的键值对并输出。

更多内容：Range-based for loop (since C++11) - cppreference.com