8、stack/queue/priority_queue这三者确切来讲，并不属于 STL 的容器，而是容器适配器：将容器封装成特定接口。8.1、stackstack 是栈数据结构，遵循先进后出（First in last out, FILO），有入栈和出栈两个操作，默认使用 std::deque 实现，入栈和出栈也是直接操作 deque 的接口。 /// stl_stack.h template<typename _Tp, typename _Sequence = deque<_Tp> > class stack { public: ...

7、unordered_map/unordered_set/unordered_multimap/unordered_multiset（C++11）STL 这四个容器底层实现都是哈希表，因为哈希表不具备排序功能，所以这四个容器元素都是无序的。底层哈希表整体布局如下：如果想进一步了解哈希表，可以查阅分析的文章GCC 哈希表设计与实现7.1、unordered_mapunordered_map 和 map 除了底层实现不同，其他接口类似。unordered_map 只有一个成员变量 _M_h，是 __umap_hashtable 类型。__umap_hashtable 就是 GCC 哈希表实现 _...

6、map/multimap/set/multiset6.1、rb_treemap 和 multimap 以及 set 和 multiset 底层数据结构都是红黑树，如果对红黑树数据结构感兴趣，可以参考关于红黑树的分享一文搞懂红黑树这里简单介绍一下 map 和 multimap 底层红黑树的布局。rb_tree 有一个 rb_tree_impl 类型的数据成员，rb_tree_impl 实现红黑树，rb_tree 是对 rb_tree_impl 的封装。header 是实现的技巧，header.parent 保存根结点 root，header.left 保存最左元素，是中序遍历的首元素，hea...

5、dequedeque 是双端队列（double-ended queue），其实现比较特殊，有多段地址连续的存储空间组成，整理布局如下：每段地址连续内存成为一个 nodemap 是指针构成的数据，每个元素指向一个 nodestart 和 finish 是一个迭代器变量，分别指向第一个和最后一个 node迭代器以 node 为单位cur 指向当前元素first 指向 node 第一个元素last 指向 node 最后一个元素的下一个地址node 指向 map 中相应位置，可以很方便找到前一个或者后一个 nodenode 计算如下元素占用内存小于 512 字节，最大占用 512 字节否则，默认分...

4、forward_list (C++11)forward_list 是 C++11 引入的单链表数据结构。4.1、_Fwd_list_node首先是 forward_list 链表结点。_Fwd_list_node 继承于 _Fwd_list_node_base，成员 _M_storage 保存用户数据，_M_valptr() 函数返回 _M_storage 的地址。 /// forward_list.h template<typename _Tp> struct _Fwd_list_node : public _Fwd_list_node_base ...

3、listlist 是双向链表实现。双向链表结点在堆上动态申请，插入和删除操作不存在移动元素的操作。3.1、_List_nodelist 中每个结点都用 _List_node 表示，继承于 _List_node_base。_List_node 成员 _M_storage，用于保存数据。 /// stl_list.h /// An actual node in the %list. template<typename _Tp> struct _List_node : public __detail::_List_node_base { #if __cplus...

https://mp.weixin.qq.com/s?__biz=Mzg4ODcxMjIyMA==&mid=2247484067&idx=1&sn=d9e888a3af3007f1637299ad1ff1a1e9&chksm=cff7bfd0f88036c639b03ee2c40cbfdf00446483d214d9e3874ab8de3eb9e1c760cc209ce7a2

2、vectorvector 属于动态数组，自动控制存储空间，根据需要进行扩展和收缩。通常拥有额外的空间以处理未来的增长，这样，每次插入元素时，不需要每次重新分配内存，仅在附加内存耗尽时才重新分配。可使用 capacity() 查看分配的内存总量，也可以调用 shrink_to_fit() 将额外的内存返回给系统。如果事先知道元素数量，可调用 reserve(n) 一次性分配内存。vector 继承于 _Vector_base，_Vector_base 只有一个 _Vector_impl 类型的成员变量。 template<typename _Tp, typename _Alloc&...

1、array（C++11）array 是固定长度的数组，定义时就指定长度，一旦定义长度不能更改（不能扩容）。 template<typename _Tp, std::size_t _Nm> struct array { typedef _Tp value_type; typedef value_type* pointer; typedef const value_type* const_point...

以引用计数为基础的智能指针，引用计数的管理逻辑如下：除了初始化对象本身外，每个构造函数（拷贝构造函数除外）还要在堆上创建一个引用计数，用来记录有多少个对象共享状态。当我们创建一个对象时，只有一个对象共享状态，因此将引用计数初始化为 1；拷贝构造函数不分配新的计数器，而是拷贝给定对象的数据成员，包括计数器。拷贝构造函数递增共享的计数器，标记给定对象的状态又被一个新用户所共享析构函数递减计数器，标记共享状态的用户少了一个。如果计数器变为 0，则析构函数析构对象，包括引进计数变量；拷贝赋值运算符递增右侧运算对象的计数器，递减左侧运算对象的计数器。如果左侧运算对象的计数器变为 0，意味着它的共享状态没...

1、std::shared_ptr1.1、总体关系首先我们看看 shared_ptr 相关的类，主要是 __shared_ptr、__shared_count 和 _Sp_counted_base 这三个。shared_ptr 继承 __shared_ptr，__shared_ptr 有两个成员变量：对象指针 _M_ptr 和引用计数 _M_refcount。引用计数 __shared_count 主要借助 _Sp_counted_base 实现。1.2、_Sp_counted_base<Lp>_Sp_counted_base 是一个基类，有三个派生类，分别用于处理：传入裸指针指定...

1、std::allocator操作符 new 申请内存成功后，调用构造函数初始化内存。另外一种申请内存的方法是调用 operator new() 函数，该函数只申请内存，不执行构造函数。 #include <iostream> class Foo { public: Foo() { std::cout << "Foo::ctor" << std::endl; } ~Foo() { std::cout << "Foo::dtor" << std::endl; } }; int main() { { std::...

1、iterator_tagiterator_tag 标记了 iterator 的类型。 /// Marking input iterators. struct input_iterator_tag { }; /// Marking output iterators. struct output_iterator_tag { }; /// Forward iterators support a superset of input iterator operations. struct forward_iterator_tag : public input_ite...

1、虚函数使用关键字 virtual 可以声明一个虚函数。虚函数在派生类中仍然为虚函数，即使派生类中没有使用关键字 virtual 声明。 class Base { public: Base() = default; virtual ~Base(); virtual void virtualFunc(); void nonOverride(); }; class Derive : public Base { public: Derive() = default; ~Derive(); void virtualFunc(); // vir...