C++刷题常用方法

C++ 中 Map 的自定义排序方法

在 C++ 中，std::map 和 std::unordered_map 是两种主要的关联容器。std::map 本身是有序的（默认按 key 升序），但我们可以通过自定义比较器来实现不同的排序方式。

1. 使用 Lambda 表达式作为比较器 (C++14及以上)

#include <iostream>
#include <map>
#include <string>int main() {// 使用lambda表达式作为比较器auto compare = [](const std::string& a, const std::string& b) {// 按字符串长度降序排序，长度相同则按字典序升序if (a.length() != b.length()) {return a.length() > b.length();}return a < b;};std::map<std::string, int, decltype(compare)> myMap(compare);myMap["apple"] = 10;myMap["banana"] = 5;myMap["orange"] = 8;myMap["kiwi"] = 3;myMap["pear"] = 4;  // 与"kiwi"长度相同for (const auto& pair : myMap) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}

在 C++ 中，当你使用自定义比较器（如 lambda 表达式）来创建 std::map 时，myMap(compare); 这一行代码非常重要，原因如下：

1. 比较器对象的传递

std::map 的模板参数只声明了比较器的类型（通过 decltype(compare)），但并没有提供实际的比较器对象。构造函数需要接收这个比较器对象的实例。

2. Lambda 表达式的特殊性

Lambda 表达式在 C++ 中是一个匿名函数对象，每个 lambda 都有独特的类型。当你使用 decltype(compare) 作为模板参数时，你只是指定了比较器的类型，但 map 仍然需要一个实际的比较器实例来使用。

在 C++ 中，lambda 表达式不能直接用作模板参数，因为每个 lambda 都有独特的匿名类型，无法在模板参数中直接指定。

2. 使用自定义比较函数对 std::map 排序 

#include <iostream>
#include <map>
#include <string>// 自定义比较函数
struct CustomCompare {bool operator()(const std::string& a, const std::string& b) const {// 按字符串长度排序，长度相同则按字典序if (a.length() != b.length()) {return a.length() < b.length();}return a < b;}
};int main() {// 使用自定义比较器的mapstd::map<std::string, int, CustomCompare> myMap;myMap["apple"] = 10;myMap["banana"] = 5;myMap["orange"] = 8;myMap["kiwi"] = 3;// 输出结果将按字符串长度排序for (const auto& pair : myMap) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}

decltype 在 C++ 中的使用详解

decltype 是 C++11 引入的关键字，用于查询表达式的类型。它在模板编程、自动类型推导和复杂类型声明中非常有用。

基本用法

1. 基本类型推导

cpp

int x = 10;
decltype(x) y = 20;  // y的类型是intdouble foo();
decltype(foo()) z = 3.14;  // z的类型是double

2. 与变量一起使用

cpp

const int& rx = x;
decltype(rx) ry = y;  // ry的类型是const int&

在模板编程中的应用

1. 函数返回类型推导

cpp

template<typename T, typename U>
auto add(T t, U u) -> decltype(t + u) {return t + u;
}

2. 元编程中的类型查询

cpp

template<typename T>
void print_type() {std::cout << typeid(decltype(T())).name() << std::endl;
}

与 lambda 表达式结合

1. 获取 lambda 类型

cpp

auto lambda = [](int x) { return x * 2; };
decltype(lambda) copy = lambda;  // 复制lambda对象

2. 在 STL 容器中使用（如 std::map）

cpp

auto comp = [](const std::string& a, const std::string& b) {return a.length() < b.length();
};
std::map<std::string, int, decltype(comp)> length_map(comp);

decltype 的特殊规则

1. 对于变量名：decltype(var) 给出变量的声明类型

   cpp

   int i = 0;
   decltype(i) j;  // j是int类型

2. 对于表达式：decltype(expr) 考虑表达式的值类别

   • 如果表达式是左值，结果为T&

   • 如果表达式是右值，结果为T

   • 如果表达式是将亡值，结果为T&&

   cpp

   int&& foo();
   decltype(foo()) x;  // x是int&&

decltype(auto) (C++14)

结合了auto和decltype的特性：

cpp

int x = 10;
int& get_ref() { return x; }decltype(auto) y = get_ref();  // y是int&
auto z = get_ref();            // z是int（会丢失引用）

实际应用示例

1. 完美转发返回值

cpp

template<typename F, typename... Args>
decltype(auto) call(F f, Args&&... args) {return f(std::forward<Args>(args)...);
}

2. 类型安全的宏替代

cpp

#define DECLTYPE(expr) decltype(expr)
int x = 42;
DECLTYPE(x) y = 10;  // y是int

3. 复杂表达式类型推导

cpp

std::vector<int> v = {1, 2, 3};
decltype(v.begin()) it = v.begin();  // it的类型是std::vector<int>::iterator

注意事项

1. decltype 在编译时求值，不会实际计算表达式

2. 对于重载函数，需要明确指定哪个重载版本

3. 在模板中使用时要注意依赖类型的问题（可能需要typename）

4. 与auto不同，decltype会保留引用和const限定符

decltype 是C++类型系统中强大的工具，特别适合在需要精确控制类型推导的场合使用。

C++ sort 函数使用方法详解

sort 是 C++ 标准库 <algorithm> 中提供的排序函数，用于对容器中的元素进行排序。下面详细介绍其使用方法。

基本用法

1. 对数组排序

cpp

#include <algorithm>
#include <iostream>int main() {int arr[] = {4, 2, 5, 1, 3};int n = sizeof(arr)/sizeof(arr[0]);std::sort(arr, arr + n);  // 升序排序for (int i = 0; i < n; ++i) {std::cout << arr[i] << " ";}// 输出: 1 2 3 4 5return 0;
}

2. 对vector排序

cpp

#include <algorithm>
#include <vector>
#include <iostream>int main() {std::vector<int> vec = {4, 2, 5, 1, 3};std::sort(vec.begin(), vec.end());  // 升序排序for (int num : vec) {std::cout << num << " ";}// 输出: 1 2 3 4 5return 0;
}

