STL基本操作小记

算法题所用到的一些STL功能

作者 Trevor Cui 日期 2018-02-09
basis LeetCode
STL基本操作小记

在刷算法题时，若使用C++，有了STL的助力会使会使代码简洁易懂很多，写起来也会变得便捷。有人说用STL会弱化编程能力，其实我认为，如果只用基本的数据结构的基本操作的话，不算是在走捷径，毕竟不可能每次用到一个数据结构的时候都现造轮子，尤其是在笔试面试这样的短时间高强度的场合中。因此本文总结归纳一些算法题中常会用到的数据结构和基本操作，并尽量保证所展现的操作不超出数据结构本身的能力范围。同时，也会有一些系统自带的基础算法和一些结构等。只要算法题中我遇到的都会写在本文中。

常用容器

Vector

Vector相当于动态数组，平常一般用来直接作为数组使用。在LeetCode中vector现在一般也直接用作数组的输入和输出参数。

引用文件：#include <vector>

初始化一个vector：

vector<int> vec;
vector<int> vec1(12);         // 12个int类型值为0的元素
vector<int> vec2(12, 9);      // 12个int类型值为9的元素

// 若 a 是一个数组（vector、set等容器均可）
vector<int> vec3(a+i, a+j)    // vec3的初始值为 a 数组中 i - j 位元素（index从0开始）

其他的一些基本操作：

// 在数组尾部操作
vec.push_back(x);
vec.pop_back();

// 数组的迭代
for(int i = 0; i < vec.size(); i++)
vector<int>::iterator iter = vec.begin();
cout << *iter << endl;

// 插入元素
// vector.insert(<起始地址>, <插入的数量>, <元素值>)，其中若插入数量为1，可以只传递(<起始地址>, <元素值>)
vec.insert(vec.begin() + i, count, number);     // i 从 0 开始，表示新插入的元素在第 i 位

// 删除元素
// vector.erase(<删除元素的地址>);
// vector.erase(<删除元素的起始地址>，<终止地址>);
vec.erase(vec.begin() + i, vec.begin() + j);    //i 仍然从 0 开始

// 清空数组
vec.clear();

Set

Set 在算法题中一般就是拿来当作一个不含重复值的数组来使用了。

#include <set>
set<int> s;
// set<int> s(a.begin(), a.end())
s.insert(x);

// set大小：s.size()
// set起始：s.begin()

if(s.find(x) != s.end()) {
    s.erase(x);
}
s.count(x)                    // 返回值为 0（未找到） 或 1（找到）

if(!s.empty()) {
    s.clear();
}

Queue

队列是非常常用的一种数据结构，特点为先进先出。若只需要普通队列的功能，头文件 <queue> 即可；若需要使用双端队列，可引入STL头文件 <deque>。

普通队列：

#include <cstdlib>
#include <queue>

queue<int> q;
q.push(x);
if(!q.empty()) {
    q.pop();             // 注：弹出元素时不会返回弹出值
}
int m = q.front()        // 队首：最早被压入的元素
int n = q.back()         // 队尾：新压入的元素
int length = q.size()    // 队列的长度

双端队列：

#include <deque>

deque<int> dq;
deque<int> dq1(dq);     // 把 dq 的值赋给 dq1
dq1.swap(dq);


dq.push_back(x);
dq.pop_front();

dq.push_front(x);
dq.pop_back();

int m = dq.front();
int n = dq.back();

int length = dq.size();
bool isEmpty = dq.empty();
dq.clear();             // 清空队列

Stack

栈也是一种很常见的数据结构，特点是先进后出。

#include <stack>

stack<int> s;

s.push(x);
int m = s.top();
if(!s.empty()) {
    s.pop();          // 一样，stack 的 pop 函数不返回栈顶的值
}

int length = s.size();

Map

Map是STL的一个关联容器，提供一对一的数据处理能力，在算法题中，我一般拿它当作哈希表来用。实际上STL还有 hash_map。区别上，map 是用红黑树来实现的，查找复杂度为 O(log(n))，hash_map 是用哈希表实现的，查找时间复杂度为 O(1)，如果记录非常大，还是建议使用 hash_map，查找效率会高很多。使用上两者的使用方法差别不大，这里就用 map 来做个示范。

#include <map>

