1.STL源码学习（3）- vector详解
2.[stl 源码分析] std::list::size 时间复杂度
3.STL源码分析之std::function
4.[stl 源码分析] 浅析 std::vector::emplace_back
5.[stl 源码分析] std::sort
6.从应用到源码理解STL反向迭代器

STL源码学习（3）- vector详解

       STL源码学习（3）- vector详解

       vector的码问迭代器与数据类型：vector内部的连续存储结构使得任何类型的数据指针都可以作为其迭代器。通过迭代器，码问可以执行诸如指针操作，码问如访问元素值。码问

       vector定义了两个迭代器start和finish，码问分别指向元素的码问走客 app 源码起始和终止地址，同时还有一个end_of_storage标记空间的码问结束位置。vector的码问容量保证大于等于已分配元素空间，提供了获取空间大小的码问函数，如front和back的码问值以引用返回，更高效。码问

       空间配置原理：STL中的码问vector使用SGI STL容器的二级空间配置器。vector头部包含配置信息，码问如data_allocator作为空间配置器的码问别名。简单配置器（simple_alloc）是码问封装了高级和低级配置器调用的抽象类。

       构造函数与内存管理：vector通过空间配置器创建元素。构造函数允许预分配并初始化元素，fill_initialize用于调整空间范围，allocate_and_fill则分配空间并填充。这个过程涉及data_allocator的allocate函数，分配空间并返回起始地址。

       vector析构时，调用deallocate函数释放空间。pop_back和erase方法会移除元素并销毁相应空间，clear则清除全部元素。insert操作复杂，根据元素数量和容器状态可能需要扩容。

       插入与扩展操作：push_back在末尾插入元素，如果空间不足，可能需要扩容。insert接受三个参数，根据情况处理插入操作，可能抛出异常并销毁部分元素。说话指标源码

[stl 源码分析] std::list::size 时间复杂度

       在对Linux上C++项目进行性能压测时，一个意外的发现是std::list::size方法的时间复杂度并非预期的高效。原来，这个接口在较低版本的g++（如4.8.2）中是通过循环遍历整个列表来计算大小的，这导致了明显的性能瓶颈。@NagiS的提示揭示了这个问题可能与g++版本有关。

       在功能测试阶段，CPU负载始终居高不下，通过火焰图分析，std::list::size的调用占据了大部分执行时间。火焰图的使用帮助我们深入了解了这一问题。

       查阅相关测试源码（源自cplusplus.com），在较低版本的g++中，std::list通过逐个节点遍历来获取列表长度，这种操作无疑增加了时间复杂度。然而，对于更新的g++版本（如9），如_glibcxx_USE_CXX_ABI宏启用后，list的实现进行了优化。它不再依赖遍历，而是利用成员变量_M_size直接存储列表大小，从而将获取大小的时间复杂度提升到了[公式]，显著提高了性能。具体实现细节可在github上找到，如在/usr/include/c++/9/bits/目录下的代码。

STL源码分析之std::function

       std::function是一个在C++中广泛应用的函数包装器，它允许你以类型安全的方式存储、复制和调用任何可复制构造的可调用目标，如普通函数、成员函数、类对象（重载了operator()的类的对象）、Lambda表达式等。伊甸乐园源码通过使用std::function，可以避免使用函数指针时的类型不安全问题。

       然而，许多人对于std::function内部是如何存储这些可调用目标的实现过程感到好奇。本文将深入探讨std::function的源码，揭示它的实现机制。首先，我们来看一下std::function的基本用法和功能。然后，我们将分析其源码，了解它如何存储和管理这些可调用目标。

       在源码中，std::function是一个模板类，其核心成员变量_M_invoker存储了一个标准函数指针类型。这个指针并不直接管理可调用目标，而是负责调用存储在内部的可调用目标。实际的可调用目标则由类_Function_base::_M_functor管理。

       为了实现这一点，std::function使用一个名为function的构造函数，通过一个名为_M_init_functor的函数来初始化_M_invoker，从而将可调用目标链接到_M_invoker上。这个过程涉及到一个名为_Base_manager的内部类，它负责存储和管理可调用目标。

       在源码中，我们发现可调用目标的存储方式取决于其大小。对于小到足以在单个内存位置存储的目标，如普通函数指针，std::function直接使用_M_pod_data作为存储空间。而对于较大的目标，如Lambda表达式或类对象，它会动态分配内存来存储这些对象。

       通过仔细分析这些内部实现，软件源码免费我们可以看到std::function是如何在存储和调用可调用目标之间建立起复杂的链接。这种设计使得std::function成为了一个灵活且强大的工具，能够在C++程序中实现高度动态和类型安全的函数调用。

       总之，std::function通过巧妙地设计其内部实现，实现了对各种可调用目标的高效存储和调用。了解其源码可以帮助我们更好地利用std::function的强大功能，同时也能深入理解C++中类模板和动态内存管理的高级概念。