自定义排序

1. 使用函数指针

cpp

bool compare(int a, int b) {return a > b;  // 降序排序
}int main() {std::vector<int> vec = {4, 2, 5, 1, 3};std::sort(vec.begin(), vec.end(), compare);// 结果: 5 4 3 2 1return 0;
}

2. 使用函数对象(Functor)

cpp

struct {bool operator()(int a, int b) const {return a > b;  // 降序排序}
} compare;int main() {std::vector<int> vec = {4, 2, 5, 1, 3};std::sort(vec.begin(), vec.end(), compare);// 结果: 5 4 3 2 1return 0;
}

3. 使用lambda表达式(C++11起)

cpp

int main() {std::vector<int> vec = {4, 2, 5, 1, 3};// 降序排序std::sort(vec.begin(), vec.end(), [](int a, int b) {return a > b;});// 结果: 5 4 3 2 1// 按绝对值排序std::sort(vec.begin(), vec.end(), [](int a, int b) {return abs(a) < abs(b);});return 0;
}

对自定义类型排序

1. 重载小于运算符

cpp

struct Person {std::string name;int age;// 重载<运算符，按年龄升序bool operator<(const Person& other) const {return age < other.age;}
};int main() {std::vector<Person> people = {{"Alice", 25}, {"Bob", 20}, {"Charlie", 30}};std::sort(people.begin(), people.end());// 按年龄升序排序return 0;
}

2. 使用自定义比较函数

cpp

struct Person {std::string name;int age;
};bool compareByName(const Person& a, const Person& b) {return a.name < b.name;  // 按名字字典序排序
}int main() {std::vector<Person> people = {{"Alice", 25}, {"Bob", 20}, {"Charlie", 30}};std::sort(people.begin(), people.end(), compareByName);// 按名字排序return 0;
}

stable_sort 保持相等元素的原始顺序：

第一种方式：匿名结构体 + 立即定义对象

cpp

struct {bool operator()(int a, int b) const {return a > b;  // 降序排序}
} compare;  // 同时定义了一个名为compare的对象

特点：

1. 定义了一个匿名结构体类型（没有类型名）

2. 立即创建了该类型的一个对象 compare

3. 只能通过这个预先创建的 compare 对象来使用

4. 不能在其他地方创建这个类型的其他对象（因为没有类型名）

5. 典型用法：

   cpp

   std::sort(vec.begin(), vec.end(), compare);

第二种方式：具名结构体

cpp

struct compare {  // 定义了一个名为compare的结构体类型bool operator()(int a, int b) const {return a > b;  // 降序排序}
};  // 注意这里没有立即创建对象

特点：

1. 定义了一个名为 compare 的结构体类型

2. 没有立即创建对象，只是一个类型定义

3. 可以随时创建多个该类型的对象：

   cpp

   compare comp1;  // 创建第一个比较器对象
   compare comp2;  // 创建第二个比较器对象

4. 典型用法：

   cpp

   std::sort(vec.begin(), vec.end(), compare());  // 临时创建匿名对象
   // 或者
   compare myComp;
   std::sort(vec.begin(), vec.end(), myComp);

关键区别对比