C++ 算法题常用工具函数

C++ STL 提供的工具函数非常强大，但是对于不是经常使用拿来干活的人来说（比如我），经常会忘记如果使用这些函数。所以我专门写一篇来总结一下一些做算法常用的工具函数。

虽说现在 LeetCode 支持各种个样的编程语言提交，不过由于我从小到大做算法题都是用的 C++，成为传统的。按理说现在直接用js写会更快一些的。

集合求和

const data1 = [1,2,3]
const result1 = _.sum(data1)

const data2 = [{ a: 1 }, { a: 2 }, { a: 3 }]
const result2 = _.sumBy(data2, (i) => i.a)
const result3 = data2.reduce((result, i) => {
    result += i.a
    return result;
}, 0)

#include <numeric>      // std::accumulate

std::vector<int> data1 = {1,2,3};
int result1 = std::accumulate(data1.begin(), data1.end(), 0);

struct Item {
	int a;
};
std::vector<Item> data2 = {{1}, {2}, {3}};
auto result2 = std::accumulate(data2.begin(), data2.end(), 0, [](int& result, Item& i) {
	return result + i.a;
});

C++ 的 `std::accumulate`  相当于 JavaScript 的 `Array.reduce`

集合最大最小

const data1 = [1,2,3]
const max1 = _.max(data1)
const min1 = _.min(data1)

const data2 = [{ a: 1 }, { a: 2 }, { a: 3 }]
const max2 = _.maxBy(data2, (i) => i.a)
const min2 = _.minBy(data2, (i) => i.a)

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

std::vector<int> data1 = {1,2,3};
int max1 = std::max_element(data1.begin(), data1.end());
int min1 = std::min_element(data1.begin(), data1.end());

struct Item {
	int a;
};
std::vector<Item> data2 = {{1}, {2}, {3}};
auto max1 = std::max_element(data2.begin(), data2.end(), [](Item& i, Item& j) {
	return i.a < j.a;
});
auto min1 = std::min_element(data2.begin(), data2.end(), [](Item& i, Item& j) {
	return i.a < j.a;
});

C++ 的 `max_element` 和 `min_element` 的 comp function 很奇怪，都要求前一个元素比后一个元素小为 True。不知道为何 C++ 要如此设计。理论上这两个函数可以反着用。

auto max1 = std::min_element(data2.begin(), data2.end(), [](Item& i, Item& j) {
	return i.a > j.a;
});
auto min1 = std::max_element(data2.begin(), data2.end(), [](Item& i, Item& j) {
	return i.a > j.a;
});

二分查找

• `std::lower_bound` 在前闭后开区间进行二分查找，返回大于或等于目标值的第一个元素位置。如果所有元素都小于目标值，则返回区间最后元素的位置。
• `std::upper_bound` 在前闭后开区间查找的关键字的上界，返回大于目标值的第一个元素位置。如果目标值大于所有元素，则返回区间最后元素的位置。
• `std::binary_search` 在前闭后开区间查找的关键字，返回是否存在的布尔值。

#include <algorithm>    // std::lower_bound, std::upper_bound

std::vector<int> data1 = {1,6,3,4,2};
sort(data1.begin(), data1.end());
auto result1 = std::lower_bound(data1.begin(), data1.end(), 4);
auto result2 = std::upper_bound(data1.begin(), data1.end(), 4);
bool result3 = std::binary_search(data1.begin(), data1.end(), 4);

struct Item {
	int a;
};
std::vector<Item> data2 = {{1}, {6}, {3}, {4}, {2}};
sort(data2.begin(), data2.end(), [](Item& i, Item& j) {
	return i.a < j.a;
});
auto result1 = std::lower_bound(data2.begin(), data2.end(), 4, [](Item& i, int target) {
	return i.a < target;
});
auto result2 = std::upper_bound(data2.begin(), data2.end(), 4, [](Item& i, int target) {
	return i.a < target;
});
bool result3 = std::binary_search(data2.begin(), data2.end(), 4, [](Item& i, int target) {
	return i.a < target;
});

交换值

#include <algorithm>    // std::swap, std::iter_swap

int a = 1; int b = 2;
std::swap(a, b);

std::vector<int> data1 = {1,6,3,4,2};
std::iter_swap(data1.begin()+1, data1.begin()+3);

字符串前后缀匹配

const text = "Hello World!"
text.startsWith("He")
text.endsWith("d!")

bool startsWith(std::string s, std::string sub) {
	return s.find(sub) == 0 ? true : false;
}

bool endsWith(std::string s, std::string sub) {
	return s.rfind(sub) == (s.length() - sub.length()) ? true : false;
}

map/transform

const data = [1,2,3]
const result = data.map((i) => {
    return { a: i }
})

#include <algorithm> // std::transform

struct Item {
	int a;
};

std::vector<int> data = {1,6,3,4,2};
std::vector<Item> result(data.size());
std::transform(data.begin(), data.end(), result.begin(), [](const int& i) -> Item {
	return Item({i});
});

集合过滤

const data = [1,2,3,4,5]
const result = data.filter((i) => i % 2 == 0)

JavaScript 里的 Array.prototype.filter 返回的数据，对 Object 类型的集合元素是引用。C++ 语言对于集合过滤的处理有两个方法：copy_if 和 remove_if。copy_if 对原集合做过滤处理并返回复制的新数据，而 remove_if 则是在原集合基础上原地修改。在做算法题的时候要注意一下。

#include <algorithm>    // std::copy_if, std::remove_if

struct Item {
	int a;
};
std::vector<Item> data = {{1}, {6}, {3}, {4}, {2}};
std::vector<Item> result;

std::copy_if(data.begin(), data.end(), std::back_inserter(result), [](const Item& item) {
	return item.a % 2 == 0;
});
auto pend = std::remove_if(data.begin(), data.end(), [](const Item& item) {
	return item.a % 2 == 0;
});
data.erase(pend, data.end());

优先队列

普通队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。而在优先队列中，元素被赋予了优先级。当访问元素时，最高优先级的元素会被最先删除。

// 小顶堆
priority_queue<int, vector<int>, greater<int>> pq1;

// 大顶堆
priority_queue<int> pq2;
priority_queue<int, vector<int>, less<int>> pq3;

集合连接

const data1 = [1,2,3]
const data2 = [4,5,6]
const result = data1.concat(data2)

和集合过滤一样的，C++ 中对集合连接也要考虑到是复制还是引用操作。

std::vector<int> data1 = {1,2,3};
std::vector<int> data2 = {4,5,6};
data1.insert(data1.end(), data2.begin(), data2.end());

std::vector<int> data3 = {1,2,3};
std::vector<int> data4 = {4,5,6};
std::move(data4.begin(), data4.end(), std::back_inserter(data3));
data4.clear();

前缀和工具 partial_sum

vector<int> data = {1,2,3,4,5,6,7,8};
vector<int> result(data.size());
partial_sum(data.begin(), data.end(), result.begin(), [](int result, int i) {
	return result * 2 + 1;
});