概述
- 首先，
stack是一个容器适配器 - 理论上，任何提供了
push_back(),pop_back(),back()等操作的序列容器都可以作为stack的底层容器
为什么默认是deque
deque之所以成为默认选择，是因为它在以下几个方面取得了最佳平衡：- 相对于
vectordeque的主要优势在于高效且低成本的动态扩容vector在尾部空间不足时，需要申请一块更大的内存，然后将所有元素整体搬迁过去，这个操作的时间复杂度是O(n)deque采用分段连续的结构，只需要新增一个内存块（buffer）并将其指针添加到中控器（map）中即可，开销要小得多
- 相对于
listdeque的主要优势在于更高的内存利用率和缓存友好性list的每个元素都存储在两个指针（前驱和后继），内存开销较大，且节点在内存中不连续，容易造成内存碎片，CPU缓存命中率较低deque的元素存储在连续的内存块中，虽然块与块之间不连续，但块内是连续的，这在保证高效操作的同时，提供了更好的内存局部性
灵活性：其他容器
- 尽管
deque是默认选择，但STL的适配器设计给予了充分的灵活性
|
1 2 3 4 5 6 7 8 9 |
#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
设计
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
_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_Is_allocator<_Container>::value用于判断类型_Container是否为分配器（Allocator）!_Is_allocator<_Container>::value表示：只有当_Container不是分配器类型时，这个推导指引才参与重载决议，有效
为了避免混淆：用一个分配器对象来构造一个栈，还是想用这个分配器作为底层容器
此约束明确排除了后一种情况-> stack<typename _Container::value_type, _Container>
推导结果：
告诉编译器：如果使用一个类型为_Container的对象来构造stack，那么最终stack的模板参数应该被推导为stack<typename _Container::value_type, _Container>
typename _Container::value_type表示从传入的容器类型中提取其元素类型，作为stack的元素类型
|
1 2 3 4 |
#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- 这个指引用于处理同时传入容器和分配器对象的情况（例如，一个使用自定义分配器的容器）
negation<_Is_allocator<_Container>>：确保第一个参数（_Container）不是分配器类型。这和第一个指引中的约束目的相同uses_allocator<_Container, _Alloc>：这是一个关键的检查，它判断提供的容器类型_Container是否能够使用提供的分配器类型_Alloc。这确保了容器与分配器是兼容的- 只有同时满足这两个条件，该推导指引才有效
- 推导结果与第一个指引相同：
stack<typename _Container::value_type, _Container>
分配器类型_Alloc已经被包含在容器的类型之中（例如，std::vector<int, MyAlloc>本身就包含了分配器信息）
|
1 2 3 4 5 6 7 8 |
// 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); // 使用第二个推导指引 |
|
1 2 3 4 5 |
#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
|
1 2 3 4 |
#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
|
1 2 3 4 |
#if _HAS_CXX23 template <_RANGES input_range _Rng> stack(from_range_t, _Rng&&) -> stack<_RANGES range_value_t<_Rng>>; #endif // _HAS_CXX23 |
- 上述
cpp23推导指引3
|
1 2 3 4 |
#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
negation
cpp17对类型特性的布尔值::value进行逻辑非运算std::bool_constant是一个辅助模板，它根据表达式!bool(B::value)的结果，提供一个static constexpr bool成员value- 如果
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// 基础案例：空参数包，结果为 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_object
cpp11用于在编译时判断一个类型是否属于对象类型- 简单来说，它的核心逻辑是：只要一个类型不是函数、不是引用、也不是
void，那么它就是一个对象类型
- 简单来说，它的核心逻辑是：只要一个类型不是函数、不是引用、也不是
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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）- 简单来说，它在编译时告诉你一个类是否不占用任何非静态数据成员存储空间
- 一个类类型要被
std::is_empty_v判定为true，必须同时满足以下严格条件- 非联合体的类类型：必须是
class或struct，但不能是union - 无非静态数据成员：类中不能有任何非静态成员变量（静态数据成员是允许的）
- 无虚函数：类中不能声明或继承虚函数（即没有虚函数表）
- 无虚基类：在继承体系中，不能有虚继承（即没有虚基类表）
- 无非空基类：所有直接基类本身也必须都是空类
- 非联合体的类类型：必须是
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#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- 如果类型
T是一个被final修饰的类类型（包括结构体），则std::is_final_v<T>的值为true，否则为false
- 如果类型
|
1 2 3 4 5 |
template<typename Base> class MyDerived : public Base { // 希望 Base 不是 final 的 static_assert(!std::is_final_v<Base>, "Base class must not be final."); // ... 其他实现 }; |
空基类优化
|
1 2 3 4 5 6 7 |
class _Compressed_pair final : private _Ty1 { // 私有继承空基类 public: _Ty2 _Myval2; // 直接存储第二个值 ... constexpr _Ty1& _Get_first() noexcept { return *this; // 通过this指针获取基类部分 } |
|
1 2 3 4 5 6 7 8 9 |
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 } |
标签分发
- 使用标签类型来区分不同的构造方式
_Zero_then_variadic_args_t：默认构造_Ty1，然后使用参数构造_Ty2_One_then_variadic_args_t：使用第一个参数构造_Ty1，剩余参数构造_Ty2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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; } }; |
- 标签
|
1 2 3 4 5 6 7 |
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 |
声明：本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ C++_trunk相关10/24
- ♥ C++14_第一篇12/14
- ♥ C++_函数模板、类模板、特化、模板元编程、SFINAE、概念06/22
- ♥ 大话数据结构_栈11/01
- ♥ C++标准模板库编程实战_关联容器12/07
- ♥ STL_内存处理工具05/02