基础数组结构

数据结构是指特定的数据组织方式，以便程序可以高效地执行。下面是在信息学编程中最常用的一些C++数组结构，其中大部分来自C++标准库（STL，standard template library）。目前比赛中都使用C++11或更新的版本（11代表2011年制定的C++标准），以下内容也以C++11为基础。还有一些常用的数据结构我们在使用到时再介绍，例如set和map。

数组和动态数组(`vector`)

你多半已经使用过数组和vector：

int a[1005];            // 一个固定长度整数数组
vector<long long> b;    // 一个动态的long long数组
 
int main() {
    ...
    b.resize(n, -1);    // 设定长度并初始化为-1
}

遍历与迭代器(`iterator`)

可以用for循环和下标变量遍历数组元素，或者可以使用迭代器(iterator)。以下四种写法效果是一样的：

for (int i = 0; i < b.size(); i++)  // 下标变量
    printf("%d\n", b[i]);
for (int i: b)                      // for-each循环
    printf("%d\n", b[i]);
for (vector<int>::iterator it = b.begin(); it != b.end(); it++) // 迭代器
    printf("%d\n", *it);
for (auto it = b.begin(); it != b.end(); it++)  // auto：自动类型推理
    printf("%d\n", *it);

范围操作

迭代器(iterator)在很多STL的库函数中都被用来指定一段范围的数据，例如排序函数sort()的参数就是一段范围。熟练使用这些函数，可以节省不少从头实现这些算法要花费的力气。注意begin()应该指向第一个要处理的元素，而end()指向最后一个元素之后的元素位置（可能并不存在）。

以下是一些常用的在范围上运行的STL函数。

sort(a.begin(), a.end());                       // 对vector a排序
sort(arr, arr+n);                               // 数组arr的范围这样指定
 
min_element(a.begin(), a.end());                // 取最小值, max_element()类似
accumulate(a.begin(), a.end(), 0);              // 求和
resize(unique(a.begin(), a.end())-a.begin());   // 对于已经排好序的a，去掉重复元素，并调整vector大小到合适

字符串

C++中有两类字符串，C字符串和string类:

#include <cstring>
...
char cs[20];        // C string
scanf("%s", cs);
char s2[20];
strncpy(s2, cs+1, 3);           // 从第二个字符开始，取3个字符
 
#include <string>
...
string ss;          // C++ string class
std::cin >> ss;
std::cout << ss.substr(1,3);    // 从第二个字符开始，取3个字符
 
char cs[] = "abc";
ss = cs;                        // C string转成C++ string
printf("%s", ss.c_str());       // C++ string转成C string

C string比较初级，操作起来并不方便，比如上面取子串操作，需要手工分配目标字符串。但好处是和stdio(scanf())能直接配合。所以如果你不需要复杂的字符串操作，那么直接使用C string没问题。

C++ string功能比较强，包括和STL(set/map)配合都很方便，但是和iostream(cin, cout)相配合，而cin/cout在编程比赛中默认会有性能差的问题，我们一般使用scanf。这时一种办法是如果题目有复杂一些的字符串操作，那可以如上面所示，在字符串scanf进来之后，立即转换成C++ string，之后操作都在C++ string上进行。

关于内存使用

在编程比赛中，题目的数据规模相对固定，所以从节省比赛时间考虑，我们经常使用全局变量（虽然在更大规模的应用编程中全局变量很不推荐使用）。例如：

int a[200005];              // a数组需要2*10^5的时候，多分配5个元素，以避免有少量越界时的错误
vector<int> graph[100005];  // 图的邻接表存储
 
int main() {
    ...
}

CSP比赛一般的程序内存限制是256MB，也就是大约 $256 \cdot 10^6$ 字节，或者 $64 \cdot 10^6$ 个int，又等于 $32 \cdot 10^6$ 个long long。解题时，需要考虑解法是否会超出内存限制。

本地和全局变量

要注意不要有过大的本地变量（函数中的变量），因为本地变量在程序执行栈上分配，而执行栈的空间一般较小（Windows 1MB, Linux 8MB）。例如以下程序:

#include <cstdio>
int main() {
        int x[2005][2005];
        x[0][0] = 1;
        printf("%d", x[0][0]);
        return 0;
}

执行时就直接seg fault了:

[1]    80766 segmentation fault  ./test

解决办法是将大数组变成全局变量，或者使用vector<vector<int>>类型的本地变量，vector是动态分配内存，不存在导致堆栈空间溢出的问题。