算法竞赛初级杂烩包

杂烩

参考网站

• cplusplus
• cppreference
• cppreferne中文

STL

vector 向量（长度可定义数组）

在头文件 <vector> 中的定义
template <class T, class Allocator = std::allocator<T> > class vector;

vector 相当于一个可变长数组，效率和使用数组没有明显差别

常见用法，建立邻接表（PS：其实我是第一次这么用，学到了 \^_^/）

<div class="md-section-divider"></div>
#include <iostream>
<div class="md-section-divider"></div>
#include <vector>
const int maxn = 110;
vector <int> tab[maxn];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) tab[i].clear();
    for (int i = 0; i < m; i ++) {
        int a, b;
        cin >> a >> b;
        tab[a].push_back(b);
    }
}
<div class="md-section-divider"></div>

如何使用这张邻接表呢？

遍历所有与 a 结点相连的结点

for (int i = 0; i < tab[a].size(); i ++) cout << tab[a][i] << endl;
<div class="md-section-divider"></div>

注意： vector 的 size()方法返回的是一个 size_t 也就是 unsign int，所以如果 vector为空的话，size()返回的 0，(unsigned int)0 - 1 = 4294967295，所以这样写

for (int i = 0; i <= tab[a].size() - 1; i ++) cout << tab[a][i] << endl;
<div class="md-section-divider"></div>

是很危险的 = =

其他重要成员

• vector::clear() vector是有 clear() 的
• vector::resize() 改变容器中可存储元素的个数，如 xxx.resize(100) 可以得到长度为100的数组
• vector::begin() 返回首个元素的迭代器
• vector::end() 返回终止位置的迭代器，注意是最后一个元素还要往后一个元素的位置
• vector::push_back()
• vector::pop_back()
• vector::erase()

pair

pair 在头文件 <utility>中定义

template <class T1, class T2> struct pair;
std::pair 是一个结构模板，提供了一种将两个异构对象存储为一个单元的方法，用法举例：

typedef pair<int,int> point; //表示一个点
typedef pair<string,int> name_and_id_pair; // 学生姓名和学号
typedef pair<int,double> id_to_height pair; // 学生学号和身高

构造方法和 make_pair

pair<int,int> point1 = make_pair(1,1);
pair<double,double> point2 = make_pair(2.0,3.0);
pair<int,int> point3 = pair<int,int>(1.0,2.0);
pair<int,int> point4 = make_pair(1.0,2.0); // 这句会编译失败，因为make出来的是pair<double,double> 却赋值给了pair<int,int>

sort

sort 在头文件 <algorithm> 中定义

template< class RandomIt > 
void sort( RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

范围 [first, last)（注意左闭右开）中的元素进行排序按升序排列，相等元素的顺序是不能保证。第一个原型是用 operator< 比较的元素（即从小到大），第二个版本使用给定的比较函数 comp，可以自定义排序关键字和顺序.

• 对基本类型的数组进行排序
  以为指针也是 RandomIt 的一种，所以 sort 直接传入指针就好了

sort(arr, arr + n);

• 对 vector 进行排序

vector 能直接返回迭代器，所以可以直接用

vector <int> arr;
sort(arr.begin(), arr.end());

如果想从大到小排序，需要用到 sort 第二种原型，第二种原型中的第三个参数 Compare comp 是一个比较器，可以传入 greater

vector <double> arr;
sort(arr.begin(), arr.end(), greater<double>());

比较器 std::greater 的使用方法

greater 在头文件 <functional> 中定义

template< class T > struct greater;

我们需要传入的实际上是是一个 greater 类型的变量,所以需要调用 greater 的构造函数，最后写成 greater<double>()

• 对 pair 排序
  排序 pair 非常容易，直接 sort 的时候默认以 first 为第一关键字，second 为第二关键字排序

vector<pair<int,int> > events;
sort(events.begin(), events.end());

• 对自定义结构体进行排序
  只需要重载结构体的运算符如：< 或 >即可

struct T_event {
    int begin, end;
    bool operator <(const T_event &other) const {
        return begin < other.begin；
    }
};
vector<T_event> events;
sort(events.begin(), events.end());

注意：比较重载运算符的两处 const，和引用 &。const T_event &other 防止比较函数对 other 进行修改，第二个 const 是限制比较函数不得修改所在的结构体的成员。如果不加这两个 const 限定就会爆满屏幕的编译错误。而比较的时候，另一个变量必须以引用方式 & 传递

• 对多关键字排序

struct Three_key {
    int a, b;
    double c;
    bool opeartor < (const Three_key &other) const {
        if (a != other.a) return a > other.a;
        if ((int)c != (int)other.c) return (int)c < (int)other.c;
        return b > other.b;
    }
};

• 使用比较函数排序
  自定义比较函数，然后向 sort 中传入函数指针，如

vector<pair<int,int> > points;
bool cmp_x_inc(const pair<int,int> &p1, const pair<int,int> &p2) {
    return p1.first < p2.first;
}
bool cmp_y_dec(const pair<int,int> &p1, const pair<int,int> &p2) {
    return p1.second < p2.second;
}
sort(points.begin(),points.end(),cmp_x_inc);//X 升序
//do something...
sort(points.begin(),points.end(),cmp_y_dec);//Y 降序

• 对字符串排序
  不推荐将字符串封装在结构体中，然后在结构体中重载运算符的方法，这样会造成结构体太大

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int N = 0;
char strs[1000][1000];
vector<char *> strs_sorted;
bool char_ptr_cmp(const char *a, const char *b) {
    return strcmp(a,b) < 0;
}
int main() {
    while (scanf("%s", strs[N++]) != EOF);
    for (int i = 0; i < N; i++) strs_sorted.push_back(strs[i]);
    sort(strs_sorted.begin(), strs_sorted.end(), char_ptr_cmp);
    printf("sorted strs are:\n");
    for (vector<char*>::iterator it = strs_sorted.begin(); it != strs_sorted.end(); it++) printf("%s\n", *it);
    return 0;
}

• 使用自定义比较器（伪函数）

——以上内容参考学习自 comzyh 的《算法竞赛初级杂烩包》，并进行整理