使用 STL 辅助解决算法问题

不要重复制造轮子，而且你造的轮子未必比得上别人的；

<numeric>⇒ accumulate，累积容器中区间的和，可以指定初值；
为什么 STL 中的容器和算法一定关于区间的操作一定是左闭右开的呢？
- int A[n]; ⇒ sort(A, A+n);
- vector<int> ⇒ sort(A.begin(), A.end());
  
  都是很自然的一件事；

1. next_permutation ⇒ 获取下一次的全排列

所在的头文件：<algorithm>
- bool next_permutation(_BidIt _First, _BidIt _Last)
功能：对一个可迭代序列，直接在原始序列上进行更易，自然属于更易型算法。
算法意义：对全部样本空间进行穷举搜索；

#include <algorithm|vector|iterator|iostream>

using namespace std;

int main(int, char**){

    vector<int> vec{ 1, 2, 3 }; // 也可以使用一维数组，int arr[] = {1, 2, 3};

    int cnt = 0;

    do{

        copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));

                            // copy(arr, arr+3, ....)

        cout << endl;

        cnt += 1;

    } while (next_permutation(vec.begin(), vec.end()));

                            // while(next_permutation(arr, arr+3));

    cout << "A_3^3 = " << cnt << endl;

    return 0;

}

2. 容器

string 与 char []

string（字符串）与字符数组类型相比，可以避免一些额外的参数，比如需要一对指针标识当前访问的区间：
```
void foo(char *A[], int lo, int hi){

    ...

    foo(A, lo, hi);

}

void foo(string& s){

    ...

    s.substr(lo, hi-lo+1);

}
```

3. 算法

排序：sort
```
int A[n];

sort(A, A+n);
```
去重：unique（hash 表实现？）
```
unique(A, A+n); 
```
一定要注意，unique(A, A+n) - A ⇒ 去重后数组的大小；

4. pair

头文件 <utility>

常用来记录二维属性信息，比如一个会议的开始和结束时间；

int begin[101], end[101];

vector<pair<int, int>> order;

for (int i = 0; i < n; ++i){

    order.push_back(make_pair(end[i], begin[i]));

}

巴特西

使用 STL 辅助解决算法问题

1. next_permutation ⇒ 获取下一次的全排列

2. 容器

3. 算法

4. pair

最新文章

热门文章