[stl 源码分析] 浅析 std::vector::emplace_back

       本文通过测试和走读 std::vector::emplace_back 源码，理解 C++ 引入的 emplace 新特性。

       原理相对简单：emplace_back 函数的参数类型是可变数量的万能引用，参数通过 完美转发 到 std::vector 内部进行对象创建构造，可以有效减少参数传递过程中产生临时对象，避免了对象的移动和拷贝。

       具体来说，std::vector::emplace_back 是 C++ 中 std::vector 类的成员函数之一，它用于在 std::vector 的末尾插入一个新元素，而不需要进行额外的拷贝或移动操作。

       通过走读源码，详细知识请查看《Effective Modern C++》- 第五章：右值引用、移动语义和完美转发。

       测试结果反馈了一些有趣的信息：在对象元素的插入过程中，有的触发拷贝构造，有的触发移动构造，有的两者都没触发。通过查看 emplace_back 的内部实现源码，找到答案。

       动态数组使用的是连续的内存空间，一些操作可能会触发内存的动态扩展，这个过程中可能产生数据拷贝或者移动。因此，最好保存对象指针，绘画源码精灵即便容器内部发生数据拷贝，成本也比较低。

       当我们不了解容器内部具体实现时，最好不要往容器里保存类/结构对象元素，保存对象指针 是个不错的选择。对于 std::vector 内部内存扩展，元素对象为什么不是转移而是拷贝构造，应该为移动构造函数添加noexcept 标识，这样才会进行移动。

[stl 源码分析] std::sort

       std::sort在标准库中是一个经典的复合排序算法，结合了插入排序、快速排序、堆排序的优点。该算法在排序时根据几种算法的优缺点进行整合，形成一种被称为内省排序的高效排序方法。

       内省排序结合了快速排序和堆排序的优点，快速排序在大部分情况下具有较高的效率，堆排序在最坏情况下仍能保持良好的性能。内省排序在排序过程中，先用快速排序进行大体排序，然后递归地对未排序部分进行更细粒度的排序，直至完成整个排序过程。在快速排序效率较低时，内省排序会自动切换至插入排序，以提高排序效率。

       在实现上，std::sort使用了内省排序算法，并在适当条件下切换至插入排序以优化性能。其源码包括排序逻辑的实现和测试案例。排序源码主要由内省排序和插入排序两部分组成。

       内省排序在排序过程中先快速排序，然后对未完全排序的元素进行递归快速排序。当子数组的长度小于某个阈值时，内省排序会自动切换至插入排序。插入排序在小规模数据中具有较高的效率，因此在内省排序中作为优化部分，提高了整个排序算法的性能。

       插入排序在排序过程中，将新元素插入已排序部分的正确位置。这种简单而直观的算法在小型数据集或接近排序状态的数据中表现出色。内省排序通过将插入排序应用于小规模数据，进一步优化了排序算法的性能。

       综上所述，std::sort通过结合内省排序和插入排序，实现了高效且稳定的数据排序。内省排序在大部分情况下提供高性能排序，而在数据规模较小或接近排序状态时，插入排序作为优化部分，进一步提高了排序效率。这种复合排序方法使得std::sort成为标准库中一个强大且灵活的排序工具。

