pair
pair是 C++ STL（标准模板库）中的一个模板类，用于表示一对相关的对象。它是一个简单的容器，存储两个数据项，它们可以是不同类型的。pair 常用于需要将两个元素一起操作的情况，例如在处理字典（映射）数据结构时，键值对就是一个常见的 pair 示例。
#include <iostream>
#include <utility> // 引入pair的定义
int main() {
// 创建一个pair
std::pair<int, std::string> p(1, "Hello");
std::cout << "First: " << p.first << std::endl; // 输出: First: 1
std::cout << "Second: " << p.second << std::endl; // 输出: Second: Hello
return 0;
}
使用场景
键值对：pair 在处理映射（map）时非常有用，std::map 容器中的元素类型就是 pair，它表示一个键值对。
std::map<int, std::string> m;
m[1] = "Apple";
m[2] = "Banana";
for (const auto& p : m) {
std::cout << p.first << " -> " << p.second << std::endl;
}
返回多个值：在函数中返回多个值时，pair 可以作为一个简单的解决方案。
std::pair<int, std::string> getData() {
return std::make_pair(1, "Result");
}
双指针优化：
排序：首先对 a 和 b 进行排序，这样我们可以通过双指针优化来减少比较次数。
双指针逻辑：
i 和 j 分别指向 a 和 b 的当前元素。
计算 a[i] 和 b[j] 的绝对差 diff，并更新最小差值 minDiff。
如果当前差值小于 minDiff，则更新 minDiff 并清空结果列表 ans，然后加入当前对。
如果差值相等，直接将当前对加入 ans。
根据 a[i] 和 b[j] 的大小关系，移动指针 i 或 j。如果 a[i] 小于 b[j]，则移动 i，否则移动 j。
输出：最终输出最小差值以及所有具有该差值的整数对。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
vector<int> a = {2, 8, 7, 5, 11};
vector<int> b = {22, 15, 12, 31, 3};
// 对两个向量进行排序
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int an = a.size(), bn = b.size();
vector<pair<int, int>> ans;
int i = 0, j = 0, minDiff = INT_MAX;
// 双指针遍历
while(i < an && j < bn) {
int diff = abs(a[i] - b[j]);
// 更新最小差值和结果
if(diff < minDiff) {
minDiff = diff;
ans.clear();
ans.push_back({a[i], b[j]});
} else if(diff == minDiff) {
ans.push_back({a[i], b[j]});
}
// 移动指针
if(a[i] < b[j]) {
i++;
} else {
j++;
}
}
// 输出最小差值
cout << minDiff << endl;
for(const auto& p : ans) {
cout << "[" << p.first << " , " << p.second << "]" << endl;
}
return 0;
}
面试题
给定两个整数数组 a 和 b，找出所有数对 (a[i], b[j])，使得 |a[i] - b[j]| 的差值最小，并输出这些数对以及最小差值。
#include<iostream>
#include<vector>
using namespace std;
int main(){
vector<int> a = {2,8,7,5,11};
vector<int> b = {22,15,12,31,3};
int an = a.size(),bn = b.size();
vector<pair<int,int>> ans;
int c,min = INT_MAX;
for(int i = 0; i < an; i++){
for(int j = 0;j < bn; j++){
c = abs(a[i] - b[j]);
if(c < min){
min = c;
ans.clear();
ans.push_back({a[i], b[j]});
} else if(c == min){
ans.push_back({a[i], b[j]});
}
}
}
cout << min << endl;
for(int i = 0; i < ans.size(); i++){
cout << "[" <<ans[i].first <<" ," << ans[i].second << "]" << endl;
}
return 0;
}
关于map
在 C++ 中，std::map 是一个关联容器，它存储的是一组键值对，并且根据键值进行排序。每个键值对是一个 pair 对象，其中第一个元素是键，第二个元素是对应的值。std::map 会自动根据键进行排序，默认情况下是按照升序排列。
#include <iostream>
#include <map>
#include <string>
int main() {
// 创建一个map
std::map<int, std::string> m;
// 插入元素
m.insert({1, "Apple"});
m.insert({2, "Banana"});
m[3] = "Cherry"; // 使用 [] 操作符插入
// 修改值
m[2] = "Blueberry";
// 查找元素
if (m.find(1) != m.end()) {
std::cout << "Found key 1: " << m[1] << std::endl;
}
// 遍历map
for (const auto& kv : m) {
std::cout << kv.first << " -> " << kv.second << std::endl;
}
// 删除元素
m.erase(2);
// 输出map大小
std::cout << "Map size: " << m.size() << std::endl;
return 0;
}
tuple
std::tuple 是 C++ 标准库中的一个容器类型，它允许存储多个异构类型的元素。与数组和 std::vector 等容器不同，std::tuple 允许存储不同类型的数据，且可以存储任意数量的元素。std::tuple 是一个模板类，支持与 C++ 中的其他容器一起使用，并具有强大的访问和操作功能。
#include <iostream>
#include <tuple>
int main() {
// 创建一个包含不同类型元素的tuple
std::tuple<int, double, std::string> t(1, 3.14, "Hello");
std::cout << "First: " << std::get<0>(t) << std::endl; // 输出: First: 1
std::cout << "Second: " << std::get<1>(t) << std::endl; // 输出: Second: 3.14
std::cout << "Third: " << std::get<2>(t) << std::endl; // 输出: Third: Hello
return 0;
}
解包
std::tuple<int, double, std::string> t(1, 3.14, "Hello");
// 使用结构化绑定解包tuple
auto [x, y, z] = t;
std::cout << x << ", " << y << ", " << z << std::endl; // 输出: 1, 3.14, Hello
合并
std::tuple<int, double> t1(1, 3.14);
std::tuple<std::string, char> t2("Hello", 'A');
auto t3 = std::tuple_cat(t1, t2);
std::cout << std::get<0>(t3) << ", " << std::get<1>(t3) << ", " << std::get<2>(t3) << ", " << std::get<3>(t3) << std::endl;
解构
std::tuple<int, double, std::string> t(1, 3.14, "Hello");
int x;
double y;
std::string z;
std::tie(x, y, z) = t;
std::cout << x << ", " << y << ", " << z << std::endl; // 输出: 1, 3.14, Hello