从一个小题中的应用来体会下std::tie的便利之处
文章目录
- 前言
- 解题过程
- 爬楼梯的最少成本
- 题目分析
- DP优化
- 利用tie进行写法优化
- std::tuple
- std::tuple的访问
- std::tie函数中使用std::ignore占位
- 总结
前言
今天主要学习一下 std::tie 函数的使用方法，之前看到 tie 函数是和 IO 绑定的，最近发现它是和 std::tuple 绑定的，查询资料后发现两个函数虽然名字相同，但是在不同的作用域下，今天学一下和 tuple 有关的这个 tie 函数，不过在学习之前先看一道小题。
解题过程
爬楼梯的最少成本
这是 LeetCode 上的一道题，题目描述如下：
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
提示：
2 <= cost.length <= 1000
0 <= cost[i] <= 999
题目分析
这种求解最小花费、最大方案数，最大价值的题目是典型的动态规划题目，这道题也可以使用动态规划的方式来解，既然每次可以选择爬一个或者两个阶梯，那么到达某一个阶梯的花费就等于这个阶梯的花费加上前一个阶梯花费和前两个花费的之间最小值即可，最终的结果取最后一个阶梯和倒数第二个阶梯中的最小值，代码比较简单，实现如下：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> ans(n);
ans[0] = cost[0];
ans[1] = cost[1];
for (int i = 2; i < n; i++) ans[i] = min(ans[i-1], ans[i-2]) + cost[i];
return min(ans[n-1], ans[n-2]);
}
};
DP优化
虽然使用dp数组求解起来很方便，但是从实现上可以看出，每个阶梯的花费只与它前两个阶梯的花费有关，所以使用一个长度为N的数组在空间上有些浪费，其实只要两个变量就可以了，我们用 first 和 second 两个变量分别表示某个阶梯前两个阶梯的花费，可以实现如下代码：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size(), first = cost[0], second = cost[1];
for (int i = 2; i < n; i++) {
int temp = min(first, second) + cost[i];
first = second;
second = temp;
}
return min(first, second);
}
};
利用tie进行写法优化
使用两个变量优化之后这个算法变成了 O(1) 的空间复杂度，但是在 for 循环中的写法还是有些啰嗦，其实这种写法和交换两个变量值过程非常相似，在GO语言中可以写成 a,b = b,a 来完成交换，但是在C++中这样的写法是错误的，不管是引入第三个变量，还是通过异或解决都需要写三条语句，但是这种情况在遇到 std::tie 函数之后有望得到改变，上面的写法利用 std::tie 可以改写如下：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size(), first = cost[0], second = cost[1];
for (int i = 2; i < n; i++) tie(first, second) = make_tuple(second, min(first, second) + cost[i]);
return min(first, second);
}
};
std::tuple
在学习 std::tie 的作用方式之前，先来看一下 std::tuple 是什么。如果你对这个结构有些陌生，可以先想想 std::pair 这个结构。首先 std::tuple 是一个类模板，同时他也是一个固定大小的由各种类型的值组成集合，是 std::pair 的一种泛化实现。
std::pair 中包含两个元素，而 std::tuple 可以同时包含多个元素，它拥有 struct 的表现，但是无需定义实际的 struct，在函数返回多个值时拥有良好的表现。
std::tuple的访问
- 利用
std::get函数通过下标访问（C++11）
auto t = std::make_tuple(110, "excellent", 3.14);
std::cout << "(" << std::get<0>(t) << ", " << std::get<1>(t)
<< ", " << std::get<2>(t) << ")" << std::endl;
- 利用
std::tie函数进行参数解绑（C++11)
auto t = std::make_tuple(110, "excellent", 3.14);
int n;
std::string s;
float d;
std::tie(n, s, d) = t;
std::cout << "(" << n << ", " << s << ", " << d << ")" << std::endl;
- 利用
std::get函数通过类型访问（C++14），这种使用方式如果每种类型不唯一会出现编译错误
auto t = std::make_tuple(110, "excellent", 3.14);
std::cout << "(" << std::get<int>(t) << ", " << std::get<const char*>(t)
<< ", " << std::get<double>(t) << ")" << std::endl;
- 利用结构化绑定的方式来访问（C++17）
auto t = std::make_tuple(110, "excellent", 3.14);
auto [n, s, d] = t;
std::cout << "(" << n << ", " << s << ", " << d << ")" << std::endl;
以上的几个例子的输出结果都是 (110, excellent, 3.14)
std::tie函数中使用std::ignore占位
使用 std::tie 函数来获取 std::tuple 参数时，有时不需要所有的参数，这种情况下可以使用 td::ignore 来占位，代替那些不关心的参数，比如 std::set 结构中 insert 函数的返回值。
std::set<int> st;
std::pair<std::set<int>::iterator, bool> sp1 = st.insert(4);
std::cout << *sp1.first << " " << sp1.second << std::endl;
std::pair<std::set<int>::iterator, bool> sp2 = st.insert(4);
std::cout << *sp2.first << " " << sp2.second << std::endl;
运行结果如下：
4 1
4 0
如果我们不关心插入的元素是什么，只想知道此次插入操作是否成功，可以利用 std::tie 和 std::ignore 来实现：
std::set<int> st;
bool inserted = false;
std::tie(std::ignore, inserted) = st.insert(4);
std::cout << inserted << std::endl;
std::tie(std::ignore, inserted) = st.insert(4);
std::cout << inserted << std::endl;
运行结果如下：
1
0
总结
std::tuple是std::pair一种更加通用的实现，std::pair只能包含两个元素，而std::tuple可以包含多个任意类型的元素- tie 本意是系牢、约束、连接、束缚的意思，用在
std::tuple上却是用来解绑参数的，含义恰好相反了，很有趣是不是 - 实际上
std::tie这个函数的作用是把一些左值绑定到std::tuple来达到解析参数的目的，函数作用还是 “tie” std::ignore可以用在std::tie函数中作为占位符，用来替代一些不关心的参数
有些事情反过来想一想，问题可能很快就解决了——记一次拼图游戏中一个对手的高谈阔论