map<int, int> mymap;

mymap[i] = j;
mymap.erase(i);

int size = mymap.size();
if(mymap.find(i) != mymap.end()) {
    // todo for mymap[i]
}

mymap.clear();

堆

使用STL构建一个堆主要是 vector 容器和几个函数相结合。在时间复杂度上面，堆插入元素的时间复杂度为 O(logn)，得到最小（最大）值的时间复杂度为 O(1)。示例代码如下：

#include <algorithm>
#include <vector>

// make_heap：对于数组[first, last)范围内进行堆排序
// cmpObject：比较对象，默认为最大堆less<int>，最小堆用greater<int>，后面三个函数一样
// make_heap(first, last)
// make_heap(first, last, cmpObject)
// push_heap：对刚插入的（尾部）元素做堆排序
// push_heap(first, last)
// pop_heap：将front（即第一个最大元素）移动到end的前部，同时将剩下的元素重新构造成(堆排序)一个新的heap
// pop_heap(first, last)
// sort_heap：将一个堆做排序,最终成为一个有序的系列（必须先得是一个堆）
// sort_heap(first, last)

// Example：剑指offer获取数组的中位数，构造最小堆和最大堆的过程
void Insert(int num) {
    if (((min.size() + max.size()) & 0x1) == 0) {
        if (max.size() > 0 && num < max[0]) {
            max.push_back(num);
            push_heap(max.begin(), max.end(), less<int>());
            num = max[0];
            pop_heap(max.begin(), max.end(), less<int>());
            max.pop_back();
        }
        min.push_back(num);
        push_heap(min.begin(), min.end(), greater<int>());
    } else {
        if (min.size() > 0 && num > min[0]) {
            min.push_back(num);
            push_heap(min.begin(), min.end(), greater<int>());
            num = min[0];
            pop_heap(min.begin(), min.end(), greater<int>());
            min.pop_back();
        }
        max.push_back(num);
        push_heap(max.begin(), max.end(), less<int>());
    }
}

Algorithm

C++ 的 <algorithm> 库很强大，很多算法题常用的函数都在该库中。

sort

sort 主要用于对于一个序列，有序的操作比乱序简便很多，且快排 O(nlog(n)) 的时间复杂度对于处理该问题可以接受时。

#include <algorithm>

bool myfunction(int i, int j) { return (i < j); }

sort(vector.begin(), vector.end());
sort(vector.begin(), vector.end(), myfunction);
sort(vector.begin(), vector.end(), [](int i, int j) {
    return i < j;
});

此外，还有三种排序，只做简单说明：

1、stable_sort：稳定排序

2、partial_sort：部分排序

3、partial_sort_copy：复制并排序

最大值、最小值、replace、swap

很简单，主要为了做说明，直接上代码：

#include <iostream>     // std::cout
#include <algorithm>    // std::min_element, std::max_element

using namespace std;

bool myfn(int i, int j) { return i<j; }

int main () {
    int myints[] = {10, 20, 30, 30, 20, 10, 20};
    vector<int> myvector(myints, myints + 8);

    cout << min(myints[0], myints[1]) << endl;
    cout << max(myints[0], myints[1]) << endl;

    cout << *min_element(myints, myints+7) << endl;
    cout << *max_element(myints, myints+7) << endl;

    // using function myfn as comp:
    cout << *min_element(myints, myints+7,myfn) << endl;
    cout << *max_element(myints, myints+7,myfn) << endl;
    
    replace(myvector.begin(), myvector.end(), 20, 90)        // replace all 20 to 90
    
    swap(myvector[0], myvector[1]);

    return 0;
}

其他

pair

pair 是在做LeetCode 406题时遇到的，然后对其进行了一番查找，发现其操作还是挺简便的。

#include <utility>                                    // pair 的头文件
#include <vector>

pair<int, int> p;
vector<pair<int, int>> vec;

while(cin >> p.first >> p.second) {                   // 使用 .first、.second 快速访问 pair 的两个元素
    vec.push_back(make_pair(p.first, p.second));      // 使用 make_pair 新建一个 pair
}

for(auto node : p) {                                  // 使用 auto : 来进行整个 vector 的迭代较简便
    //todo for node.first & node.second
}
FEATURED TAGS
basis LeetCode