从应用到源码理解STL反向迭代器

       在实际应用中，我们可能需要从序列容器（如vector）的尾部移除不满足特定条件的部分元素。这通常涉及从尾部开始的迭代操作。然而，容器成员函数erase不接受反向迭代器作为参数。因此，我们需要将反向迭代器转换为普通迭代器。先来看看STL迭代器的分类和转换关系。

       STL迭代器主要分为用途迭代器，它们之间存在转换关系，但不是所有迭代器类型都可以相互转换。转换关系需通过迭代器的构造函数定义，有些可以直接转换，有些则需调用特定方法。

       特别地，反向迭代器到普通迭代器的转换可以通过调用反向迭代器的base()方法实现。但初版代码存在缺陷，未能按预期将元素正确删除。通过跟踪代码并参考cpp reference文档，我们发现base()方法返回的迭代器实际上比预期位置靠后一个元素。

       为了修正这个问题，我们需要将通过base()方法得到的迭代器向前移动一个位置，以正确指向第一个符合移除条件的元素。修改代码后，可以确保元素按约定进行删除。

       在一般场景下，迭代器的使用主要涉及遍历访问和遍历修改元素值。对于删除和插入操作，可能需要将反向迭代器转换为普通迭代器。STL容器的erase和insert成员函数仅接受普通迭代器作为参数。

       在执行插入操作时，直接使用base()将反向迭代器转换为普通迭代器，并传入insert函数，其语义是一致的。而在删除操作中，直接使用base()转换后的迭代器可能无法正确执行，因为反向迭代器和普通迭代器在终止位置上的处理存在差异。为了修正此问题，需要手动调整，确保迭代器的有效性。

       对于反向迭代器，通过正确的反向迭代操作得到的迭代器，在不等于rend()返回的迭代器时，都是指向有效值的。因此，除了rend().base()-1操作可能导致问题外，其他转换通常都是安全的。

       讨论end()迭代器的前移操作时，需要考虑是否能够安全地访问容器的尾端元素。对于随机访问迭代器，如vector容器，end()返回的迭代器可以进行前移操作，但需确保移动操作的合法性。对于双向访问迭代器如list，同样可以进行前移操作以访问尾端元素。

       结束讨论前，还需要确认iterator的-1操作是否对指向容器尾端元素的迭代器有效。在vector容器中，通过end成员函数返回的迭代器通过-1操作可以得到指向尾端元素的普通迭代器。对于list容器，其end成员函数返回的迭代器也支持前移操作。

       总结来说，支持向前移动操作的迭代器访问容器内元素的容器，其end成员函数通过前移操作可以得到一个指向容器尾端元素的迭代器。这符合双向迭代器的设定语义。通过反向迭代器的原理，我们也能验证end()函数返回的迭代器可以进行反向移动。

STL源码剖析总结笔记（2）：容器（containers）概览

       容器作为STL的重要组成部分，其使用极大地提升了解决问题的效率。深入研究容器内部结构与实现方式，对提升编程技能至关重要。本文将对容器进行概览，分为序列式容器、关联式容器与无序容器三大类。

       容器大致分为序列式容器、关联式容器和无序容器。其中序列式容器侧重于顺序存储，关联式容器则强调元素间的键值关系，而无序容器可以看作关联式容器的一种。

       容器之间的关系可以归纳为：序列式容器为基层，关联式容器则在基层基础上构建了更复杂的数据结构。例如，heap和priority容器以vector作为底层支持，而set和map则采用红黑树作为基础数据结构。此外，还存在一些非标准容器，如slist和以hash开头的容器。在C++ 中，slist更名为了forward-list，而hash开头的容器改名为了unordered开头。

       在容器的实现中，sizeof()函数可能揭示容器的内部大小对比。需要注意的是，尽管在GNU 4.9版本中，一些容器的设计变得复杂，采用了较多的继承结构，但实际上，这些设计在功能上并未带来太大差异。

       熟悉容器的结构后，我们可以从vector入手，探索其内部实现细节。其他容器同样蕴含丰富的学习内容，如在list中，迭代器（iterators）的设计体现了编程的精妙之处；而在set和map中，红黑树的实现展现了数据结构的高效管理。

       本文对容器进行了概览，旨在提供一个全面的视角，后续将对vector、list、set、map等容器进行详细分析，揭示其背后的实现机制与设计原理。

STL源码剖析9-set、multiset

       STL源码深入研究：set与multiset的内部结构详解

       1. 结论

       在C++标准模板库(STL)中，set和multiset是两种常用的数据结构，它们底层实现依赖于红黑树（rb tree）。set是一种无序的关联容器，不允许有重复元素，而multiset则允许元素重复，但仍然保持插入顺序。

       2. set的实现

       set内部的红黑树使用了stl_function.h中的仿函数模板参数，这个仿函数用于定义元素的比较规则。set类在stl_set.h文件中定义，它通过这个仿函数确保了元素的唯一性，保证了查找、插入和删除操作的高效性。

       3. multiset的特性

       与set不同，multiset在stl_multiset.h中定义，它允许元素重复，这主要通过维护每个元素在树中的多个实例来实现。与set一样，它也依赖红黑树的数据结构，但对元素的比较规则更为宽松，允许基于给定的比较仿函数进行重复元素的插入和查找。