leetcode —— Two Sum
刷题刷到std::pair和make_pair()函数，记录下用法，做一个?上人。
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
class Solution
{
// 新思路，两根指针分别指向vector首部以及尾部
// 左侧指针向右移，右侧指针向左移
// 两指针指向的内存数据相加与target比较
// 左侧指针只在相加结果<target时右移，
// 右侧指针只在相加结果>target时左移。
// 左侧指针与右侧指针相遇时结束。
public:
vector<int> twoSum(vector<int> &nums, int target)
{
vector<int> ret;
// 对nums排序并保存下标
std::vector< std::pair<int, int> > nums_;
int nums_size = nums.size();
for (int i = 0; i < nums_size; ++i) { nums_.push_back(make_pair(nums[i], i)); }
std::sort(nums_.begin(), nums_.end());
// 下标声明
int l = 0, r = nums_.size() - 1;
while (l < r)
{
if (nums_[l].first + nums_[r].first == target)
{
ret.push_back(nums_[l].second);
ret.push_back(nums_[r].second);
break;
}
else if (nums_[l].first + nums_[r].first > target)
{
r--;
}
else l++;
}
return ret;
}
};
int main()
{
//int arr[100] = {0};
//cout << arr[0] << " " << arr[1]<<" "<<arr[100];
Solution m_sol;
vector<int> nums{ 2,7,11,15 };
vector<int> m_return;
m_return=m_sol.twoSum(nums , 13);
for (auto i : m_return)
cout << i << " ";
return 0;
}
使用vector配合std::pair成为简易的unordered_map；
背景
C/C++ 语言中的函数只能返回一个值。那么我们如何达到返回多个值的目的?
- 使用指针指向一个容纳多个非对称类型的值的结构，将指针返回到该数据类型的数组。
- 使用元组tuple（用于返回多个值）和成对pair（用于两个值）。
std::pair
1 pair的应用
pair是将2个数据组合成一个数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量。
2 make_pair函数
template pair make_pair(T1 a, T2 b) { return pair(a, b); }
很明显，我们可以使用pair的构造函数也可以使用make_pair来生成我们需要的pair。 一般make_pair都使用在需要pair做参数的位置，可以直接调用make_pair生成pair对象很方便，代码也很清晰。 另一个使用的方面就是pair可以接受隐式的类型转换，这样可以获得更高的灵活度。灵活度也带来了一些问题如：
std::pair<int, float>(1, 1.1);
std::make_pair(1, 1.1);
是不同的，第一个就是float，而第2个会自己匹配成double。
类模板：template <class T1, class T2> struct pair
参数：T1是第一个值的数据类型，T2是第二个值的数据类型。
功能：pair将一对值组合成一个值，这一对值可以具有不同的数据类型（T1和T2），两个值可以分别用pair的两个公有函数first和second访问。
具体用法：
1.定义（构造）：
1 pair<int, double> p1; //使用默认构造函数
2 pair<int, double> p2(1, 2.4); //用给定值初始化
3 pair<int, double> p3(p2); //拷贝构造函数2.访问两个元素（通过first和second）：
1 pair<int, double> p1; //使用默认构造函数
2 p1.first = 1;
3 p1.second = 2.5;
4 cout << p1.first << ' ' << p1.second << endl;输出结果：1 2.5
std::tuple
pair 可以理解为一种特殊的 tuple（只有 2 个元素的 tuple），tuple是一个固定大小的不同类型值的集合，是泛化的std::pair。我们也可以把他当做一个通用的结构体来用，不需要创建结构体又获取结构体的特征，在某些情况下可以取代结构体使程序更简洁，直观。std::tuple理论上可以有无数个任意类型的成员变量，而std::pair只能是2个成员，因此在需要保存3个及以上的数据时就需要使用tuple元组了。
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
// A Method that returns multiple values using
// tuple in C++.
tuple<int, int, char> foo(int n1, int n2)
{
// Packing values to return a tuple
return make_tuple(n2, n1, 'a');
}
// A Method returns a pair of values using pair
std::pair<int, int> foo1(int num1, int num2)
{
// Packing two values to return a pair
return std::make_pair(num2, num1);
}
int main()
{
int a,b;
char cc;
// Unpack the elements returned by foo
std::tie(a, b, cc) = foo(5, 10); //创建到其参数或 std::ignore 实例的左值引用的 tuple 。
// Storing returned values in a pair
std::pair<int, int> p = foo1(5,2);
cout << "Values returned by tuple: ";
cout << a << " " << b << " " << cc << endl;
cout << "Values returned by Pair: ";
cout << p.first << " " << p.second;
return 0;
}
std::tie
std::tie
能用于引入字典序比较到结构体，或解包 tuple 。通过tie解包将会把这4个元素的值分别赋值给tie提供的4个变量中。
#include <iostream>
#include <string>
#include <set>
#include <tuple>
struct S {
int n;
std::string s;
float d;
bool operator<(const S& rhs) const
{
// 比较 n 与 rhs.n,
// 然后为 s 与 rhs.s,
// 然后为 d 与 rhs.d
return std::tie(n, s, d) < std::tie(rhs.n, rhs.s, rhs.d);
}
};
int main()
{
std::set<S> set_of_s; // S 为可比较小于 (LessThanComparable)
S value{42, "Test", 3.14};
std::set<S>::iterator iter;
bool inserted;
// 解包 insert 的返回值为 iter 与 inserted
std::tie(iter, inserted) = set_of_s.insert(value);
if (inserted)
std::cout << "Value was inserted successfully\n";
}
std::optional
std::optional 是在 C++ 17 中引入到标准库中的，C++ 17 之前的版本可以通过 boost::optional 实现几乎相同的功能。
-
在
cppreference
中对其描述：
The class template
std::optional
manages an
optional
contained value, i.e. a value that may or may not be present.
A common use case for
optional
is the return value of a function that may fail. As opposed to other approaches, such as
std::pair
<T,bool>,
optional
handles expensive-to-construct objects well and is more readable, as the intent is expressed explicitly.
类模板
std::optional
管理一个
可选
的容纳值，即可以存在也可以不存在的值。
一种常见的
optional
使用情况是一个可能失败的函数的返回值。与其他手段，如
std::pair
<T,bool> 相比，
optional
良好地处理构造开销高昂的对象，并更加可读，因为它显式表达意图。
若一个
optional<T>
含值，则保证值作为
optional
对象所用空间的一部分分配，
即不会发生动态内存分配。
从而
optional
对象模拟一个对象，而非指针，尽管定义了
operator*()
和
operator->()
运算符。
当一个
optional<T>
对象被
隐式转换成 bool
时，若对象含值则转换返回 true ，若对象不含值则返回 false 。
optional
对象在下列条件下含值：
-
对象被以
T
类型值或另一含值的
optional
初始化/赋值。
对象在下列条件下不含值：
- 对象被默认初始化。
-
对象被以
std::nullopt_t
类型值（ 等同于{ } ）或不含值的
optional
对象初始化/赋值。 -
调用了成员函数
reset()
。
如果程序
optional
使用引用类型实例化一个程序，则格式不正确。另外，类型
optional
为
std :: reference_wrapper
的
T
可以用来保存引用。
此外，如果程序
optional
使用（可能是cv限定的）标记类型
std :: nullopt_t
或
std :: in_place_t
实例化一个程序，则该程序格式将报错。
创建一个 optional 的方法：
// 空 optiolal
optional<int> oEmpty;
optional<float> oFloat = nullopt;
optional<int> oInt(10);
optional oIntDeduced(10); // type deduction
// make_optional
auto oDouble = std::make_optional(3.0);
auto oComplex = make_optional<complex<double>>(3.0, 4.0);
// in_place
optional<complex<double>> o7{in_place, 3.0, 4.0};
// initializer list
optional<vector<int>> oVec(in_place, {1, 2, 3});
// 拷贝赋值
auto oIntCopy = oInt;
示例：
#include <iostream>
#include <string>
#include <functional>
#include <optional>
struct Out {
std::string out1{ "" };
std::string out2{ "" };
};
std::optional<Out> func(const std::string& in) {
Out o;
if (in.size() == 0)
return std::nullopt;
o.out1 = "hello";
o.out2 = "world";
return { o };
}
// optional can be used as the return type of a factory that may fail
std::optional<std::string> create(bool b) {
if (b)
return "Godzilla";
return {};
}
// std::nullopt can be used to create any (empty) std::optional
auto create2(bool b) {
return b ? std::optional<std::string>{"Godzilla"} : std::nullopt;
}
// std::reference_wrapper may be used to return a reference
auto create_ref(bool b) {
static std::string value = "Godzilla";
return b ? std::optional<std::reference_wrapper<std::string>>{value}: std::nullopt;
}
int main()
{
if (auto ret = func("hi"); ret.has_value()) {
std::cout << ret->out1 << std::endl;
std::cout << ret->out2 << std::endl;
}
std::cout << "create(false) returned "
<< create(false).value_or("empty") << '\n';
// optional-returning factory functions are usable as conditions of while and if
if (std::optional<std::string> str = create2(true)) {
std::cout << "create2(true) returned " << *str << '\n';
}
if (auto str = create_ref(true)) {
// using get() to access the reference_wrapper's value
std::cout << "create_ref(true) returned " << str->get() << '\n';
str->get() = "Mothra";
std::cout << "modifying it changed it to " << str->get() << '\n';
}
}
使用 std::optional 带来的好处：
- 省去了运行状态的 bool 值的声明，让代码更简洁，更注重返回值本身的语意
- 不用担心额外的动态内存分配，这一点会在后面的文章里详细展开
参考文章：