序言
工作之余，突觉自己编程水平有限，对数据结构、算法知之甚少，甚至C++基础也不甚牢固，决定仔细研究基础但相当重要的STL容器，以查漏补缺。
历时一个多月，从C++初学者水平，零STL基础完成了整个手撕STL的项目，感慨良多，决定制作一份详细的讲解，供大家交流讨论。
系列导航
项目地址：https://github.com/Icingworld/WW-STL
仓库代码已经补全，code review会随着系列帖子逐渐完成，欢迎大家关注交流！
一、初识 STL
STL（标准模板库）是 C++ 标准库的一个重要组成部分，是一套泛型编程组件。它提供了大量可复用的模板类和函数，帮助程序员快速实现高效的数据结构和算法。
STL 并非指某些特定的代码，而是一套抽象的接口概念，是一个严谨的接口标准，凡是严格按照 STL 标准实现的容器，都可以称为 STL 容器。
一、STL 的特点
STL 的特点是：
- 通用性：STL 广泛使用模板，可以使得容器能存储不同的数据类型。
- 高效性：时间方面，STL 规定了算法的时间复杂度，并使用哈希表、红黑树等作为高级容器的底层数据结构，提高了算法的效率；空间方面，STL 有自己的内存分配器，设计了动态的内存策略，提高了内存管理的效率。
- 灵活性：STL 采用分层设计，六大组件各司其职，可以独立测试，也可以组合使用，为自定义、扩展提供了便捷。
- 统一性：对不同的容器，STL 设计了类似的接口，可以方便地操作不同地容器，降低了学习和使用难度。
二、STL 的组成
STL 由六大组件组成，每个组件可以组合使用：
- 容器（container）：STL 中最直观的部分，提供存储数据的容器，包括了vector、list、deque等常用数据结构。
- 算法（algorithm）：提供操作数据结构的算法，通过迭代器来适配各种不同的数据结构，提供通用的算法操作。
- 迭代器（iterator）：迭代器是一种自定义的指针，可以便捷地在容器中移动，对外提供访问容器的能力，也是容器和算法之间的桥梁。
- 仿函数（functor）：仿函数是一种重载了()的类，以模仿函数的调用方式。
- 适配器（adaptor）：适配器是一种修饰容器的策略，其底层一般使用某种容器，适配器在其基础上限制或扩展容器的功能，以达到构建某种数据结构的目的。比如，stack 和 queue 都是适配器，其底层是 deque 双端队列，stack 和 queue 通过限制数据的插入、删除，实现了栈和队列两种数据结构。
- 分配器（allocator）：提供内存管理的策略。
三、STL 容器
STL 中，容器分为序列型容器、关联型容器、无序关联型容器和容器适配器四种
序列型容器有：
- array：固定长度数组
- vector：动态数组
- deque：双端队列
- forward_list：单向链表
- list：双向链表
关联型容器有：
- set：有序集合
- multiset：有序多值集合
- map：有序映射
- multimap：有序多值映射
无序关联型容器有：
- unordered_set：无序集合
- unordered_multiset：无序多值集合
- unordered_map：无序映射
- unordered_multimap：无序多值映射
容器适配器有：
- stack：栈
- queue：队列
- priority_queue：优先队列
二、分配器
分配器是 STL 容器的基石，一切的容器都离不开分配器，使用分配器，我们能方便地管理容器中的内存，提高了内存的管理效率，使得我们在实现容器时保证了代码的可读性和可维护性。
因此我们从分配器开始，一步步实现 STL。在本实现中，作者只实现了一个拥有基本分配能力的分配器，而 SGI STL 实现的 STL 中，分配器具有次级空间分配能力，能够根据分配空间的大小，选择如何分配空间，当空间大于128byte时，直接在堆中申请相应大小的空间，当小于128byte时，启动次级分配器，在预先维护的内存池中取出一块分配给用户。
一、分配器的实现
分配器的完整实现位于ww_memory.h中，文后亦会给出
1. 分配器的结构
template <class T>
class allocator
{
public:
using value_type = T;
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using propagate_on_container_move_assignment = std::true_type;
using is_always_equal = std::true_type;
template <typename U>
class rebind
{
public:
using other = allocator<U>;
};
};
allocator是一个模板类，用于管理数据类型为T的对象内存。
using value_type = T;
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using propagate_on_container_move_assignment = std::true_type;
using is_always_equal = std::true_type;
这是allocator类的嵌套类型定义，用于描述allocator的成员类型，其中value_type的定义是必须的，其他定义可选，如果没有定义，allocator_traits会为其自动生成默认的嵌套类型定义。
在《STL源码剖析》一书及标准库实现中，可能采用typedef来定义别名，这和using的效果是一样的，由于using更符合现代 C++ 的风格，符合自然语言的直觉，且在支持模板上更胜一筹，本实现使用using来定义别名。
template <typename U>
class rebind
{
public:
using other = allocator<U>;
};
rebind是一个嵌套类，它只有一个类型定义other，通过它可以将allocator重新绑定到新的类型U上去。
使用方法示例：
#include "ww_memory.h"
using int_allocator_type = wwstl::allocator<int>;
using double_allocator_type = typename int_allocator_type::template rebind<double>::other;
为什么要这么做呢，在一些数据结构如 list 等，维护的并不是单纯的数据类型T，而是一个节点list_node，因此分配器的职责需要转为管理节点类，而我们在定义 list 的模板时发现：
template <
class T,
class Allocator = mystl::allocator<T>
> class list
{
};
Allocator是根据模板参数T已经确定了的，只能管理数据类型T，因此需要在使用前将其rebind转换为节点分配器。
2. 分配器的接口
分配器主要拥有申请空间、释放空间、构造对象、销毁对象四个功能。
- 申请空间：
pointer allocate(size_type n, const void * hint = nullptr)
{
(void)hint;
if (n > max_size())
throw std::bad_array_new_length();
if (n == 0)
return nullptr;
return static_cast<pointer>(::operator new(n * sizeof(value_type)));
}
该接口接受两个参数，第一个参数n为需要申请的元素个数，第二个参数hint为提示指针，如果支持，则在申请空间时会优先申请靠近这个指针的空间，本 STL 实现忽略所有带提示的接口。
值得注意的是，这个接口中使用了::operator new运算符，它是全局作用域下的内存分配函数，是对malloc的封装，因此它和malloc一样，接受一个空间大小，返回一个void *，需要将其转换为目标pointer
在这个函数中，存在两种异常抛出，一是bad_array_new_length，当申请空间过大时抛出；二是bad_alloc，由::operator new抛出，这也是和malloc不一样的地方。
- 释放空间
void deallocate(pointer ptr, size_type n = 0)
{
(void)n;
if (ptr == nullptr)
return;
::operator delete(ptr);
}
该函数使用::operator delete，它是对free的封装，接受一个指针作为参数，第二个参数n是申请时申请的元素数量，起到提醒的作用，可忽略。
- 构造对象
template <typename U, typename... Args>
void construct(U * ptr, Args&&... args)
{
::new(ptr) U(std::forward<Args>(args)...);
}
该接口接受两个参数，第一个是一个指针ptr，表明需要在什么地方构造对象，第二个参数是一个万能引用参数包，可以传入任何数量的任何参数，作为类U的构造函数的参数。
该函数中，使用的是 placement new 函数，它接受一个已经申请空间，但是未构造的指针，在该位置构造一个对象。
- 销毁对象
template <typename U>
void destroy(U * ptr)
{
ptr->~U();
}
该接口接受一个指针参数，传入一个由 placement new 构造的对象，调用它的析构函数，注意它并不会释放被占用的空间，只是将内存恢复为申请后的状态。
- 思考
这四个函数涵盖了 C++ 常用的内存管理机制，我们常用 new 和 delete 来进行动态分配，实际上，当我们使用 new operator 时，首先申请了一个元素大小的空间，随后在该空间上构造对象；当我们使用 delete operator 时，首先调用了类的析构函数，随后释放该空间。
int * p = new int(7);
delete p;
3. 其他接口
在allocator的实现中，引人注目的还有这两个重载：
bool operator==(const allocator & other) const noexcept
{
return true;
}
bool operator!=(const allocator & other) const noexcept
{
return false;
}
实际上，分配器是一个无状态的类，无论是什么模板参数的分配器，它们总是相等的，这一点在嵌套类型定义中可见：
using is_always_equal = std::true_type;
完整代码
#ifndef __WW_MEMORY_H__
#define __WW_MEMORY_H__
#include <limits>
#include <stdexcept>
namespace wwstl
{
template <class T>
class allocator
{
public:
using value_type = T;
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using propagate_on_container_move_assignment = std::true_type;
using is_always_equal = std::true_type;
template <typename U>
class rebind
{
public:
using other = allocator<U>;
};
public:
allocator() noexcept = default;
allocator(const allocator & other) noexcept = default;
template <typename U>
allocator(const allocator<U> & other) noexcept
{
};
~allocator() = default;
public:
pointer allocate(size_type n, const void * hint = nullptr)
{
(void)hint;
if (n > max_size())
throw std::bad_array_new_length();
if (n == 0)
return nullptr;
return static_cast<pointer>(::operator new(n * sizeof(value_type)));
}
void deallocate(pointer ptr, size_type n = 0)
{
(void)n;
if (ptr == nullptr)
return;
::operator delete(ptr);
}
template <typename U, typename... Args>
void construct(U * ptr, Args&&... args)
{ ::new(ptr) U(std::forward<Args>(args)...); }
template <typename U>
void destroy(U * ptr)
{ ptr->~U(); }
size_type max_size() const noexcept
{ return std::numeric_limits<std::size_t>::max() / sizeof(value_type); }
pointer address(reference r) const noexcept
{ return &r; }
const_pointer address(const_reference r) const noexcept
{ return &r; }
bool operator==(const allocator & other) const noexcept
{ return true; }
bool operator!=(const allocator & other) const noexcept
{ return false; }
};
template <>
class allocator<void>
{
public:
using value_type = void;
using pointer = void*;
using const_pointer = const void*;
using propagate_on_container_move_assignment = std::true_type;
using is_always_equal = std::true_type;
};
}
#endif
[复制链接]
发表于 2025-1-16 23:51
|
发表于 2025-1-17 13:50
