STL_容器适配器：stack记录-Aet

Bingliaolong 2025-11-04 14:35 Aet | 隐藏边栏 | 抢沙发 | 7 0

文章评分 2 次，平均分 5.0 ：

概述

首先，stack是一个容器适配器
理论上，任何提供了 push_back(), pop_back(), back()等操作的序列容器都可以作为 stack的底层容器

为什么默认是`deque`

deque之所以成为默认选择，是因为它在以下几个方面取得了最佳平衡：
相对于vector
1. deque的主要优势在于高效且低成本的动态扩容
2. vector在尾部空间不足时，需要申请一块更大的内存，然后将所有元素整体搬迁过去，这个操作的时间复杂度是 O(n)
3. deque采用分段连续的结构，只需要新增一个内存块（buffer）并将其指针添加到中控器（map）中即可，开销要小得多
相对于list
1. deque的主要优势在于更高的内存利用率和缓存友好性
2. list的每个元素都存储在两个指针（前驱和后继），内存开销较大，且节点在内存中不连续，容易造成内存碎片，CPU缓存命中率较低
3. deque的元素存储在连续的内存块中，虽然块与块之间不连续，但块内是连续的，这在保证高效操作的同时，提供了更好的内存局部性

灵活性：其他容器

尽管 deque是默认选择，但STL的适配器设计给予了充分的灵活性

#include <stack>

#include <vector>

#include <list>

// 如果你需要极致的遍历速度，且栈大小相对固定，可以考虑vector

std::stack<int, std::vector<int>> stack_using_vector;

// 如果你需要频繁地在栈的中间进行插入删除（这其实比较少见，不符合栈的典型用法），可以考虑list

std::stack<int, std::list<int>> stack_using_list;

`stack`

设计

_EXPORT_STD template <class _Ty, class _Container = deque<_Ty>>

class stack {

public:

// 类型

static_assert(is_same_v<_Ty, value_type>, "container adaptors require consistent types");

static_assert(is_object_v<_Ty>, "The C++ Standard forbids container adaptors of non-object types "

"because of [container.requirements].");

// 不同版本构造

// empty 使用_Container功能

// size 使用_Container功能

// top 使用_Container功能

// push 使用_Container功能

// emplace 使用_Container功能

// pop 使用_Container功能

// swap 使用std::swap

protected:

_Container c{};

};

// C++17 类型推导指引

// C++23 类型推导指引

// 一些操作符处理

类型推导指引

上述cpp17推导指引1
1. _Is_allocator<_Container>::value用于判断类型_Container是否为分配器（Allocator）
2. !_Is_allocator<_Container>::value表示：只有当_Container不是分配器类型时，这个推导指引才参与重载决议，有效
  为了避免混淆：用一个分配器对象来构造一个栈，还是想用这个分配器作为底层容器
  此约束明确排除了后一种情况
3. -> stack<typename _Container::value_type, _Container>
  推导结果：
  告诉编译器：如果使用一个类型为_Container的对象来构造stack，那么最终stack的模板参数应该被推导为stack<typename _Container::value_type, _Container>
  typename _Container::value_type表示从传入的容器类型中提取其元素类型，作为stack的元素类型

#if _HAS_CXX17

template <class _Container, enable_if_t<!_Is_allocator<_Container>::value, int> = 0>

stack(_Container) -> stack<typename _Container::value_type, _Container>;

#endif // _HAS_CXX17

上述cpp17推导指引2
1. 这个指引用于处理同时传入容器和分配器对象的情况（例如，一个使用自定义分配器的容器）
2. negation<_Is_allocator<_Container>>：确保第一个参数（_Container）不是分配器类型。这和第一个指引中的约束目的相同
3. uses_allocator<_Container, _Alloc>：这是一个关键的检查，它判断提供的容器类型_Container是否能够使用提供的分配器类型_Alloc。这确保了容器与分配器是兼容的
4. 只有同时满足这两个条件，该推导指引才有效
5. 推导结果与第一个指引相同：stack<typename _Container::value_type, _Container>
  分配器类型_Alloc已经被包含在容器的类型之中（例如，std::vector<int, MyAlloc>本身就包含了分配器信息）

