类型推断
主要包括auto, decltype, 模板类型推断几种
auto 关键字
auto是C++11引入的关键字，允许编译器根据右侧的表达式自动推断变量的类型。通过使用auto，我们可以避免显式地写出复杂的类型定义，编译器会根据表达式的类型来推断。
特点：
- auto只能用于声明和定义，不能用作函数的参数类型。
- 编译器根据初始化的表达式推断类型。
auto 推导规则的特殊情况
- 指针和引用：如果初始值是指针或引用，auto会保留它们的类型。
- 数组与函数指针：auto不会直接推断为数组类型或函数类型，而是推断为指针。
#include <iostream>
int main() {
int x = 42;
int& ref = x;
auto a = ref; // a是int类型，而不是int&类型
a = 100;
std::cout << "x: " << x << ", a: " << a << std::endl; // 输出 x: 42, a: 100
return 0;
}
推断返回类型
#include <iostream>
#include <type_traits>
template <typename T1, typename T2>
auto add(T1 a, T2 b) -> decltype(a + b) {
return a + b;
}
int main() {
int x = 5;
double y = 10.5;
// 返回类型被推断为 decltype(x + y)，即 double
auto result = add(x, y);
std::cout << "Result: " << result << std::endl; // 输出 15.5
}
C++14引入了一种新特性，即允许在函数返回值处使用auto，编译器会根据函数体中的返回语句自动推断返回类型。这对模板函数尤其有用，可以避免显式地指定返回类型。
#include <iostream>
auto add(int x, int y) {
return x + y; // 编译器推断返回类型为int
}
int main() {
auto result = add(5, 3);
std::cout << "Result: " << result << std::endl; // 输出Result: 8
return 0;
}
C++17引入了结构化绑定，使得可以将多个值的返回结果通过auto绑定到多个变量中。这对于返回std::pair或std::tuple的函数特别有用。
#include <iostream>
#include <tuple>
std::tuple<int, double, std::string> getValues() {
return {42, 3.14, "Hello"};
}
int main() {
auto [x, y, z] = getValues(); // 结构化绑定
std::cout << "x: " << x << ", y: " << y << ", z: " << z << std::endl; // 输出 x: 42, y: 3.14, z: Hello
return 0;
}
decltype 关键字
decltype也是C++11引入的，用于推断表达式的类型，但与auto不同，decltype不会对表达式进行求值，它只会根据表达式的类型来推断变量类型。
特点：
- decltype可以用于任何表达式，推断该表达式的类型。
- 在复杂场景下可以用来获取某个变量或表达式的精确类型。
#include <iostream>
int main() {
int a = 5;
decltype(a) b = a * 2; // 推断b的类型为int
decltype((a)) c = a; // 推断为int&（左值引用）
std::cout << "a: " << a << ", b: " << b << ", c: " << c << std::endl;
int x = 42;
double y = 3.14;
// 使用decltype推断表达式的类型，auto用于变量声明
decltype(x + y) result = x + y; // 推断为double
return 0;
}
模板类型推断
模板类型推断是C++的核心特性之一，允许编译器自动根据传入的模板参数推断类型。
#include <iostream>
template<typename T>
void printType(T x) {
std::cout << "Type: " << typeid(x).name() << ", Value: " << x << std::endl;
}
int main() {
printType(42); // 推断T为int
printType(3.14); // 推断T为double
printType("Hello"); // 推断T为const char*
return 0;
}
在C++11及以后，auto和decltype与模板结合使用，进一步简化了模板编程。
initializer_list
std::initializer_list 允许通过 {} 语法进行列表初始化。它常用于构造函数、函数参数，尤其适合简洁地传递一组值。常见的 C++ 标准容器和自定义类(构造函数接受 std::initializer_list 作为参数的自定义类。)都可以通过 std::initializer_list 支持列表初始化。
std::initializer_list 的限制：
- 只读性：std::initializer_list 内的元素是常量，不能被修改。如果需要可修改的列表，可以考虑使用其他容器（如 std::vector）。
- 不支持动态大小：std::initializer_list 是不可变的，一旦创建，大小固定。
std::initializer_list 是一个轻量级的类模板，通常由两个指针组成：一个指向元素数组的指针，元素数量的计数。这使得它非常高效，因为它只是持有指向数据的指针，并没有进行额外的拷贝或内存管理。元素可以通过迭代器访问。在编译时能够推导出类型。
template<class T>
class initializer_list {
public:
// 返回指向数组的指针
const T* begin() const noexcept { return _array; }
// 返回数组末尾
const T* end() const noexcept { return _array + _size; }
// 返回元素个数
size_t size() const noexcept { return _size; }
private:
const T* _array;
size_t _size;
};
自定义类使用 std::initializer_list 构造函数
#include <iostream>
#include <initializer_list>
class MyClass {
public:
std::initializer_list<int> values;
MyClass(std::initializer_list<int> list): values(list) {
for (int value : list) {
std::cout << "Initializing with value: " << value << std::endl;
}
}
void printValues() const {
for (int value : values) {
std::cout << value << " ";
}
std::cout << std::endl;
}
};
int main() {
MyClass obj = {5, 10, 15, 20}; // 使用std::initializer_list初始化
obj.printValues(); // 输出 5 10 15 20
return 0;
}
STL
C++中的STL（标准模板库）是编程中非常重要的一个部分，STL不仅提供了丰富的数据结构和算法，同时也是泛型编程的重要应用。
选择合适的STL容器通常取决于你对数据结构的需求，如访问速度、插入/删除操作的频率、内存使用等。以下是一些常见的选择标准：
- std::vector：当你需要频繁随机访问元素，且只在末尾插入/删除时。
- push_back(const T& value)：在末尾添加元素。
- pop_back()：移除末尾元素。
- size()：返回当前元素个数。
- capacity()：返回当前分配的内存大小（可以容纳多少元素）。
- reserve(size_t n)：预留至少 n 个元素的存储空间。
- resize(size_t n)：改变容器大小，增加的部分会默认初始化。
- at(size_t index)：访问指定索引处的元素，并进行范围检查。
- operator[]：通过索引访问元素，不进行范围检查。
- front()：返回第一个元素。
- back()：返回最后一个元素。
- clear()：清空所有元素。
- insert(iterator pos, const T& value)：在指定位置插入元素。
- erase(iterator pos)：移除指定位置的元素。
- emplace_back(args...)：原地构造元素并添加到末尾。
- std::deque：一个双端队列，支持在两端进行快速插入和删除。
- push_back(const T& value)：在末尾添加元素。
- push_front(const T& value)：在开头添加元素。
- pop_back()：移除末尾元素。
- pop_front()：移除开头元素。
- size()：返回当前元素个数。
- at(size_t index)：访问指定索引处的元素，并进行范围检查。
- operator[]：通过索引访问元素，不进行范围检查。
- front()：返回第一个元素。
- back()：返回最后一个元素。
- clear()：清空所有元素。
- insert(iterator pos, const T& value)：在指定位置插入元素。
- erase(iterator pos)：移除指定位置的元素。
- std::array：固定大小数组
- std::forward_list：单向链表
- std::list：双向链表，支持高效的插入和删除操作，尤其是在中间或两端。
- push_back(const T& value)：在末尾添加元素。
- push_front(const T& value)：在开头添加元素。
- pop_back()：移除末尾元素。
- pop_front()：移除开头元素。
- size()：返回当前元素个数。
- empty()：检查容器是否为空。
- front()：返回第一个元素。
- back()：返回最后一个元素。
- insert(iterator pos, const T& value)：在指定位置插入元素。
- erase(iterator pos)：移除指定位置的元素。
- remove(const T& value)：移除所有等于 value 的元素。
- sort()：对列表进行排序。
- reverse()：将列表元素顺序反转。
- std::set：是一个不允许重复元素的有序集合，基于红黑树实现。
- insert(const T& value)：插入元素，元素会自动排序。
- erase(const T& value)：移除指定元素。
- size()：返回当前元素个数。
- empty()：检查容器是否为空。
- find(const T& value)：查找元素，返回指向该元素的迭代器。
- count(const T& value)：检查是否包含某个元素（返回 1 或 0）。
- clear()：清空所有元素。
- begin()：返回指向第一个元素的迭代器。
- end()：返回指向最后一个元素之后的迭代器。
- std::unordered_set: 一种基于哈希表实现的容器，用于存储唯一的无序元素。通过哈希表实现常数时间复杂度的插入、删除和查找操作。
- insert(const T& value)：向集合中插入元素。如果元素已存在，则不会插入新的值。
- erase(const T& value)：从集合中移除等于 value 的元素，若不存在该元素则不做任何操作。
- clear()：清空集合中的所有元素。
- find(const T& value)：查找元素，返回指向该元素的迭代器，如果未找到则返回 end() 迭代器。
- count(const T& value)：检查集合中是否包含元素 value，如果包含则返回 1，否则返回 0。
- size()：返回集合中的元素个数。
- empty()：检查集合是否为空。
- begin()：返回指向第一个元素的迭代器。
- end()：返回指向容器末尾的迭代器（最后一个元素的下一个位置）。
- cbegin() 和 cend()：返回常量迭代器，保证迭代时集合内容不可修改。
- bucket_count()：返回当前哈希表中桶（bucket）的数量。
- max_bucket_count()：返回容器可能包含的最大桶数。
- load_factor()：返回当前哈希表的装载因子，即元素数量与桶数量的比值。
- rehash(size_t n)：重组容器，使其至少有 n 个桶。
- reserve(size_t n)：预留足够空间以容纳至少 n 个元素，并减少重哈希操作的次数。
- std::multiset
- std::unordered_multiset
- std::multimap：允许存在重复的键，即相同的键可以关联多个值，一对多的关系。使用 find() 方法查找某个键时，只能返回第一个找到的键值对。如果需要找到该键对应的所有值，可以使用 equal_range() 或者 lower_bound() 和 upper_bound() 组合使用来获取一个范围。
- std::unordered_multimap
- std::map： 是一个基于键值对的有序关联容器，键是唯一的，一对一的关系。
insert(const std::pair<K, V>& value)：插入键值对。- erase(const K& key)：通过键删除元素。
- size()：返回当前元素个数。
- empty()：检查容器是否为空。
- find(const K& key)：查找键值对，返回指向该元素的迭代器。
- count(const K& key)：检查是否包含某个键。
- clear()：清空所有元素。
- operator[]：通过键访问或插入元素。
- std::unordered_map: 是一个基于哈希表实现的映射，键是唯一的，且不保证顺序。
insert(const std::pair<K, V>& value)：插入键值对。- erase(const K& key)：通过键删除元素。`
- size()：返回当前元素个数。
- empty()：检查容器是否为空。
- find(const K& key)：查找键值对，返回指向该元素的迭代器。
- count(const K& key)：检查是否包含某个键。
- clear()：清空所有元素。
- operator[]：通过键访问或插入元素。
- std::stack: 适合后进先出 (LIFO) 的数据结构。
- push(const T& value)：将元素压入栈顶。
- pop()：移除栈顶元素。
- top()：返回栈顶元素。
- size()：返回当前元素个数。
- empty()：检查容器是否为空。
- std::queue: 一种适合先进先出 (FIFO) 的数据结构
- push(const T& value)：将元素添加到队尾。
- pop()：移除队首元素。
- front()：返回队首元素。
- back()：返回队尾元素。
- size()：返回当前元素个数。
- empty()：检查容器是否为空。
- std::priority_queue, 是一种元素具有优先级的队列，默认情况下，最大元素会在队首。
- push(const T& value)：将元素插入队列。
- pop()：移除优先级最高的元素。
- top()：返回优先级最高的元素。
- size()：返回当前元素个数。
- empty()：检查容器是否为空。
STL容器本身不是线程安全的。多个线程同时读写同一个容器，或者同时修改容器状态（比如插入或删除元素）时，可能会导致数据竞争。因此，需要通过锁（如std::mutex）来确保线程安全。
STL广泛采用了泛型编程，所有STL容器和算法都使用模板，使它们能够处理不同的数据类型。
#include <iostream>
#include <vector>
template <typename T>
void print_vector(const std::vector<T>& vec) {
for (const auto& item : vec) {
std::cout << item << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> int_vec = {1, 2, 3};
std::vector<double> double_vec = {1.1, 2.2, 3.3};
print_vector(int_vec);
print_vector(double_vec);
return 0;
}
RAII
STL中，像std::vector、std::unique_ptr等容器和智能指针都遵循RAII原则。RAII（Resource Acquisition Is Initialization）是一种资源管理的原则。在C++中，RAII意味着对象的生命周期与资源的管理直接相关。当对象被创建时，资源被分配；当对象被销毁时，资源自动释放。
#include <iostream>
#include <vector>
int main() {
{
std::vector<int> vec = {1, 2, 3};
// vec创建时分配内存，RAII管理其生命周期
}
// 离开作用域时，vec自动销毁，内存被释放
return 0;
}
allocator
Allocator是STL中用于管理内存分配的机制。STL中的所有容器都使用allocator来控制如何分配、释放和管理内存。这使得STL能够更灵活地适应不同的内存管理需求。
默认的allocator是std::allocator，但用户可以自定义allocator来优化内存分配策略（比如用于嵌入式系统中的内存池）。
#include <iostream>
#include <vector>
#include <memory>
int main() {
std::vector<int, std::allocator<int>> vec = {1, 2, 3};
return 0;
}
STL中的优先级队列是如何实现的？
STL中的priority_queue是基于堆（heap）实现的。优先级队列默认是一个最大堆，即每次取出的元素都是当前队列中的最大值（或最小值，取决于定义）。堆的性质确保插入和删除的时间复杂度为O(log n)。
代码示例：
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int> pq;
pq.push(10);
pq.push(5);
pq.push(20);
while (!pq.empty()) {
std::cout << pq.top() << " "; // 每次输出最大值
pq.pop();
}
return 0;
}
这里，std::priority_queue是通过std::vector存储数据，并使用堆来维持顺序。内部使用std::make_heap()、std::push_heap()和std::pop_heap()等算法。
STL中常见的算法库
STL中的算法库是其核心部分之一，包含了很多常见的算法，比如排序、查找、遍历等。以下是一些常见的算法：
- std::sort：快速排序，时间复杂度为O(n log n)。
- std::find：在范围内查找某个元素，线性时间复杂度。
- std::binary_search：二分查找，时间复杂度为O(log n)，需要排序数组。
- std::accumulate：用于计算区间内所有元素的累加值。
代码示例：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {1, 3, 5, 2, 4};
// 排序
std::sort(vec.begin(), vec.end());
// 查找
if (std::binary_search(vec.begin(), vec.end(), 3)) {
std::cout << "找到元素3" << std::endl;
}
return 0;
}
map的底层实现
std::map的底层实现是红黑树，这是一种自平衡二叉搜索树。红黑树保证插入、删除、查找的时间复杂度为O(log n)。红黑树通过颜色标记和旋转操作保持平衡。
set的底层实现
std::set的底层实现与std::map类似，也是基于红黑树。区别在于std::set只存储键，而不存储值。