常用工具函数

集合求和

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());

集合连接

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;
});