// C++17 之前

std::vector<int, MyAllocator> my_vec;

std::stack<int, std::vector<int, MyAllocator>> my_stack(my_vec); // 需要完整写出类型

// C++17 之后

std::vector<int, MyAllocator> my_vec;

std::stack my_stack(my_vec); // 编译器自动推导为 stack<int, vector<int, MyAllocator>>

std::stack my_stack2(my_vec, my_allocator); // 使用第二个推导指引

#if _HAS_CXX17

template <class _Container, class _Alloc,

enable_if_t<conjunction_v<negation<_Is_allocator<_Container>>, uses_allocator<_Container, _Alloc>>, int> = 0>

stack(_Container, _Alloc) -> stack<typename _Container::value_type, _Container>;

#endif // _HAS_CXX17

上述cpp23推导指引1

#if _HAS_CXX23

template <_Iterator_for_container _InIt, _Allocator_for_container _Alloc = allocator<_Iter_value_t<_InIt>>>

stack(_InIt, _InIt, _Alloc = _Alloc()) -> stack<_Iter_value_t<_InIt>, deque<_Iter_value_t<_InIt>, _Alloc>>;

#endif // _HAS_CXX23

上述cpp23推导指引2

#if _HAS_CXX23

template <_RANGES input_range _Rng>

stack(from_range_t, _Rng&&) -> stack<_RANGES range_value_t<_Rng>>;

#endif // _HAS_CXX23

上述cpp23推导指引3

#if _HAS_CXX23

template <_RANGES input_range _Rng, _Allocator_for_container _Alloc>

stack(from_range_t, _Rng&&, _Alloc) -> stack<_RANGES range_value_t<_Rng>, deque<_RANGES range_value_t<_Rng>, _Alloc>>;

#endif // _HAS_CXX23

其他

`enable_if`

enable_if

`negation`

cpp17对类型特性的布尔值 ::value进行逻辑非运算
std::bool_constant是一个辅助模板，它根据表达式 !bool(B::value)的结果，提供一个 static constexpr bool成员 value
1. 如果 B::value为 true，则 negation<B>::value为 false，反之亦然

1 2	template<class B> struct negation : std::bool_constant<!bool(B::value)> { };

`conjunction`

cpp17对多个类型特征的 ::value进行逻辑与运算
等价：T1::value && T2::value && ... && Tn::value
短路特性：一旦某个 Ti::value为 false，便停止实例化后续类型特征
空参数包：std::conjunction_v<>结果为 true

// 基础案例：空参数包，结果为 true

template<class...>

struct conjunction : std::true_type {};

// 递归案例：只有一个类型时，直接继承该类型

template<class B1>

struct conjunction<B1> : B1 {};

// 递归案例：多个类型时，通过 std::conditional_t 进行短路判断

template<class B1, class... Bn>

struct conjunction<B1, Bn...>

: std::conditional_t<bool(B1::value), conjunction<Bn...>, B1> {};

template<class... B>

constexpr bool conjunction_v = conjunction<B...>::value;

`is_same`

is_same

`is_object`

cpp11用于在编译时判断一个类型是否属于对象类型
1. 简单来说，它的核心逻辑是：只要一个类型不是函数、不是引用、也不是 void，那么它就是一个对象类型

template<typename T>

void process() {

static_assert(std::is_object_v<T>, "T must be an object type.");

// ... 你的代码逻辑

}

class MyClass {};

int main() {

process<int>(); // 通过：int 是对象类型

process<MyClass>(); // 通过：MyClass 是对象类型

// process<int&>(); // 编译错误：int& 是引用类型，不是对象类型

return 0;

}

`is_empty`

cpp11引入，用于判断一个类类型是否为空类（empty class）
1. 简单来说，它在编译时告诉你一个类是否不占用任何非静态数据成员存储空间
一个类类型要被 std::is_empty_v判定为 true，必须同时满足以下严格条件
1. 非联合体的类类型：必须是 class或 struct，但不能是 union
2. 无非静态数据成员：类中不能有任何非静态成员变量（静态数据成员是允许的）
3. 无虚函数：类中不能声明或继承虚函数（即没有虚函数表）
4. 无虚基类：在继承体系中，不能有虚继承（即没有虚基类表）
5. 无非空基类：所有直接基类本身也必须都是空类

