数据结构与算法学习札记(I):STL简介
今天想放松放松,所以看一下STL,算法以及C++的东西吧,以下简要记录一下看的过程中遇到的有意思的点,以及一些好玩的东东。
STL
入门篇1
也许你已经使用C++作为主要编程语言来解决Topcoder中的问题了，这就意味着你已经在简单的使用STL了，因为数组和字符串都是以STL对象的方式传入到你的函数中的。也许你已经注意到了，有许多程序员他们写代码要比你快并且代码也比你的简洁。
也许你不是一个C++程序员，但是因为C++的强大功能以及它的库（或者因为你在Topcoder practice房间和比赛里面看到的简短的解决方案），你想成为一个这样的程序员。
不管你来自哪里，这篇文章将会帮助你掌握它。我们将会看到STL中一些强大的特性--一个强大的工具有的时候可以为你在算法比赛中节省很多时间。
最简单的方式去熟悉STL就是从它的容器入手了。
Containers
任何时候当你需要处理很多元素的时候你需要一些种类的容器。在C当中，这里只有一种这种类型的容器,那就是数组。现在的问题不是数组的功能有限（比如它不能够在运行时决定数组的大小，而是有许多问题需要一个具有更多功能的容器。
比方说， 我们需要一下的一种或几种操作：
- 在容器中添加一些字符串
- 从容器中移除一些字符串
- 查看指定字符串是否在容器中
- 返回容器中一些不同元素
- 遍历整个容器并获得一定顺序的被添加的字符串的列表
当然，你可以在一个顺序的数组里面实现以上的功能。但是这些普通实现会变得非常低效。你也可以创建树型或者散列表结构来更得到一个更快的解决方案， 但是请思考一点：这个容器的实现是否依赖于它将存储的元素呢？例如当你需要存储一个平面上的点的时候，你是否需要重新实现这个模块来使得它工作呢？
如果不想这样，我们可以为这样的容器创建一个接口，那样我们就可以在任何地方使用任何数据类型了。其实，那正是STL容器的概念。
Before we begin
当程序中使用STL的时候，需要包含相应的文件，对于大多数的容器，包含文件的名字与容器的名字相同，并且不需要后缀。如果你将要使用stack，只要在你的程序的开头加上下面的一句话就可以了：
#include <stack>
容器类型（算法，函数对象和所有的STL内容）并不是定义在全局的名字空间中的，而是在一个特定的名叫“std”的名字空间里的。将下面的话添加在include之后和你的代码之前：
using namespace std;
另外一个重要的事情你要记住的是容器的类型是模版参数。程序当中模版参数使用 '<' 和 '>'标注的。例如:
vector<int> N;
当使用嵌套的构造时，确保括号不要紧随着另外一个--中间最好留个空格。
vector< vector<int> > CorrectDefinition;
vector<vector<int>> WrongDefinition; // Wrong: compiler may be confused by 'operator >>'
Vector
NOTE:目前C++ 11版本两种写法都是支持的(笔者注）
最简单的STL容器是vector。vector实际上是一个有着扩展功能的数组。此外，vector是仅有的一个向后兼容C的容器--这意味着vector实际上就是数组，但是有了一些附加的特性。
vector<int> v(10);
for(int i = 0; i < 10; i++) {
v[i] = (i+1)*(i+1);
}
for(int i = 9; i > 0; i--) {
v[i] -= v[i-1];
}
事实上，当你输入
vector<int> v;
空的vector被创建了。注意像一下创建的情形：
vector<int> v[10];
这里我们定义了一个有着10个vector
最常使用的vector的特征是得到它的大小
int elements_count = v.size();
两个注意点：
- 第一，size()是无符号的，这个也许有的时候会产生一些问题。相应的，我通常定义一些宏，比如sz(C)，返回代表C的大小的带符号的数。
-
第二，将v.size()和0比较不是一个好的习惯，如果你想要知道这个容器是否为空。你最好使用empty()函数：
bool is_nonempty_notgood = (v.size() >= 0); // Try to avoid this bool is_nonempty_ok = !v.empty();这个是因为并不是所有的容器可以在$O(1)$的复杂度内得到它的大小，并且你应当绝对的避免计算一个双端链表所有的元素 个数而仅仅是为了知道它是不是为空。
另外一个经常使用的函数是push_back。push_back是在vector的尾部增加一个元素，使得它的大小增加1。考虑下面的例子：
vector<int> v;
for(int i = 1; i < 1000000; i *= 2) {
v.push_back(i);
}
int elements_count = v.size();
不要担心内存分配--vector不会为一个元素每次都分配。相反的，vector在使用push_buck增加元素的时候会比它需要的分配的多。唯一你要担心的是内存使用，但是在TopCoder中这个没什么关系（后面将更多的关注vector的内存策略）
当你需要重新规划vector的大小时，使用resize()函数：
vector<int> v(20);
for(int i = 0; i < 20; i++) {
v[i] = i+1;
}
v.resize(25);
for(int i = 20; i < 25; i++) {
v[i] = i*2;
}
resize()函数使得vector包含需要数量的元素，如果你需要比vector已经有的元素少，最后部分的元素将被删除，如果你需要vector大小增长，它将会增加它的大小并且用用0进行初始化。
注意如果你在resize()之后使用push_buck()，它将会在新增加的大小后继续增加元素，而不是填充。在上面的例子中，vector最后的大小是25。而当我们在第二个循环中使用push_buch，它的大小将变为30.
vector<int> v(20);
for(int i = 0; i < 20; i++) {
v[i] = i+1;
}
v.resize(25);
for(int i = 20; i < 25; i++) {
v.push_back(i*2); // Writes to elements with indices [25..30), not [20..25) !
}
清除一个vector使用clear()成员函数。这个函数将使得vector包含0个元素。它并不是使这些元素为0。注意--它是完全清除这个容器。
有许多方法初始化vector， 你也可以从另外一个vector创建一个vector
vector<int> v1;
//
vector<int> v2 = v1;
vector<int> v3(v1);
v2和v3的初始化是基本一样的。
如果你想要创建一个指定大小的vector，使用下面的构造函数
vector<int> Data(1000);
上面的例子中， Data在创建后将包含1000个0。记得用圆括号而不是方括号，如果你想使用指定的元素进行初始化，像如下方式构造：
vector<string> names(20, “Unknown”);
记住你可以创建任何类型的vector
多维数组也很重要，最简单的方法来创建一个二维数组是通过声明一个元素为vector的vector。
vector< vector<int> > Matrix;
下面很清楚的向你显示如何创建一个指定大小的二维数组：
int N, N;
//
vector< vector<int> > Matrix(N, vector<int>(M, -1));
这里我们创建了一个$N*M$的二维数组，并且初始化为-1.
最简单的向一个vector中添加数据是使用push_back(),但是如果我们不想在尾部添加呢？这里我们利用insert()函数来达到这个目的。并且这里也有erase()函数来清除元素。但是首先我们需要谈谈迭代器。
你需要记住一些非常重要的事情：当vector作为参数传递给一些函数的时候。一份拷贝也会被创建。创建一个这样的vector是非常耗时间和内存的，并且我们其实也不需要。事实上，发现一个需要vector的拷贝作为参数的情况是很少的，所以，你不应该写:
void some_function(vector<int> v) { // Never do it unless you’re sure what you do!
//
}
相反的，你应该写：
void some_function(const vector<int>& v) { // OK
//
}
如果你需要在函数中更改vector中的内容，忽略const修饰符就可以了。
int modify_vector(vector<int>& v) { // Correct
v[0]++;
}
Pairs
在我们谈论迭代器之前，让我们先谈谈pairs，Pairs在STL中被广泛使用着，像TopCoder SRM 250中的500分的简单问题，通常需要一些有着一对元素的简单数据结构，而STL中的std::pair正好是一对元素。最简单的形式如下：
template<typename T1, typename T2> struct pair {
T1 first;
T2 second;
};
简单的有pair
pair<string, pair<int,int> > P;
string s = P.first; // extract string
int x = P.second.first; // extract first int
int y = P.second.second; // extract second int
pairs的最大好处在于他们内建了比较操作，pairs比较是从第一个比较到第二个。如果第一个元素不相等，那么结果仅仅基于第一个元素的比较；第二个元素比较被用到仅当第一个元素相等的情况。 数组（或者vector）能够轻易的被STL中内部函数排序。
例如，如果你想对一个有着整数点的数组排序而使得它能够构成一个多边形，把他们放到vector< pair
此外，pairs也被广泛的用在联合容器中，我们稍后将会在这里谈到它。
Iterators
什么是迭代器呢？在STL中，迭代器是最常使用的访问容器中数据的方法。考虑这样一个简单的问题：将一个有着N个int类型元素的数组倒序。让我们先看C写的一个解决方法：
void reverse_array_simple(int *A, int N) {
Int first = 0, last = N-1; // First and last indices of elements to be swapped
While(first < last) { // Loop while there is something to swap
swap(A[first], A[last]); // swap(a,b) is the standard STL function
first++; // Move first index forward
last--; // Move last index back
}
}
这段代码已经很清晰了。上面代码可以很容器的改成指针的形式:
void reverse_array(int *A, int N) {
int *first = A, *last = A+N-1;
while(first < last) {
Swap(*first, *last);
first++;
last--;
}
}
看这段代码的主循环部分，它在first和last指针上进行了4种不同的操作:
- 比较指针(first < last)
- 通过指针获取值 (first, last)
- 增加指针的值
- 减少指针的值
现在考虑处理第二个问题：将整个或者部分的双端链表进行倒序。第一段使用索引的代码将不在有效。至少，它在时间方面是没有优势的，因为在双端链表中不可能在O(1)的复杂度内通过索引获取到一个元素，只有在$O(N)$才行，所以整个算法将在$O(N^2)$内完成。厄。。。
但是注意： 第二段代码可以在任何指针类型的对象中起作用。仅有的约束是对象只能够进行上述的操作：取值(unary *)，比较(<),和自增自减(++/--).与容器相关并且具有上述属性的对象被喻为迭代器。任何STL容器也许都可以通过迭代器的形式进行遍历。尽管对于vector来说不需要，但是对于其他类型的容器很重要。
那么，我们拥有了一个什么了呢？一个语法和指针非常像的对象。下面的操作被定义为迭代器的操作：
- 获取迭代器代表的值，int x = *it;
- 增加和减少迭代器自身的值 it1++, it2--;
- 迭代器间的比较, 通过 != 和 <
- 迭代器后加上一个直接数 it += 20;等同于前移20个元素
- 获取迭代器之间的距离, int n = it2 - it1;
但是与指针不同的是，迭代器提供了更多的功能。它不仅可以作用在任何容器上，还可以进行比如，下标检查和描述容器用途等等。
当然，迭代器最大的好处在于它很大程度上重用了代码，你自己的基于迭代器的算法，将会作用在很大范围的容器上(包括你自己的提供迭代器的容器)上，并且可以作为参数传递给很多标准函数。
并不是所有类型的迭代器提供所有潜在的功能。事实上，迭代器中有“简单迭代器”和“随机访问迭代器”。简单迭代器可以使用'=='和'!='，并且他们能够自增和自减，但是他们不可以在减去或者加上一个值。一般来说，不可能为所有的容器在O(1)复杂度内完成上面描述的操作。倒置数组的函数应该像下面这样:
template<typename T> void reverse_array(T *first, T *last) {
if(first != last) {
while(true) {
swap(*first, *last);
first++;
if(first == last) {
break;
}
last--;
if(first == last) {
break;
}
}
}
}
这段代码和上面的不同之处在于我们没有在迭代器上使用'<'比较，而仅仅是使用'=='。另外，你不要对函数原型感到惊慌： 模版是声明函数的一个方法，它将使所有可以的参数类型得以工作。这个函数可以在参数是指向对象的指针或者所有简单迭代器时很好的工作。
让我们回到STL。STL算法总是使用两种迭代器，叫做"begin"和"end".这个end迭代器并不是指向最后一个元素，而是指向第一个非法的元素，也就是最后一个元素后面的一个。通常使用它是非常方便的。
每一个STL容器都有begin()和end()成员函数返回那个容器的begin和end迭代器。
基于这些原理，我们可以得到，c.begin()==c.end()只有当c是空的情况下，并且c.end()-c.begin()总是等于c.size().(这个式子当迭代器可以进行减法操作时才是合法的。也就是说，begin()和end()返回了随机访问迭代器，而这并不是对所有的容器都适合。前面双端链表就是一个例子)
服从STL规则的倒置函数应该像下面这么写:
template<typename T> void reverse_array_stl_compliant(T *begin, T *end) {
// We should at first decrement 'end'
// But only for non-empty range
if(begin != end)
{
end--;
if(begin != end) {
while(true) {
swap(*begin, *end);
begin++;
If(begin == end) {
break;
}
end--;
if(begin == end) {
break;
}
}
}
}
}
注意,这个函数和标准函数std::reverse(T begin, T end)所做的事情是一样的，后者可以在算法模块中找到(#include
此外， 任何一个有足够功能的对象可以被当作一个迭代器传递给STL算法和函数。这就是模版的力量之所在！看下面的例子：
vector<int> v;
//
vector<int> v2(v);
vector<int> v3(v.begin(), v.end()); // v3 equals to v2
int data[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
vector<int> primes(data, data+(sizeof(data) / sizeof(data[0])));
最后一句话展示了从一个C的数组构造vector的例子。没有加索引的data被当成指向数组开始的指针，'data+N'指向第N个元素。当N是这个数组的长度时，'data+N'指向第一个不在数组的元素，所以‘data+data的长度'可以被当成数组'data'的end迭代器。表达式 'sizeof(data)/sizeof(data[0])'返回data数组的大小，但是这样的语句只能用在一小部分情况下，所以不要在任何地方使用它除了像以上的情况。(C程序员会同意我的说法的！)
更进一步的，我们可以甚至使用下面的构造:
vector<int> v;
//
vector<int> v2(v.begin(), v.begin() + (v.size()/2));
这样就创建的v2向量等同于v向量的前半部分。
下面是使用reverse函数的一个例子
int data[10] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
reverse(data+2, data+6); // the range { 5, 7, 9, 11 } is now { 11, 9, 7, 5 };
每一个容器还拥有rbegin()和rend()函数，他们返回的是倒置过的迭代器。倒置的迭代器被用在倒序容器上的，比如：
vector
这样创建的v2向量将等于v的前半部分，顺序是从后向前。
要创建一个迭代器对象，我们通常要指定它的类型。迭代器的类型通常可以由该类型的容器加上"::iterator","::const_iterator","::reverse_iterator" 或者"const_reverse_iterator"来构造。因此vector可以使用下面的方式进行遍历：
vector<int> v;
//
// Traverse all container, from begin() to end()
for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
*it++; // Increment the value iterator is pointing to
}
建议你使用 '!=' 而不是 '<' 并且'empty()'而不是'size()!=0'--因为对于一些类型的容器而言，去判断一个迭代器是否在另外一个之前是非常低效的。
现在你知道STL的算法函数reverse()了。其实许多STL算法是以这么一种方式声明的：他们通常使用一对迭代器，开始和结束迭代器，并且返回一个迭代器。
find()算法在一个区间内查找指定的元素，如果这个元素被找到了，那么指向这个元素第一次出现位置的迭代器将会被返回。反之，则返回这个区间的end迭代器。看下面的代码：
vector<int> v;
for(int i = 1; i < 100; i++) {
v.push_back(i*i);
}
if(find(v.begin(), v.end(), 49) != v.end()) {
//
}
想要得到被找到的元素的下标，需要用find()的结果减去开始迭代器：
int i = (find(v.begin(), v.end(), 49) - v.begin();
if(i < v.size()) {
//
}
记得在使用STL算法的时候，在源代码中加上#include
min_element和max_element返回一个指向单个元素的迭代器。要获得最小或者最大的元素，和find()一样，使用min_element(...)或者 max_element(...)。要获得下标的话，减去容器或者一定范围的开始迭代器就可以了：
int data[5] = { 1, 5, 2, 4, 3 };
vector<int> X(data, data+5);
int v1 = *max_element(X.begin(), X.end()); // Returns value of max element in vector
int i1 = max_element(X.begin(), X.end()) – X.begin; // Returns index of max element in vector
int v2 = *min_element(data, data+5); // Returns value of min element in array
int i3 = min_element(data, data+5) – data; // Returns index of min element in array
现在你可以看到有用的宏了:
#define all(c) c.begin(), c.end()
不要把右边的部分放到圆括号里面--那样是错的！
另外一个好用的算法是sort(), 它使用起来非常简单。 看下面的一个例子：
vector<int> X;
//
sort(X.begin(), X.end()); // Sort array in ascending order
sort(all(X)); // Sort array in ascending order, use our #define
sort(X.rbegin(), X.rend()); // Sort array in descending order using with reverse iterators
Compiling STL Programs
一个需要值得指出的事情就是STL的错误消息。由于STL已经被广泛的使用在源代码中了，所以有必要要求编译器去创建高效的可执行文件，STL的一个习惯在于它的难读的错误消息.
例如,如果你传递一个vector
void f(const vector<int>& v) {
for(
vector<int>::iterator it = v.begin(); // hm where’s the error?..
//
//
}
这里的错误是你正在从一个常量对象中创建一个非指向常量的迭代器(实际上找出错误比修改它要难).正确的代码如下：
void f(const vector<int>& v) {
int r = 0;
// Traverse the vector using const_iterator
for(vector<int>::const_iterator it = v.begin(); it != v.end(); it++) {
r += (*it)*(*it);
}
return r;
}
尽管如此,让我告诉你在GNU C++中成为"typeof"的一个重要特性。这个操作符会在编译时被替换为表达式的类型。考虑下面的例子：
typeof(a+b) x = (a+b);
这样将会创建一个和(a+b)表达式相同的类型变量x。请注意typeof(v.size())对于STL中的任何容器类型来说都是无符号的。但是在TopCoder中typeof最重要的应用在于遍历一个容器。考虑下面一些宏：
#define tr(container, iterator) \
for(typeof(container.begin()) iterator = container.begin(); iterator != container.end(); iterator++)
通过使用这些宏，我们可以遍历任何类型的容器，不仅仅是vector。这样将会为常量对象产生指向常量的迭代器并且为非常量对象产生普通迭代器，当然你也不会获得一个错误。
void f(const vector<int>& v) {
int r = 0;
tr(v, it) {
r += (*it)*(*it);
}
return r;
}
注意： 为了提高可读性，我没有在#define行上添加额外的圆括号。这篇文章的下面将会给出更加精确的#define语句，并且你可以直接将其拷贝到你的模版代码中。
遍历宏对与vector来说并不是必需的，但是对于一些复杂的数据类型，由于它们没有索引访问而迭代器是唯一访问数据的方法，这是遍历宏将显得非常方便。我们将在这篇文章的后面继续讨论它。
Data manipulation in vector
我们可以使用insert()函数向vector中插入一个元素。
vector<int> v;
//
v.insert(1, 42); // Insert value 42 after the first
所有从第二个元素（下标为1）到最后一个都会向右移动一个单位来腾出空位给新插入的元素。如果你打算加入很多元素的话，做许多这样的移动是不太好的，你最好只调用insert()一次。所以，insert()有插入一段区间的形式：
vector<int> v;
vector<int> v2;
// ..
// Shift all elements from second to last to the appropriate number of elements.
// Then copy the contents of v2 into v.
v.insert(1, all(v2));
vector也有一个叫做erase的函数，同样的，它也有两种形式，猜猜他们是什么样的：
erase(iterator);
erase(begin iterator, end iterator);
第一个例子中，vector中的单个元素将会被删除，在第二个例子中，由两个迭代器指定的区间将会从vector中删除。
插入，删除的技巧很普遍，但对于STL的容器来说并不都是一样的。
String
这里有一个操纵字符串的特殊容器。这个字符串容器与vector
string有一个不用迭代器而使用下标的取子串函数(substr()函数第一个参数表示起始位置,第二个参数表示截取的字符数):
string s = "hello";
string
s1 = s.substr(0, 3), // "hel"
s2 = s.substr(1, 3), // "ell"
s3 = s.substr(0, s.length()-1), "hell"
s4 = s.substr(1); // "ello"
注意当(s.length()-1)作用在空串上的情况，因为s.length()返回的是无符号的数，那么unsigned(0)-1得到的并不是你期望的！
Set
通常很难决定是先讲set容器还是map容器。我的意见是如果读者有一个基本的算法概念，那么从'set'讲起会容易理解一点。
考虑我们需要一个有着下面特征的容器：
- 增加一个元素，但是不允许它重复出现
- 删除元素
- 获取不同元素的数量
- 判断元素是否已经在集合当中
这是一个经常被使用到的任务。STL为其提供了一个特殊的容器--set。set能够添加，移除和在$O(logN)$内检查是否有指定元素存在，这里的N是指在set中存在的对象数量。当像set中集合中添加元素时，重复的将会被丢弃。set中元素的数量N，可以在$O(1)$的时间复杂度内得到。我们将稍后谈到set和map的算法实现。现在，让我们先研究一下set的接口:
set<int> S;
for(int i = 1; i <= 100; i++) {
S.insert(i); // Insert 100 elements, [1..100]
}
S.insert(42); // does nothing, 42 already exists in set
for(int i = 2; i <= 100; i += 2) {
S.remove(i); // Remove even values
}
int N = int(S.size()); // N will be 50
push_back()成员函数对set是不适用的。因为set中的元素没有什么顺序关系，因此push_back()在这里就不适用了。
由于set并不是线性容器，所以使用索引去访问元素是不可能的。因此唯一访问set元素的方法是使用迭代器。
// Calculate the sum of elements in set
set<int> S;
//
int r = 0;
for(set<int>::const_iterator it = S.begin(); it != S.end(); it++) {
r += *it;
}
这里使用遍历宏会变得非常优雅，为什么呢？试想这里有一个集合set
set< pair<string, pair< int, vector<int> > > SS;
int total = 0;
tr(SS, it) {
total += it->second.first;
}
注意 'it->second.first'的语法。因为'it'是一个迭代器了，我们需要'it'中取出一个对象进行操作。所以正确的语法是'(it).second.first'.尽管如此，写'something->'要比'(something)'来的容易一点。要完整的解释的话估计要写好长--只要记住，对于迭代器而言，两种语法都是允许的。
要判断set中是否已经存在一些元素，使用'find()'成员函数。不要感到迷惑，虽然：在STL中有许多'find()'.有一个全局的算法'find()' 参数包括两个迭代器，元素并且在O(N)内完成。在set中使用它来查找元素是可能的，但是为什么有已经存在的O(logN)的算法还要要使用O(N)的算法呢？当在set和map（multiset/multimap，hash_map/hash_set,等等)进行搜索时，不要使用全局的find--相反的使用成员函数'set::find()'。作为顺序的查找，set::find将会返回一个迭代器，要么指向找到的元素，要么指向'end()'。所以检查元素是否存在应该像下面这样：
set<int> s;
//
if(s.find(42) != s.end()) {
// 42 presents in set
}
else {
// 42 not presents in set
}
另外一个在O(logN)下工作的算法是计算函数。有些人认为
set<int> s;
//
if(s.find(42) != s.end()) {
// 42 presents in set
}
else {
// 42 not presents in set
}
甚至
if(s.count(42)) {
// …
}
非常容易写。但是就个人而言，在set或者map中使用count()是没有意义的：元素要么存在要么不存在。 对我来说，我更加喜欢使用下面两个宏：
#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element) (find(all(container),element) != container.end())
(记住 all(c) 代表 "c.begin(),c.end")
这里，'present()'使用成员函数'find()'返回这个元素是否存在与容器中，而'cpresent'是用于vector的。
想要从set中移除一个元素使用erase()函数。
set<int> s;
// …
s.insert(54);
s.erase(29);
erase也有区间的形式:
set<int> s;
// ..
set<int>::iterator it1, it2;
it1 = s.find(10);
it2 = s.find(100);
// Will work if it1 and it2 are valid iterators, i.e. values 10 and 100 present in set.
s.erase(it1, it2); // Note that 10 will be deleted, but 100 will remain in the container
set有一个区间的构造函数：
int data[5] = {5, 1, 4, 2, 3 };
set<int> S(data, data+5);
它给我们提供一个消除vector中重复元素的办法，并且进行排序，如下：
vector<int> v;
// …
set<int> s(all(v));
vector<int> v2(all(s));
这里，'v2'将和 'v'包含一样的元素，但是进行了升序排序，并且不具有重复元素。任何可以进行比较的元素都可以在set中进行存储。这个将在后面进行讨论。
Map
有两种关于map的解释，简单的解释如下：
map<string, int> M;
M["Top"] = 1;
M["Coder"] = 2;
M["SRM"] = 10;
int x = M["Top"] + M["Coder"];
if(M.find("SRM") != M.end()) {
M.erase(M.find("SRM"));
}
非常简单，难道不是吗？
事实上，map和set很像，除了map保存的不仅仅是值，而是一个键值对
遍历map可以简单的使用'tr()'宏。注意迭代器将会使一个std::pair的key和value，要获取值可以使用it->second.下面是个例子：
map<string, int> M;
// …
int r = 0;
tr(M, it) {
r += it->second;
}
不要使用迭代器去更改map中元素的key， 因为它可能会破坏map内部数据结构的集成性（看下面).
要记住的最重要的关于map的事情是，[]操作符将会创建一个元素,如果那个元素不存在的话。并且这个元素将会被添加到map中。所以，如果你想使你的代码更加快，绝不要用[]操作符除非你能确保那个元素已经存在与map中了。这就是为什么[]操作符不用在map作为常引用参数传递给一些函数的原因了:
void f(const map<string, int>& M) {
if(M["the meaning"] == 42) { // Error! Cannot use [] on const map objects!
}
if(M.find("the meaning") != M.end() && *M.find("the meaning") == 42) { // Correct
cout << "Don't Panic!" << endl;
}
}
Notice on Map and Set
map和set内部使用红黑树实现的。因此，当访问这些容器的时候，map和set的元素总是以升序排列。并且这就是为什么强烈建议不要在遍历map或者set时更改key值的原因了：如果你做了修改，那么将会打乱顺序，这样至少导致容器算法的不正确。
但是事实上map和set元素总是有序的这一点在解决TopCoder问题上面是很实用的。
另外一个重要的事情是定义在map和set迭代器上的操作符++和--。因此，如果值42在set当中并且它不是第一个 也不是最后一个，那么下面这段代码是可以工作的：
set<int> S;
//
set<int>::iterator it = S.find(42);
set<int>::iterator it1 = it, it2 = it;
it1--;
it2++;
int a = *it1, b = *it2;
这里a将包含42左边的第一个邻居，而b则包含右边的第一个邻居。
More on algorithms
是时候深入讨论一些算法了。大多数算法被定义在#include
sort()算法也被广泛的使用着。调用sort(begin,end)将会将一定区间进行升序排列。注意sort()需要随机访问迭代器,因此它并不是在任何容器上都适用。尽管如此，你也许不会在一个已经有序的set上调用sort()。
你已经听说了find()算法了。呼叫find(begin,end,element)将返回'element'第一次出现的迭代器或者end如果这个元素没有找到的话。与find(...)不同的是，count(begin,end,element)返回一个元素在整个容器或者部分中出现的数量。记住set和map都有成员函数find()和count(),它们都是在O(logN)内工作的，而std::find()和std::count()在O(N)内工作。
其他一些有用的算法有next_permutation()和prev_permutation()。让我们先谈谈next_permutation.调用next_permutation(begin, end)将会使区间[begin, end)保持同样元素的下一个排列或者当当前排列是最后一个排列时返回false。因此，next_permutation使得很多工作变得相当简单。如果你想要检查所有的排列，像下面这样写：
vector<int> v;
for(int i = 0; i < 10; i++) {
v.push_back(i);
}
do {
Solve(,v);
} while(next_permutation(all(v));
不用忘记确保容器中的元素在你第一次调用next_permutation(...)之前已经排序了，他们的初始状态将决定第一个排列；否则的话，有一些排列将不会被检查到。
String Streams
你经常需要处理一些字符串的输入和输出。C++为其提供了两个有趣的对象： 'istringstream'和'ostringstream'
他们都在 #include
void f(const string& s) {
// Construct an object to parse strings
istringstream is(s);
// Vector to store data
vector<int> v;
// Read integer while possible and add it to the vector
int tmp;
while(is >> tmp) {
v.push_back(tmp);
}
}
ostringstream是用来格式化输出的。下面是代码：
string f(const vector<int>& v) {
// Constucvt an object to do formatted output
ostringstream os;
// Copy all elements from vector<int> to string stream as text
tr(v, it) {
os << ' ' << *it;
}
// Get string from string stream
string s = os.str();
// Remove first space character
if(!s.empty()) { // Beware of empty string here
s = s.substr(1);
}
return s;
}
Summary
接着往下讲STL，我更想总结一下被用到的一些模版列表。这个将会简化阅读代码样例 并且我希望，提高你的TopCoder技巧。这些模版列表和宏如下：
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
vector
另外一个需要记住的是： 当#define左边的序列出现在右边时，它应该加上圆括号来避免许多不必要的问题。