#include <iostream>

#include <type_traits>

struct EmptyStruct {}; // 空结构体

struct NonEmpty {

int data; // 有非静态数据成员

};

struct WithVirtual {

virtual ~WithVirtual() {} // 有虚函数

};

int main() {

std::cout << std::boolalpha;

std::cout << "std::is_empty_v<EmptyStruct>: " << std::is_empty_v<EmptyStruct> << std::endl; // 输出 true

std::cout << "std::is_empty_v<NonEmpty>: " << std::is_empty_v<NonEmpty> << std::endl; // 输出 false

std::cout << "std::is_empty_v<WithVirtual>: " << std::is_empty_v<WithVirtual> << std::endl; // 输出 false

std::cout << "std::is_empty_v<int>: " << std::is_empty_v<int> << std::endl; // 输出 false (非类类型)

return 0;

}

`is_final`

cpp14引入，用于在编译时判断一个类型是否被声明为 final
1. 如果类型 T是一个被 final修饰的类类型（包括结构体），则 std::is_final_v<T>的值为 true，否则为 false

template<typename Base>

class MyDerived : public Base { // 希望 Base 不是 final 的

static_assert(!std::is_final_v<Base>, "Base class must not be final.");

// ... 其他实现

};

空基类优化

class _Compressed_pair final : private _Ty1 { // 私有继承空基类

public:

_Ty2 _Myval2; // 直接存储第二个值

...

constexpr _Ty1& _Get_first() noexcept {

return *this; // 通过this指针获取基类部分

}

template <class _Ty1, class _Ty2>

class _Compressed_pair<_Ty1, _Ty2, false> final { // 存储两个成员变量

public:

_Ty1 _Myval1; // 显式存储第一个值

_Ty2 _Myval2;

...

constexpr _Ty1& _Get_first() noexcept {

return _Myval1; // 返回成员变量 _Myval1

}

标签分发

使用标签类型来区分不同的构造方式
1. _Zero_then_variadic_args_t：默认构造 _Ty1，然后使用参数构造 _Ty2
2. _One_then_variadic_args_t：使用第一个参数构造 _Ty1，剩余参数构造 _Ty2

template <class _Ty1, class _Ty2, bool = is_empty_v<_Ty1> && !is_final_v<_Ty1>>

class _Compressed_pair final : private _Ty1 { // store a pair of values, deriving from empty first

public:

_Ty2 _Myval2;

using _Mybase = _Ty1; // for visualization

template <class... _Other2>

constexpr explicit _Compressed_pair(_Zero_then_variadic_args_t, _Other2&&... _Val2)

noexcept(conjunction_v<is_nothrow_default_constructible<_Ty1>, is_nothrow_constructible<_Ty2, _Other2...>>)

: _Ty1(), _Myval2(_STD forward<_Other2>(_Val2)...) {}

template <class _Other1, class... _Other2>

constexpr _Compressed_pair(_One_then_variadic_args_t, _Other1&& _Val1, _Other2&&... _Val2)

noexcept(conjunction_v<is_nothrow_constructible<_Ty1, _Other1>, is_nothrow_constructible<_Ty2, _Other2...>>)

: _Ty1(_STD forward<_Other1>(_Val1)), _Myval2(_STD forward<_Other2>(_Val2)...) {}

constexpr _Ty1& _Get_first() noexcept {

return *this;

}

constexpr const _Ty1& _Get_first() const noexcept {

return *this;

}

};

标签

struct _Zero_then_variadic_args_t {

explicit _Zero_then_variadic_args_t() = default;

}; // tag type for value-initializing first, constructing second from remaining args

struct _One_then_variadic_args_t {

explicit _One_then_variadic_args_t() = default;

}; // tag type for constructing first from one arg, constructing second from remaining args

`std::move`

概述
1. 源码实现巧妙地运用了C++的模板元编程技术，其核心在于类型转换，它本身并不移动任何数据，而是为真正的移动操作（由移动构造函数或移动赋值运算符执行）铺平道路
remove_reference
1. remove_reference模板，它的唯一作用就是剥去类型上的引用修饰符，暴露出最根本的类型 _Ty

// 主模板：处理非引用类型。直接定义 `type` 为 _Ty。

template <class _Ty>

struct remove_reference {

using type = _Ty; // 原始类型

using _Const_thru_ref_type = const _Ty; // 常量版本的原类型

};

// 特化版本1：处理左值引用 (_Ty&)。剥去`&`，`type` 为 _Ty。

template <class _Ty>

struct remove_reference<_Ty&> {

using type = _Ty; // 剥去左值引用，得到原始类型

using _Const_thru_ref_type = const _Ty&; // 保持左值引用，并为底层类型添加const

};

// 特化版本2：处理右值引用 (_Ty&&)。剥去`&&`，`type` 同样为 _Ty。

template <class _Ty>

struct remove_reference<_Ty&&> {

using type = _Ty; // 剥去右值引用，得到原始类型

using _Const_thru_ref_type = const _Ty&&; // 保持右值引用，并为底层类型添加const

};

// 便捷别名模板，允许直接使用 remove_reference_t<T> 代替 typename remove_reference<T>::type

template <class _Ty>

using remove_reference_t = typename remove_reference<_Ty>::type;

这个模板通过特化技术，针对不同的输入类型（无引用、左值引用、右值引用）提供了统一的接口来获取其原始类型

T remove_reference<T>::type remove_reference_t<T>

int int int

int& int int

int&& int int

move函数本身
1. _Ty：这是类型推导的关键
2. _Ty&& _Arg：这是一个万能引用（universal reference）
  注意，并非所有 T&&都是万能引用，但在模板函数参数这个特定语境下，它可以根据实参类型进行推导，绑定到左值或右值
3. 返回remove_reference_t<_Ty>&&：这是精髓所在
  它使用 remove_reference_t先获取 _Ty的原始类型，然后明确地加上 &&，表示此函数总是返回一个该类型的右值引用
4. static_cast<remove_reference_t<_Ty>&&>(_Arg)：进行一个静态类型转换，将参数 _Arg强制转换为右值引用类型
5. noexcept：声明此操作不会抛出异常，这对于移动操作的安全性和效率很重要

template <class _Ty>

_NODISCARD _MSVC_INTRINSIC constexpr remove_reference_t<_Ty>&& move(_Ty&& _Arg) noexcept {

return static_cast<remove_reference_t<_Ty>&&>(_Arg);

}

注意
1. std::move本身不移动
  它只是一个高级的类型转换工具，告诉编译器：“这个对象可以被移动了”。真正的资源转移发生在类的移动构造函数或移动赋值运算符中
2. 使用后的对象状态：
  被 std::move转换并移交资源后，原对象处于有效但未指定的状态。你不应再使用其值，但可以对其重新赋值或析构
3. 不要移动临时对象（右值）
  对于临时对象（纯右值，如函数返回值 return obj;），编译器已经会优先尝试移动，无需再画蛇添足地使用 std::move
4. 确保对象之后不再被使用：
  一旦对一个对象使用了 std::move，就意味着你放弃了对它资源的所有权，不应再依赖其值

`std::forward`

概述
1. 核心作用是实现完美转发
2. 简单来说，它能在函数模板中，将一个参数的原始值类别（是左值还是右值）“原封不动”地传递给另一个函数
示例


特性/场景	未使用 `std::forward`(`func(arg)`)	使用 `std::forward`(`func(std::forward<T>(arg))`)
核心问题	参数 `arg`在函数内部始终是左值，导致右值属性丢失	保持参数的原始值类别（左值或右值）
传入左值	调用 `func(int&)`，符合预期	调用 `func(int&)`，符合预期
传入右值	调用 `func(int&)`，但期望调用 `func(int&&)` 右值被当作左值处理，可能无法触发移动语义，造成不必要的拷贝	调用 `func(int&&)`，符合预期能正确利用移动语义，提升效率

code

_EXPORT_STD template <class _Ty>

_NODISCARD _MSVC_INTRINSIC constexpr _Ty&& forward(remove_reference_t<_Ty>& _Arg) noexcept {