MyTinySTL——开源项目深度分析与优化改进
选择一开源项目（推荐开源操作系统、数据库等基础软件），调试运行，修改项目。通过对MyTinySTL这一高质量C++ STL实现项目的深入研究，掌握大型开源项目的分析方法、缺陷发现技巧和代码优化策略，提升软件工程实践能力。
项目筛选标准：
调研内容：
环境配置：
项目构建：
功能验证：
架构分析：
代码质量评估：
技术特点总结：
测试策略制定：
缺陷发现：
缺陷分析与修复：
每个发现的缺陷需提供：
性能优化：
功能扩展：
代码重构：
功能测试：
性能测试：
兼容性测试：
技术文档：
成果展示：
| 周次 | 主要任务 | 交付物 |
|---|---|---|
| 第1-2周 | 项目选择与调研 | 项目调研报告 |
| 第2-3周 | 环境搭建与运行 | 环境配置文档 |
| 第3-5周 | 代码深度分析 | 架构分析报告 |
| 第4-6周 | 缺陷发现与修复 | Bug修复代码 |
| 第5-7周 | 功能改进与优化 | 优化改进代码 |
| 第6-7周 | 测试与验证 | 测试报告 |
| 第7-8周 | 文档编写与总结 | 完整实践报告 |
MyTinySTL/
├── MyTinySTL/ # 核心库实现
│ ├── astring.h # 字符串类实现
│ ├── algorithm.h # 算法库
│ ├── algobase.h # 基础算法
│ ├── allocator.h # 内存分配器
│ ├── construct.h # 对象构造/析构
│ ├── deque.h # 双端队列
│ ├── functional.h # 函数对象
│ ├── hashtable.h # 哈希表实现
│ ├── heap.h # 堆算法
│ ├── iterator.h # 迭代器
│ ├── list.h # 双向链表
│ ├── map.h # 关联容器map
│ ├── memory.h # 内存管理
│ ├── numeric.h # 数值算法
│ ├── queue.h # 队列适配器
│ ├── rb_tree.h # 红黑树
│ ├── set.h # 集合容器
│ ├── stack.h # 栈适配器
│ ├── type_traits.h # 类型萃取
│ ├── unordered_map.h # 无序映射
│ ├── unordered_set.h # 无序集合
│ ├── util.h # 工具函数
│ └── vector.h # 动态数组
├── Test/ # 测试代码
│ ├── algorithm_performance_test.h
│ ├── algorithm_test.h
│ ├── deque_test.h
│ ├── list_test.h
│ ├── map_test.h
│ ├── set_test.h
│ ├── string_test.h
│ ├── unordered_map_test.h
│ ├── unordered_set_test.h
│ └── vector_test.h
└── docs/ # 文档目录// 第一层：基础类型萃取和内存管理
namespace mystl {
// 类型萃取系统
template<class T> struct type_traits;
template<class Iterator> struct iterator_traits;
// 内存分配器
template<class T> class allocator;
template<class T> class simple_alloc;
}
// 第二层：迭代器和基础算法
namespace mystl {
// 迭代器类型
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
// 基础算法
template<class InputIter, class OutputIter>
OutputIter copy(InputIter first, InputIter last, OutputIter result);
}
// 第三层：容器实现
namespace mystl {
template<class T, class Alloc = allocator<T>> class vector;
template<class T, class Alloc = allocator<T>> class list;
template<class T, class Alloc = allocator<T>> class deque;
}
// 第四层：高级容器和算法
namespace mystl {
template<class Key, class T, class Compare = less<Key>> class map;
template<class Key, class Hash = hash<Key>> class unordered_set;
template<class RandomIter>
void sort(RandomIter first, RandomIter last);
}template <class T, class Alloc = mystl::allocator<T>>
class vector {
public:
// 类型定义
typedef mystl::allocator<T> allocator_type;
typedef mystl::allocator<T> data_allocator;
typedef typename allocator_type::value_type value_type;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::size_type size_type;
typedef typename allocator_type::difference_type difference_type;
typedef value_type* iterator;
typedef const value_type* const_iterator;
typedef mystl::reverse_iterator<iterator> reverse_iterator;
typedef mystl::reverse_iterator<const_iterator> const_reverse_iterator;
private:
// 数据成员 - 三指针设计
iterator begin_; // 表示目前使用空间的头部
iterator end_; // 表示目前使用空间的尾部
iterator cap_; // 表示目前储存空间的尾部
public:
// 构造函数
vector() noexcept { try_init(); }
explicit vector(size_type n) { fill_init(n, value_type()); }
vector(size_type n, const value_type& value) { fill_init(n, value); }
template <class Iter, typename std::enable_if<
mystl::is_input_iterator<Iter>::value, int>::type = 0>
vector(Iter first, Iter last) {
MYSTL_DEBUG(!(last < first));
range_init(first, last);
}
vector(const vector& rhs) { range_init(rhs.begin_, rhs.end_); }
vector(vector&& rhs) noexcept
: begin_(rhs.begin_), end_(rhs.end_), cap_(rhs.cap_) {
rhs.begin_ = nullptr;
rhs.end_ = nullptr;
rhs.cap_ = nullptr;
}
vector(std::initializer_list<value_type> ilist) {
range_init(ilist.begin(), ilist.end());
}
// 析构函数
~vector() {
destroy_and_recover(begin_, end_, cap_ - begin_);
begin_ = end_ = cap_ = nullptr;
}
};动态扩容机制：
template <class T, class Alloc>
void vector<T, Alloc>::reallocate_insert(iterator pos, const value_type& value) {
const auto new_size = get_new_cap(1); // 计算新容量
auto new_begin = data_allocator::allocate(new_size);
auto new_end = new_begin;
try {
// 拷贝插入点之前的元素
new_end = mystl::uninitialized_move(begin_, pos, new_begin);
// 构造新元素
data_allocator::construct(mystl::address_of(*new_end), value);
++new_end;
// 拷贝插入点之后的元素
new_end = mystl::uninitialized_move(pos, end_, new_end);
}
catch (...) {
// 异常安全：清理已分配的内存
data_allocator::deallocate(new_begin, new_size);
throw;
}
// 销毁原有元素并释放内存
destroy_and_recover(begin_, end_, cap_ - begin_);
// 更新指针
begin_ = new_begin;
end_ = new_end;
cap_ = new_begin + new_size;
}
// 容量增长策略
template <class T, class Alloc>
typename vector<T, Alloc>::size_type
vector<T, Alloc>::get_new_cap(size_type add_size) {
const auto old_size = capacity();
THROW_LENGTH_ERROR_IF(old_size > max_size() - add_size,
"vector<T>'s size too big");
if (old_size > max_size() - old_size / 2) {
return old_size + add_size > max_size() - 16
? old_size + add_size : old_size + add_size + 16;
}
// 1.5倍增长策略
const size_type new_size = old_size == 0
? mystl::max(add_size, static_cast<size_type>(16))
: mystl::max(old_size + old_size / 2, old_size + add_size);
return new_size;
}插入操作的优化：
template <class T, class Alloc>
typename vector<T, Alloc>::iterator
vector<T, Alloc>::insert(const_iterator pos, const value_type& value) {
MYSTL_DEBUG(pos >= begin() && pos <= end());
iterator xpos = const_cast<iterator>(pos);
const size_type n = xpos - begin_;
if (end_ != cap_ && xpos == end_) {
// 在末尾插入且有足够空间
data_allocator::construct(mystl::address_of(*end_), value);
++end_;
}
else if (end_ != cap_) {
// 中间插入且有足够空间
auto new_end = end_;
data_allocator::construct(mystl::address_of(*end_), *(end_ - 1));
++new_end;
mystl::copy_backward(xpos, end_ - 1, end_);
*xpos = value;
end_ = new_end;
}
else {
// 需要重新分配内存
reallocate_insert(xpos, value);
}
return begin() + n;
}// 链表节点基类
template <class T>
struct list_node_base {
typedef void* base_ptr;
typedef list_node_base<T>* node_ptr;
node_ptr prev; // 前驱节点
node_ptr next; // 后继节点
list_node_base() = default;
node_ptr self() { return static_cast<node_ptr>(&*this); }
void unlink() {
prev = next = self();
}
};
// 链表节点
template <class T>
struct list_node : public list_node_base<T> {
typedef list_node_base<T>* base_ptr;
typedef list_node<T>* node_ptr;
T data; // 数据域
list_node() = default;
list_node(const T& x) : data(x) {}
list_node(T&& x) : data(mystl::move(x)) {}
base_ptr as_base() { return static_cast<base_ptr>(&*this); }
node_ptr as_node() { return static_cast<node_ptr>(&*this); }
};template <class T>
struct list_iterator : public mystl::iterator<mystl::bidirectional_iterator_tag, T> {
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef typename node_traits<T>::base_ptr base_ptr;
typedef typename node_traits<T>::node_ptr node_ptr;
typedef list_iterator<T> self;
base_ptr node_; // 指向当前节点
// 构造函数
list_iterator() = default;
list_iterator(base_ptr x) : node_(x) {}
list_iterator(node_ptr x) : node_(x->as_base()) {}
list_iterator(const list_iterator& rhs) : node_(rhs.node_) {}
// 解引用操作
reference operator*() const { return node_->as_node()->data; }
pointer operator->() const { return &(operator*()); }
// 前进后退操作
self& operator++() {
MYSTL_DEBUG(node_ != nullptr);
node_ = node_->next;
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
MYSTL_DEBUG(node_ != nullptr);
node_ = node_->prev;
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
// 比较操作
bool operator==(const self& rhs) const { return node_ == rhs.node_; }
bool operator!=(const self& rhs) const { return node_ != rhs.node_; }
};splice操作（链表拼接）：
template <class T, class Alloc>
void list<T, Alloc>::splice(const_iterator pos, list& other) {
MYSTL_DEBUG(this != &other);
if (!other.empty()) {
THROW_LENGTH_ERROR_IF(size_ > max_size() - other.size_,
"list<T>'s size too big");
auto f = other.node_->next;
auto l = other.node_->prev;
other.unlink_nodes(f, l);
link_nodes(pos.node_, f, l);
size_ += other.size_;
other.size_ = 0;
}
}
// 链接节点的辅助函数
template <class T, class Alloc>
void list<T, Alloc>::link_nodes(base_ptr pos, base_ptr first, base_ptr last) {
pos->prev->next = first;
first->prev = pos->prev;
pos->prev = last;
last->next = pos;
}
// 断开节点的辅助函数
template <class T, class Alloc>
void list<T, Alloc>::unlink_nodes(base_ptr first, base_ptr last) {
first->prev->next = last->next;
last->next->prev = first->prev;
}merge操作（有序链表合并）：
template <class T, class Alloc>
template <class Compare>
void list<T, Alloc>::merge(list& x, Compare comp) {
if (this != &x) {
THROW_LENGTH_ERROR_IF(size_ > max_size() - x.size_,
"list<T>'s size too big");
auto f1 = begin();
auto l1 = end();
auto f2 = x.begin();
auto l2 = x.end();
while (f1 != l1 && f2 != l2) {
if (comp(*f2, *f1)) {
// 找到f2中连续小于*f1的元素范围
auto next = f2;
++next;
for (; next != l2 && comp(*next, *f1); ++next)
;
auto f = f2.node_;
auto l = next.node_->prev;
f2 = next;
// 将[f, l]范围的节点移动到f1之前
x.unlink_nodes(f, l);
link_nodes(f1.node_, f, l);
++f1;
}
else {
++f1;
}
}
// 如果x中还有剩余元素，全部移动到末尾
if (f2 != l2) {
auto f = f2.node_;
auto l = l2.node_->prev;
x.unlink_nodes(f, l);
link_nodes(l1.node_, f, l);
}
size_ += x.size_;
x.size_ = 0;
}
}// 红黑树节点颜色
typedef bool rb_tree_color_type;
static constexpr rb_tree_color_type rb_tree_red = false;
static constexpr rb_tree_color_type rb_tree_black = true;
// 红黑树节点基类
template <class T>
struct rb_tree_node_base {
typedef rb_tree_color_type color_type;
typedef rb_tree_node_base* base_ptr;
color_type color; // 节点颜色
base_ptr parent; // 父节点
base_ptr left; // 左子节点
base_ptr right; // 右子节点
base_ptr get_base_ptr() { return &*this; }
static base_ptr minimum(base_ptr x) {
while (x->left != nullptr) x = x->left;
return x;
}
static base_ptr maximum(base_ptr x) {
while (x->right != nullptr) x = x->right;
return x;
}
};
// 红黑树节点
template <class T>
struct rb_tree_node : public rb_tree_node_base<T> {
typedef rb_tree_node_base<T>* base_ptr;
typedef rb_tree_node<T>* node_ptr;
T value; // 节点值
base_ptr get_base_ptr() { return static_cast<base_ptr>(&*this); }
node_ptr get_node_ptr() { return &*this; }
};// 红黑树插入后的平衡调整
template <class T, class Compare>
typename rb_tree<T, Compare>::node_ptr
rb_tree<T, Compare>::rb_tree_insert_rebalance(node_ptr x, node_ptr& root) {
x->color = rb_tree_red; // 新节点为红色
while (x != root && x->parent->color == rb_tree_red) {
if (x->parent == x->parent->parent->left) {
// 父节点是祖父节点的左子节点
auto uncle = x->parent->parent->right;
if (uncle && uncle->color == rb_tree_red) {
// Case 1: 叔叔节点是红色
x->parent->color = rb_tree_black;
uncle->color = rb_tree_black;
x->parent->parent->color = rb_tree_red;
x = x->parent->parent;
}
else {
// Case 2 & 3: 叔叔节点是黑色或不存在
if (x == x->parent->right) {
// Case 2: x是右子节点，需要左旋转换为Case 3
x = x->parent;
rb_tree_rotate_left(x, root);
}
// Case 3: x是左子节点，右旋并重新着色
x->parent->color = rb_tree_black;
x->parent->parent->color = rb_tree_red;
rb_tree_rotate_right(x->parent->parent, root);
}
}
else {
// 父节点是祖父节点的右子节点（对称情况）
auto uncle = x->parent->parent->left;
if (uncle && uncle->color == rb_tree_red) {
x->parent->color = rb_tree_black;
uncle->color = rb_tree_black;
x->parent->parent->color = rb_tree_red;
x = x->parent->parent;
}
else {
if (x == x->parent->left) {
x = x->parent;
rb_tree_rotate_right(x, root);
}
x->parent->color = rb_tree_black;
x->parent->parent->color = rb_tree_red;
rb_tree_rotate_left(x->parent->parent, root);
}
}
}
root->color = rb_tree_black; // 根节点始终为黑色
return x;
}
// 左旋操作
template <class NodePtr>
void rb_tree_rotate_left(NodePtr x, NodePtr& root) {
auto y = x->right; // y是x的右子节点
x->right = y->left; // y的左子树成为x的右子树
if (y->left) {
y->left->parent = x;
}
y->parent = x->parent; // y替代x的位置
if (x == root) {
root = y;
}
else if (x == x->parent->left) {
x->parent->left = y;
}
else {
x->parent->right = y;
}
y->left = x; // x成为y的左子节点
x->parent = y;
}// 红黑树删除节点
template <class T, class Compare>
typename rb_tree<T, Compare>::node_ptr
rb_tree<T, Compare>::rb_tree_erase_rebalance(node_ptr z, node_ptr& root,
node_ptr& leftmost, node_ptr& rightmost) {
auto y = (z->left == nullptr || z->right == nullptr) ? z : rb_tree_next(z);
auto x = y->left != nullptr ? y->left : y->right;
node_ptr x_parent = nullptr;
if (x != nullptr) {
x->parent = y->parent;
}
x_parent = y->parent;
if (y == root) {
root = x;
}
else if (y == y->parent->left) {
y->parent->left = x;
}
else {
y->parent->right = x;
}
if (y != z) {
z->value = y->value; // 用y的值替换z的值
}
// 更新最左和最右节点
if (leftmost == z) {
leftmost = z->right == nullptr ? z->parent : rb_tree_node_base::minimum(x);
}
if (rightmost == z) {
rightmost = z->left == nullptr ? z->parent : rb_tree_node_base::maximum(x);
}
// 如果删除的是黑色节点，需要进行平衡调整
if (y->color == rb_tree_black) {
rb_tree_erase_rebalance_impl(x, x_parent, root);
}
return y;
}
// 删除后的平衡调整实现
template <class NodePtr>
void rb_tree_erase_rebalance_impl(NodePtr x, NodePtr x_parent, NodePtr& root) {
while (x != root && (x == nullptr || x->color == rb_tree_black)) {
if (x == x_parent->left) {
auto sibling = x_parent->right;
if (sibling->color == rb_tree_red) {
// Case 1: 兄弟节点是红色
sibling->color = rb_tree_black;
x_parent->color = rb_tree_red;
rb_tree_rotate_left(x_parent, root);
sibling = x_parent->right;
}
if ((sibling->left == nullptr || sibling->left->color == rb_tree_black) &&
(sibling->right == nullptr || sibling->right->color == rb_tree_black)) {
// Case 2: 兄弟节点的两个子节点都是黑色
sibling->color = rb_tree_red;
x = x_parent;
x_parent = x_parent->parent;
}
else {
if (sibling->right == nullptr || sibling->right->color == rb_tree_black) {
// Case 3: 兄弟节点的右子节点是黑色，左子节点是红色
if (sibling->left) sibling->left->color = rb_tree_black;
sibling->color = rb_tree_red;
rb_tree_rotate_right(sibling, root);
sibling = x_parent->right;
}
// Case 4: 兄弟节点的右子节点是红色
sibling->color = x_parent->color;
x_parent->color = rb_tree_black;
if (sibling->right) sibling->right->color = rb_tree_black;
rb_tree_rotate_left(x_parent, root);
break;
}
}
else {
// 对称情况：x是右子节点
// ... 类似的处理逻辑
}
}
if (x) x->color = rb_tree_black;
}// 基础类型萃取结构
template <class T>
struct type_traits {
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};
// 针对内置类型的特化
template <>
struct type_traits<bool> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
template <>
struct type_traits<char> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
// 指针类型的偏特化
template <class T>
struct type_traits<T*> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};// 迭代器类型萃取
template <class Iterator>
struct iterator_traits {
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
};
// 针对原生指针的特化
template <class T>
struct iterator_traits<T*> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};
template <class T>
struct iterator_traits<const T*> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef const T* pointer;
typedef const T& reference;
};
// 萃取迭代器类型的辅助函数
template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
typedef typename iterator_traits<Iterator>::iterator_category category;
return category();
}
template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type*
distance_type(const Iterator&) {
return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}
template <class Iterator>
inline typename iterator_traits<Iterator>::value_type*
value_type(const Iterator&) {
return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}// 检测类型是否为输入迭代器
template <class Iterator>
struct is_input_iterator : public m_bool_constant<
std::is_convertible<typename iterator_traits<Iterator>::iterator_category,
input_iterator_tag>::value> {};
// 检测类型是否为前向迭代器
template <class Iterator>
struct is_forward_iterator : public m_bool_constant<
std::is_convertible<typename iterator_traits<Iterator>::iterator_category,
forward_iterator_tag>::value> {};
// 检测类型是否为随机访问迭代器
template <class Iterator>
struct is_random_access_iterator : public m_bool_constant<
std::is_convertible<typename iterator_traits<Iterator>::iterator_category,
random_access_iterator_tag>::value> {};
// 使用SFINAE进行函数重载
template <class InputIter, class OutputIter>
OutputIter copy_dispatch(InputIter first, InputIter last, OutputIter result,
input_iterator_tag) {
for (; first != last; ++first, ++result) {
*result = *first;
}
return result;
}
template <class RandomIter, class OutputIter>
OutputIter copy_dispatch(RandomIter first, RandomIter last, OutputIter result,
random_access_iterator_tag) {
return copy_d(first, last, result, distance_type(first));
}
template <class InputIter, class OutputIter>
OutputIter copy(InputIter first, InputIter last, OutputIter result) {
return copy_dispatch(first, last, result, iterator_category(first));
}// 第一级分配器：直接使用malloc/free
template <int inst>
class __malloc_alloc_template {
private:
// 内存不足时的处理函数指针
static void (*__malloc_alloc_oom_handler)();
static void* oom_malloc(size_t);
static void* oom_realloc(void*, size_t);
public:
static void* allocate(size_t n) {
void* result = malloc(n);
if (0 == result) result = oom_malloc(n);
return result;
}
static void deallocate(void* p, size_t /* n */) {
free(p);
}
static void* reallocate(void* p, size_t /* old_sz */, size_t new_sz) {
void* result = realloc(p, new_sz);
if (0 == result) result = oom_realloc(p, new_sz);
return result;
}
// 设置内存不足处理函数
static void (*set_malloc_handler(void (*f)()))() {
void (*old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return old;
}
};
// 第二级分配器：内存池
template <bool threads, int inst>
class __default_alloc_template {
private:
enum { __ALIGN = 8 }; // 小型区块的上调边界
enum { __MAX_BYTES = 128 }; // 小型区块的上限
enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; // free-lists个数
// 将bytes上调至8的倍数
static size_t ROUND_UP(size_t bytes) {
return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));
}
// 根据区块大小，决定使用第n号free-list
static size_t FREELIST_INDEX(size_t bytes) {
return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
}
// free-list的节点构造
union obj {
union obj* free_list_link;
char client_data[1];
};
// 16个free-lists
static obj* volatile free_list[__NFREELISTS];
// 内存池
static char* start_free; // 内存池起始位置
static char* end_free; // 内存池结束位置
static size_t heap_size; // 堆大小
// 返回一个大小为n的对象，并可能加入大小为n的其他区块到free list
static void* refill(size_t n);
// 配置一大块空间，可容纳nobjs个大小为size的区块
static char* chunk_alloc(size_t size, int& nobjs);
public:
static void* allocate(size_t n) {
obj* volatile* my_free_list;
obj* result;
// 大于128就调用第一级配置器
if (n > (size_t)__MAX_BYTES) {
return malloc_alloc::allocate(n);
}
// 寻找16个free lists中适当的一个
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if (result == 0) {
// 没找到可用的free list，准备重新填充free list
void* r = refill(ROUND_UP(n));
return r;
}
// 调整free list
*my_free_list = result->free_list_link;
return result;
}
static void deallocate(void* p, size_t n) {
obj* q = (obj*)p;
obj* volatile* my_free_list;
// 大于128就调用第一级配置器
if (n > (size_t)__MAX_BYTES) {
malloc_alloc::deallocate(p, n);
return;
}
// 寻找对应的free list
my_free_list = free_list + FREELIST_INDEX(n);
// 调整free list，回收区块
q->free_list_link = *my_free_list;
*my_free_list = q;
}
};// 从内存池中取空间给free list使用
template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs) {
char* result;
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free; // 内存池剩余空间
if (bytes_left >= total_bytes) {
// 内存池剩余空间完全满足需求量
result = start_free;
start_free += total_bytes;
return result;
}
else if (bytes_left >= size) {
// 内存池剩余空间不能完全满足需求量，但足够供应一个（含）以上的区块
nobjs = bytes_left / size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return result;
}
else {
// 内存池剩余空间连一个区块的大小都无法提供
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
// 以下试着让内存池中的残余零头还有利用价值
if (bytes_left > 0) {
// 内存池中还有一些零头，先配给适当的free list
obj* volatile* my_free_list = free_list + FREELIST_INDEX(bytes_left);
// 调整free list，将内存池中的残余空间编入
((obj*)start_free)->free_list_link = *my_free_list;
*my_free_list = (obj*)start_free;
}
// 配置heap空间，用来补充内存池
start_free = (char*)malloc(bytes_to_get);
if (0 == start_free) {
// heap空间不足，malloc()失败
int i;
obj* volatile* my_free_list, *p;
// 试着检视我们手上拥有的东西，这不会造成伤害
// 我们不打算尝试配置较小的区块，因为那在多进程机器上容易导致灾难
// 以下搜寻适当的free list
// 所谓适当是指"尚有未用区块，且区块够大"之free list
for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (0 != p) {
// free list内尚有未用区块
// 调整free list以释出未用区块
*my_free_list = p->free_list_link;
start_free = (char*)p;
end_free = start_free + i;
// 递归调用自己，为了修正nobjs
return chunk_alloc(size, nobjs);
}
}
end_free = 0; // 如果出意外（山穷水尽，到处都没有内存可用了）
// 调用第一级配置器，看看out-of-memory机制能否尽点力
start_free = (char*)malloc_alloc::allocate(bytes_to_get);
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
// 递归调用自己，为了修正nobjs
return chunk_alloc(size, nobjs);
}
}
// 返回一个大小为n的对象，并且有时候会为适当的free list增加节点
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n) {
int nobjs = 20;
// 调用chunk_alloc()，尝试取得nobjs个区块作为free list的新节点
char* chunk = chunk_alloc(n, nobjs);
obj* volatile* my_free_list;
obj* result;
obj* current_obj, *next_obj;
int i;
// 如果只获得一个区块，这个区块就分配给调用者用，free list无新节点
if (1 == nobjs) return chunk;
// 否则准备调整free list，纳入新节点
my_free_list = free_list + FREELIST_INDEX(n);
// 以下在chunk空间内建立free list
result = (obj*)chunk; // 这一块准备返回给客端
// 以下导引free list指向新配置的空间（取自内存池）
*my_free_list = next_obj = (obj*)(chunk + n);
// 以下将free list的各节点串接起来
for (i = 1; ; i++) {
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj + n);
if (nobjs - 1 == i) {
current_obj->free_list_link = 0;
break;
} else {
current_obj->free_list_link = next_obj;
}
}
return result;
}// 快速排序的优化实现
template <class RandomIter, class T, class Compare>
void __introsort_loop(RandomIter first, RandomIter last, T*,
size_t depth_limit, Compare comp) {
// 当元素个数小于等于16时，使用插入排序
const size_t __stl_threshold = 16;
while (last - first > __stl_threshold) {
if (depth_limit == 0) {
// 递归深度过深，改用堆排序
mystl::partial_sort(first, last, last, comp);
return;
}
--depth_limit;
// 选择枢轴并进行分割
RandomIter cut = __unguarded_partition
(first, last, T(__median(*first, *(first + (last - first) / 2),
*(last - 1), comp)), comp);
// 对右半部分递归排序
__introsort_loop(cut, last, value_type(first), depth_limit, comp);
last = cut; // 现在回到while循环，对左半部分进行排序
}
}
// 三数取中法选择枢轴
template <class T, class Compare>
const T& __median(const T& a, const T& b, const T& c, Compare comp) {
if (comp(a, b)) {
if (comp(b, c)) {
return b; // a < b < c
} else if (comp(a, c)) {
return c; // a < c <= b
} else {
return a; // c <= a < b
}
} else if (comp(a, c)) {
return a; // b <= a < c
} else if (comp(b, c)) {
return c; // b < c <= a
} else {
return b; // c <= b <= a
}
}
// 分割操作
template <class RandomIter, class T, class Compare>
RandomIter __unguarded_partition(RandomIter first, RandomIter last,
T pivot, Compare comp) {
while (true) {
while (comp(*first, pivot)) ++first;
--last;
while (comp(pivot, *last)) --last;
if (!(first < last)) return first;
mystl::iter_swap(first, last);
++first;
}
}
// 插入排序（用于小数组）
template <class RandomIter, class Compare>
void __insertion_sort(RandomIter first, RandomIter last, Compare comp) {
if (first == last) return;
for (RandomIter i = first + 1; i != last; ++i) {
__linear_insert(first, i, value_type(first), comp);
}
}
template <class RandomIter, class T, class Compare>
inline void __linear_insert(RandomIter first, RandomIter last,
T*, Compare comp) {
T value = *last;
if (comp(value, *first)) {
mystl::copy_backward(first, last, last + 1);
*first = value;
} else {
__unguarded_linear_insert(last, value, comp);
}
}
// 主排序函数
template <class RandomIter, class Compare>
inline void sort(RandomIter first, RandomIter last, Compare comp) {
if (first != last) {
// 内省排序：快排+堆排+插入排序的混合
__introsort_loop(first, last, value_type(first),
__lg(last - first) * 2, comp);
__final_insertion_sort(first, last, comp);
}
}// 二分查找的优化实现
template <class ForwardIter, class T, class Compare>
ForwardIter lower_bound(ForwardIter first, ForwardIter last,
const T& value, Compare comp) {
typedef typename iterator_traits<ForwardIter>::difference_type Distance;
Distance len = mystl::distance(first, last);
Distance half;
ForwardIter middle;
while (len > 0) {
half = len >> 1; // 除以2
middle = first;
mystl::advance(middle, half);
if (comp(*middle, value)) {
first = middle;
++first;
len = len - half - 1;
} else {
len = half;
}
}
return first;
}
// 针对随机访问迭代器的特化版本
template <class RandomIter, class T, class Compare>
RandomIter __lower_bound(RandomIter first, RandomIter last,
const T& value, Compare comp,
random_access_iterator_tag) {
typedef typename iterator_traits<RandomIter>::difference_type Distance;
Distance len = last - first;
Distance half;
RandomIter middle;
while (len > 0) {
half = len >> 1;
middle = first + half;
if (comp(*middle, value)) {
first = middle + 1;
len = len - half - 1;
} else {
len = half;
}
}
return first;
}
// equal_range的实现
template <class ForwardIter, class T, class Compare>
mystl::pair<ForwardIter, ForwardIter>
equal_range(ForwardIter first, ForwardIter last, const T& value, Compare comp) {
typedef typename iterator_traits<ForwardIter>::difference_type Distance;
Distance len = mystl::distance(first, last);
Distance half;
ForwardIter middle, left, right;
while (len > 0) {
half = len >> 1;
middle = first;
mystl::advance(middle, half);
if (comp(*middle, value)) {
first = middle;
++first;
len = len - half - 1;
} else if (comp(value, *middle)) {
len = half;
} else {
// *middle == value
left = mystl::lower_bound(first, middle, value, comp);
mystl::advance(first, len);
right = mystl::upper_bound(++middle, first, value, comp);
return mystl::pair<ForwardIter, ForwardIter>(left, right);
}
}
return mystl::pair<ForwardIter, ForwardIter>(first, first);
}// RAII在容器中的应用
template <class T, class Alloc>
class vector {
private:
T* data_;
size_t size_;
size_t capacity_;
Alloc alloc_;
public:
// 构造函数中获取资源
explicit vector(size_t n) : size_(n), capacity_(n) {
data_ = alloc_.allocate(capacity_);
try {
mystl::uninitialized_fill_n(data_, size_, T());
} catch (...) {
alloc_.deallocate(data_, capacity_);
throw;
}
}
// 析构函数中释放资源
~vector() {
if (data_) {
mystl::destroy(data_, data_ + size_);
alloc_.deallocate(data_, capacity_);
}
}
// 移动构造函数：资源转移
vector(vector&& other) noexcept
: data_(other.data_), size_(other.size_),
capacity_(other.capacity_), alloc_(std::move(other.alloc_)) {
other.data_ = nullptr;
other.size_ = 0;
other.capacity_ = 0;
}
// 移动赋值操作符
vector& operator=(vector&& other) noexcept {
if (this != &other) {
// 释放当前资源
if (data_) {
mystl::destroy(data_, data_ + size_);
alloc_.deallocate(data_, capacity_);
}
// 转移资源
data_ = other.data_;
size_ = other.size_;
capacity_ = other.capacity_;
alloc_ = std::move(other.alloc_);
// 清空源对象
other.data_ = nullptr;
other.size_ = 0;
other.capacity_ = 0;
}
return *this;
}
};// 分配器策略
template <class T>
class allocator {
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
static T* allocate(size_t n) {
if (n == 0) return nullptr;
return static_cast<T*>(::operator new(n * sizeof(T)));
}
static void deallocate(T* ptr, size_t) {
if (ptr) ::operator delete(ptr);
}
};
// 内存池分配器策略
template <class T>
class pool_allocator {
private:
static memory_pool<sizeof(T)> pool_;
public:
static T* allocate(size_t n) {
if (n == 1) {
return static_cast<T*>(pool_.allocate());
}
return static_cast<T*>(::operator new(n * sizeof(T)));
}
static void deallocate(T* ptr, size_t n) {
if (n == 1) {
pool_.deallocate(ptr);
} else {
::operator delete(ptr);
}
}
};
// 比较函数策略
template <class T>
struct less {
bool operator()(const T& x, const T& y) const {
return x < y;
}
};
template <class T>
struct greater {
bool operator()(const T& x, const T& y) const {
return x > y;
}
};
// 哈希函数策略
template <class Key>
struct hash {};
template <>
struct hash<int> {
size_t operator()(int x) const {
return static_cast<size_t>(x);
}
};
template <>
struct hash<string> {
size_t operator()(const string& str) const {
size_t result = 0;
for (auto ch : str) {
result = result * 131 + ch;
}
return result;
}
};// 算法的模板方法模式
template <class InputIter, class OutputIter>
OutputIter copy(InputIter first, InputIter last, OutputIter result) {
return __copy_dispatch<InputIter, OutputIter>()(first, last, result);
}
// 根据迭代器类型选择不同的实现策略
template <class InputIter, class OutputIter>
struct __copy_dispatch {
OutputIter operator()(InputIter first, InputIter last, OutputIter result) {
return __copy(first, last, result, iterator_category(first));
}
};
// 针对指针的特化版本
template <class T>
struct __copy_dispatch<T*, T*> {
T* operator()(T* first, T* last, T* result) {
typedef typename __type_traits<T>::has_trivial_assignment_operator t;
return __copy_t(first, last, result, t());
}
};
template <class T>
struct __copy_dispatch<const T*, T*> {
T* operator()(const T* first, const T* last, T* result) {
typedef typename __type_traits<T>::has_trivial_assignment_operator t;
return __copy_t(first, last, result, t());
}
};
// 具体的实现方法
template <class InputIter, class OutputIter>
inline OutputIter __copy(InputIter first, InputIter last, OutputIter result,
input_iterator_tag) {
// 逐个元素拷贝
for (; first != last; ++result, ++first) {
*result = *first;
}
return result;
}
template <class RandomAccessIter, class OutputIter>
inline OutputIter __copy(RandomAccessIter first, RandomAccessIter last,
OutputIter result, random_access_iterator_tag) {
// 利用随机访问特性优化
return __copy_d(first, last, result, distance_type(first));
}
template <class RandomAccessIter, class OutputIter, class Distance>
inline OutputIter __copy_d(RandomAccessIter first, RandomAccessIter last,
OutputIter result, Distance*) {
for (Distance n = last - first; n > 0; --n, ++result, ++first) {
*result = *first;
}
return result;
}
// 针对POD类型的优化
template <class T>
inline T* __copy_t(const T* first, const T* last, T* result, __true_type) {
memmove(result, first, sizeof(T) * (last - first));
return result + (last - first);
}
template <class T>
inline T* __copy_t(const T* first, const T* last, T* result, __false_type) {
return __copy_d(first, last, result, (ptrdiff_t*)0);
}// 迭代器基类
template <class Category, class T, class Distance = ptrdiff_t,
class Pointer = T*, class Reference = T&>
struct iterator {
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
// vector的迭代器实现
template <class T, class Alloc>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
typedef mystl::reverse_iterator<iterator> reverse_iterator;
typedef mystl::reverse_iterator<const_iterator> const_reverse_iterator;
// 迭代器相关函数
iterator begin() noexcept { return begin_; }
const_iterator begin() const noexcept { return begin_; }
iterator end() noexcept { return end_; }
const_iterator end() const noexcept { return end_; }
reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const noexcept {
return const_reverse_iterator(end());
}
reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
const_reverse_iterator rend() const noexcept {
return const_reverse_iterator(begin());
}
const_iterator cbegin() const noexcept { return begin(); }
const_iterator cend() const noexcept { return end(); }
const_reverse_iterator crbegin() const noexcept { return rbegin(); }
const_reverse_iterator crend() const noexcept { return rend(); }
};
// list的迭代器实现
template <class T>
struct list_iterator : public mystl::iterator<mystl::bidirectional_iterator_tag, T> {
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef typename node_traits<T>::base_ptr base_ptr;
typedef typename node_traits<T>::node_ptr node_ptr;
typedef list_iterator<T> self;
base_ptr node_;
// 构造函数
list_iterator() = default;
list_iterator(base_ptr x) : node_(x) {}
list_iterator(node_ptr x) : node_(x->as_base()) {}
list_iterator(const list_iterator& rhs) : node_(rhs.node_) {}
// 解引用操作
reference operator*() const { return node_->as_node()->data; }
pointer operator->() const { return &(operator*()); }
// 前进后退操作
self& operator++() {
MYSTL_DEBUG(node_ != nullptr);
node_ = node_->next;
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
MYSTL_DEBUG(node_ != nullptr);
node_ = node_->prev;
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
// 比较操作
bool operator==(const self& rhs) const { return node_ == rhs.node_; }
bool operator!=(const self& rhs) const { return node_ != rhs.node_; }
};
// 反向迭代器的实现
template <class Iterator>
class reverse_iterator {
protected:
Iterator current; // 对应的正向迭代器
public:
typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
typedef typename iterator_traits<Iterator>::value_type value_type;
typedef typename iterator_traits<Iterator>::difference_type difference_type;
typedef typename iterator_traits<Iterator>::pointer pointer;
typedef typename iterator_traits<Iterator>::reference reference;
typedef Iterator iterator_type;
typedef reverse_iterator<Iterator> self;
public:
// 构造函数
reverse_iterator() {}
explicit reverse_iterator(iterator_type x) : current(x) {}
reverse_iterator(const self& x) : current(x.current) {}
template <class Iter>
reverse_iterator(const reverse_iterator<Iter>& x) : current(x.base()) {}
// 获取底层迭代器
iterator_type base() const { return current; }
// 解引用操作
reference operator*() const {
Iterator tmp = current;
return *--tmp; // 关键：反向迭代器的*操作对应正向迭代器的前一个位置
}
pointer operator->() const {
return &(operator*());
}
// 前进后退操作（注意方向相反）
self& operator++() {
--current; // 反向迭代器的++对应正向迭代器的--
return *this;
}
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
self& operator--() {
++current; // 反向迭代器的--对应正向迭代器的++
return *this;
}
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}
// 随机访问操作
self operator+(difference_type n) const {
return self(current - n);
}
self& operator+=(difference_type n) {
current -= n;
return *this;
}
self operator-(difference_type n) const {
return self(current + n);
}
self& operator-=(difference_type n) {
current += n;
return *this;
}
reference operator[](difference_type n) const {
return *(*this + n);
}
// 比较操作
bool operator==(const self& rhs) const { return current == rhs.current; }
bool operator!=(const self& rhs) const { return current != rhs.current; }
bool operator<(const self& rhs) const { return rhs.current < current; }
bool operator>(const self& rhs) const { return rhs.current > current; }
bool operator<=(const self& rhs) const { return !(rhs < *this); }
bool operator>=(const self& rhs) const { return !(*this < rhs); }
};// 全局构造函数
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
new (p) T1(value); // placement new
}
template <class T>
inline void construct(T* p) {
new (p) T();
}
// C++11移动构造支持
template <class T1, class T2>
inline void construct(T1* p, T2&& value) {
new (p) T1(mystl::forward<T2>(value));
}
// 可变参数模板构造
template <class T, class... Args>
inline void construct(T* p, Args&&... args) {
new (p) T(mystl::forward<Args>(args)...);
}
// 全局析构函数
template <class T>
inline void destroy(T* pointer) {
pointer->~T();
}
// 范围析构 - 根据类型特性优化
template <class ForwardIter>
inline void destroy(ForwardIter first, ForwardIter last) {
__destroy(first, last, value_type(first));
}
template <class ForwardIter, class T>
inline void __destroy(ForwardIter first, ForwardIter last, T*) {
typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
__destroy_aux(first, last, trivial_destructor());
}
// 对于有非平凡析构函数的类型
template <class ForwardIter>
inline void __destroy_aux(ForwardIter first, ForwardIter last, __false_type) {
for (; first != last; ++first) {
destroy(&*first);
}
}
// 对于有平凡析构函数的类型（如内置类型），什么都不做
template <class ForwardIter>
inline void __destroy_aux(ForwardIter, ForwardIter, __true_type) {}
// 针对指针的特化版本
inline void destroy(char*, char*) {}
inline void destroy(int*, int*) {}
inline void destroy(long*, long*) {}
inline void destroy(float*, float*) {}
inline void destroy(double*, double*) {}// 未初始化内存的拷贝
template <class InputIter, class ForwardIter>
ForwardIter uninitialized_copy(InputIter first, InputIter last, ForwardIter result) {
return __uninitialized_copy(first, last, result, value_type(result));
}
template <class InputIter, class ForwardIter, class T>
ForwardIter __uninitialized_copy(InputIter first, InputIter last,
ForwardIter result, T*) {
typedef typename __type_traits<T>::is_POD_type is_POD;
return __uninitialized_copy_aux(first, last, result, is_POD());
}
// 对于POD类型，直接使用高效的内存拷贝
template <class InputIter, class ForwardIter>
ForwardIter __uninitialized_copy_aux(InputIter first, InputIter last,
ForwardIter result, __true_type) {
return mystl::copy(first, last, result);
}
// 对于非POD类型，需要调用构造函数
template <class InputIter, class ForwardIter>
ForwardIter __uninitialized_copy_aux(InputIter first, InputIter last,
ForwardIter result, __false_type) {
ForwardIter cur = result;
try {
for (; first != last; ++first, ++cur) {
construct(&*cur, *first);
}
return cur;
}
catch (...) {
// 异常安全：销毁已构造的对象
destroy(result, cur);
throw;
}
}
// 未初始化内存的填充
template <class ForwardIter, class T>
void uninitialized_fill(ForwardIter first, ForwardIter last, const T& x) {
__uninitialized_fill(first, last, x, value_type(first));
}
template <class ForwardIter, class T, class T1>
void __uninitialized_fill(ForwardIter first, ForwardIter last,
const T& x, T1*) {
typedef typename __type_traits<T1>::is_POD_type is_POD;
__uninitialized_fill_aux(first, last, x, is_POD());
}
template <class ForwardIter, class T>
void __uninitialized_fill_aux(ForwardIter first, ForwardIter last,
const T& x, __true_type) {
mystl::fill(first, last, x);
}
template <class ForwardIter, class T>
void __uninitialized_fill_aux(ForwardIter first, ForwardIter last,
const T& x, __false_type) {
ForwardIter cur = first;
try {
for (; cur != last; ++cur) {
construct(&*cur, x);
}
}
catch (...) {
destroy(first, cur);
throw;
}
}
// 未初始化内存的填充n个元素
template <class ForwardIter, class Size, class T>
ForwardIter uninitialized_fill_n(ForwardIter first, Size n, const T& x) {
return __uninitialized_fill_n(first, n, x, value_type(first));
}
template <class ForwardIter, class Size, class T, class T1>
ForwardIter __uninitialized_fill_n(ForwardIter first, Size n,
const T& x, T1*) {
typedef typename __type_traits<T1>::is_POD_type is_POD;
return __uninitialized_fill_n_aux(first, n, x, is_POD());
}
template <class ForwardIter, class Size, class T>
ForwardIter __uninitialized_fill_n_aux(ForwardIter first, Size n,
const T& x, __true_type) {
return mystl::fill_n(first, n, x);
}
template <class ForwardIter, class Size, class T>
ForwardIter __uninitialized_fill_n_aux(ForwardIter first, Size n,
const T& x, __false_type) {
ForwardIter cur = first;
try {
for (; n > 0; --n, ++cur) {
construct(&*cur, x);
}
return cur;
}
catch (...) {
destroy(first, cur);
throw;
}
}MyTinySTL实现了三个层次的异常安全保证：
// 异常安全的vector实现示例
template <class T, class Alloc>
void vector<T, Alloc>::push_back(const value_type& value) {
if (end_ != cap_) {
// 有足够空间，提供强异常安全保证
data_allocator::construct(mystl::address_of(*end_), value);
++end_;
}
else {
// 需要重新分配，可能抛出异常
reallocate_insert(end_, value);
}
}
template <class T, class Alloc>
void vector<T, Alloc>::reallocate_insert(iterator pos, const value_type& value) {
const auto new_size = get_new_cap(1);
auto new_begin = data_allocator::allocate(new_size);
auto new_end = new_begin;
try {
// 第一阶段：拷贝插入点之前的元素
new_end = mystl::uninitialized_move_if_noexcept(begin_, pos, new_begin);
// 第二阶段：构造新元素
data_allocator::construct(mystl::address_of(*new_end), value);
++new_end;
// 第三阶段：拷贝插入点之后的元素
new_end = mystl::uninitialized_move_if_noexcept(pos, end_, new_end);
}
catch (...) {
// 异常处理：清理已分配的资源
data_allocator::deallocate(new_begin, new_size);
throw; // 重新抛出异常，提供强异常安全保证
}
// 所有操作成功后才修改对象状态
destroy_and_recover(begin_, end_, cap_ - begin_);
begin_ = new_begin;
end_ = new_end;
cap_ = new_begin + new_size;
}
// 移动语义的异常安全版本
template <class InputIter, class ForwardIter>
ForwardIter uninitialized_move_if_noexcept(InputIter first, InputIter last,
ForwardIter result) {
return mystl::uninitialized_copy(mystl::make_move_if_noexcept_iterator(first),
mystl::make_move_if_noexcept_iterator(last),
result);
}
template <class Iter>
auto make_move_if_noexcept_iterator(Iter i)
-> typename std::conditional<
!std::is_nothrow_move_constructible<typename std::iterator_traits<Iter>::value_type>::value
&& std::is_copy_constructible<typename std::iterator_traits<Iter>::value_type>::value,
Iter,
std::move_iterator<Iter>>::type {
return i;
}// 简单的RAII包装器
template <class T, class Deleter = std::default_delete<T>>
class unique_ptr {
private:
T* ptr_;
Deleter deleter_;
public:
// 构造函数
constexpr unique_ptr() noexcept : ptr_(nullptr) {}
explicit unique_ptr(T* p) noexcept : ptr_(p) {}
unique_ptr(T* p, const Deleter& d) noexcept : ptr_(p), deleter_(d) {}
unique_ptr(T* p, Deleter&& d) noexcept : ptr_(p), deleter_(std::move(d)) {}
// 移动构造
unique_ptr(unique_ptr&& u) noexcept
: ptr_(u.release()), deleter_(std::move(u.deleter_)) {}
// 禁止拷贝
unique_ptr(const unique_ptr&) = delete;
unique_ptr& operator=(const unique_ptr&) = delete;
// 析构函数
~unique_ptr() {
if (ptr_) deleter_(ptr_);
}
// 移动赋值
unique_ptr& operator=(unique_ptr&& u) noexcept {
if (this != &u) {
reset(u.release());
deleter_ = std::move(u.deleter_);
}
return *this;
}
// 访问操作
T& operator*() const { return *ptr_; }
T* operator->() const noexcept { return ptr_; }
T* get() const noexcept { return ptr_; }
// 修改操作
T* release() noexcept {
T* result = ptr_;
ptr_ = nullptr;
return result;
}
void reset(T* ptr = nullptr) noexcept {
T* old_ptr = ptr_;
ptr_ = ptr;
if (old_ptr) deleter_(old_ptr);
}
void swap(unique_ptr& other) noexcept {
std::swap(ptr_, other.ptr_);
std::swap(deleter_, other.deleter_);
}
// 布尔转换
explicit operator bool() const noexcept {
return ptr_ != nullptr;
}
};
// 异常安全的临时对象管理
template <class T>
class temp_buffer {
private:
T* buffer_;
std::size_t size_;
std::size_t capacity_;
public:
temp_buffer(std::size_t n) : buffer_(nullptr), size_(0), capacity_(0) {
try {
buffer_ = static_cast<T*>(std::malloc(n * sizeof(T)));
if (buffer_) capacity_ = n;
} catch (...) {
buffer_ = nullptr;
capacity_ = 0;
}
}
~temp_buffer() {
if (buffer_) {
// 销毁已构造的对象
for (std::size_t i = 0; i < size_; ++i) {
(buffer_ + i)->~T();
}
std::free(buffer_);
}
}
T* begin() { return buffer_; }
T* end() { return buffer_ + size_; }
std::size_t size() const { return size_; }
std::size_t capacity() const { return capacity_; }
void push_back(const T& value) {
if (size_ < capacity_) {
new (buffer_ + size_) T(value);
++size_;
}
}
// 禁止拷贝和赋值
temp_buffer(const temp_buffer&) = delete;
temp_buffer& operator=(const temp_buffer&) = delete;
};// 编译期常量表达式
template <class T>
constexpr bool is_power_of_two(T n) {
return n > 0 && (n & (n - 1)) == 0;
}
// 编译期递归计算
template <int N>
struct factorial {
static constexpr int value = N * factorial<N - 1>::value;
};
template <>
struct factorial<0> {
static constexpr int value = 1;
};
// 编译期类型选择
template <bool B, class T, class F>
struct conditional {
typedef T type;
};
template <class T, class F>
struct conditional<false, T, F> {
typedef F type;
};
// 基于编译期信息的优化
template <class Iterator>
typename iterator_traits<Iterator>::difference_type
distance_impl(Iterator first, Iterator last, std::input_iterator_tag) {
typename iterator_traits<Iterator>::difference_type n = 0;
while (first != last) {
++first;
++n;
}
return n;
}
template <class Iterator>
typename iterator_traits<Iterator>::difference_type
distance_impl(Iterator first, Iterator last, std::random_access_iterator_tag) {
return last - first; // O(1)时间复杂度
}
template <class Iterator>
typename iterator_traits<Iterator>::difference_type
distance(Iterator first, Iterator last) {
return distance_impl(first, last,
typename iterator_traits<Iterator>::iterator_category());
}// 缓存友好的数据结构设计
template <class T, std::size_t BlockSize = 4096>
class deque {
private:
static constexpr std::size_t buffer_size() {
return BlockSize / sizeof(T) < 1 ? 1 : BlockSize / sizeof(T);
}
typedef T* pointer;
typedef T** map_pointer;
map_pointer map_; // 指向缓冲区指针数组
std::size_t map_size_; // map数组的大小
iterator start_; // 第一个缓冲区的第一个元素
iterator finish_; // 最后一个缓冲区的最后一个元素的下一个位置
public:
// 预分配策略减少内存分配次数
void reserve_map_at_back(std::size_t nodes_to_add = 1) {
if (nodes_to_add + 1 > map_size_ - (finish_.node - map_)) {
reallocate_map(nodes_to_add, false);
}
}
void reserve_map_at_front(std::size_t nodes_to_add = 1) {
if (nodes_to_add > start_.node - map_) {
reallocate_map(nodes_to_add, true);
}
}
private:
void reallocate_map(std::size_t nodes_to_add, bool add_at_front) {
std::size_t old_num_nodes = finish_.node - start_.node + 1;
std::size_t new_num_nodes = old_num_nodes + nodes_to_add;
map_pointer new_nstart;
if (map_size_ > 2 * new_num_nodes) {
// map空间足够，只需要调整位置
new_nstart = map_ + (map_size_ - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
if (new_nstart < start_.node) {
std::copy(start_.node, finish_.node + 1, new_nstart);
} else {
std::copy_backward(start_.node, finish_.node + 1,
new_nstart + old_num_nodes);
}
} else {
// 需要重新分配map
std::size_t new_map_size = map_size_ +
std::max(map_size_, nodes_to_add) + 2;
map_pointer new_map = allocate_map(new_map_size);
new_nstart = new_map + (new_map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
std::copy(start_.node, finish_.node + 1, new_nstart);
deallocate_map(map_, map_size_);
map_ = new_map;
map_size_ = new_map_size;
}
start_.set_node(new_nstart);
finish_.set_node(new_nstart + old_num_nodes - 1);
}
};
// 内存预取优化
template <class ForwardIter, class T>
void prefetch_range(ForwardIter first, ForwardIter last, const T&) {
constexpr std::size_t cache_line_size = 64;
constexpr std::size_t prefetch_distance = cache_line_size / sizeof(T);
for (auto it = first; it != last; ++it) {
if (std::distance(first, it) % prefetch_distance == 0) {
__builtin_prefetch(&*it, 0, 3); // GCC内置预取指令
}
}
}// 快速排序的优化版本
template <class RandomIter, class Compare>
void optimized_sort(RandomIter first, RandomIter last, Compare comp) {
typedef typename iterator_traits<RandomIter>::difference_type difference_type;
const difference_type threshold = 16; // 小数组阈值
const difference_type size = last - first;
if (size <= 1) return;
if (size <= threshold) {
// 小数组使用插入排序
insertion_sort(first, last, comp);
} else {
// 大数组使用内省排序
const difference_type depth_limit = 2 * log2_floor(size);
introsort_loop(first, last, comp, depth_limit);
// 最后使用插入排序处理几乎有序的数组
if (size > threshold) {
insertion_sort(first, first + threshold, comp);
unguarded_insertion_sort(first + threshold, last, comp);
} else {
insertion_sort(first, last, comp);
}
}
}
// 三路快排处理重复元素
template <class RandomIter, class Compare>
void three_way_quicksort(RandomIter first, RandomIter last, Compare comp) {
if (first >= last) return;
auto pivot = *first;
auto lt = first; // [first, lt) < pivot
auto gt = last - 1; // (gt, last) > pivot
auto i = first; // [lt, i) == pivot
while (i <= gt) {
if (comp(*i, pivot)) {
std::iter_swap(lt++, i++);
} else if (comp(pivot, *i)) {
std::iter_swap(i, gt--);
} else {
++i;
}
}
// 递归排序小于和大于pivot的部分
three_way_quicksort(first, lt, comp);
three_way_quicksort(gt + 1, last, comp);
}
// 并行归并排序
template <class RandomIter, class Compare>
void parallel_merge_sort(RandomIter first, RandomIter last, Compare comp) {
const auto size = std::distance(first, last);
const auto threshold = 1000; // 并行阈值
if (size <= threshold) {
std::sort(first, last, comp);
return;
}
auto mid = first + size / 2;
// 并行执行两个子任务
auto future1 = std::async(std::launch::async, [=]() {
parallel_merge_sort(first, mid, comp);
});
parallel_merge_sort(mid, last, comp);
future1.wait();
// 合并结果
std::inplace_merge(first, mid, last, comp);
}
// SIMD优化的向量操作
template <class T>
void vectorized_copy(const T* src, T* dst, std::size_t count) {
static_assert(std::is_trivially_copyable_v<T>, "T must be trivially copyable");
if constexpr (sizeof(T) == 4 && alignof(T) >= 4) {
// 使用SSE指令集优化32位数据拷贝
const std::size_t simd_count = count / 4;
const std::size_t remainder = count % 4;
for (std::size_t i = 0; i < simd_count; ++i) {
__m128i data = _mm_loadu_si128(reinterpret_cast<const __m128i*>(src + i * 4));
_mm_storeu_si128(reinterpret_cast<__m128i*>(dst + i * 4), data);
}
// 处理剩余元素
std::copy(src + simd_count * 4, src + count, dst + simd_count * 4);
} else {
// 回退到标准拷贝
std::copy(src, src + count, dst);
}
}// 圈复杂度分析示例
template <class T, class Alloc>
typename vector<T, Alloc>::iterator
vector<T, Alloc>::insert(const_iterator pos, const value_type& value) {
// 圈复杂度: 4 (有4个判断分支)
MYSTL_DEBUG(pos >= begin() && pos <= end()); // +0 (断言不计入)
iterator xpos = const_cast<iterator>(pos);
const size_type n = xpos - begin_;
if (end_ != cap_ && xpos == end_) { // +1
// 分支1: 在末尾插入且有足够空间
data_allocator::construct(mystl::address_of(*end_), value);
++end_;
}
else if (end_ != cap_) { // +1
// 分支2: 中间插入且有足够空间
auto new_end = end_;
data_allocator::construct(mystl::address_of(*end_), *(end_ - 1));
++new_end;
mystl::copy_backward(xpos, end_ - 1, end_);
*xpos = value;
end_ = new_end;
}
else { // +1
// 分支3: 需要重新分配内存
reallocate_insert(xpos, value);
}
return begin() + n;
}
// 认知复杂度较高的函数重构示例
// 重构前：认知复杂度过高
template <class T, class Compare>
void complex_sort_old(T* arr, int n, Compare comp) {
for (int i = 0; i < n - 1; ++i) { // +1 (循环)
for (int j = 0; j < n - i - 1; ++j) { // +2 (嵌套循环)
if (comp(arr[j + 1], arr[j])) { // +3 (嵌套条件)
if (arr[j] != arr[j + 1]) { // +4 (嵌套条件)
std::swap(arr[j], arr[j + 1]);
if (j > 0 && comp(arr[j], arr[j - 1])) { // +5 (嵌套条件)
// 更多嵌套逻辑...
}
}
}
}
}
}
// 重构后：降低认知复杂度
template <class T, class Compare>
void complex_sort_new(T* arr, int n, Compare comp) {
for (int i = 0; i < n - 1; ++i) {
bubble_pass(arr, n - i, comp); // 提取函数降低复杂度
}
}
template <class T, class Compare>
void bubble_pass(T* arr, int n, Compare comp) {
for (int j = 0; j < n - 1; ++j) {
if (should_swap(arr[j], arr[j + 1], comp)) {
perform_swap(arr, j);
}
}
}
template <class T, class Compare>
bool should_swap(const T& a, const T& b, Compare comp) {
return comp(b, a) && a != b;
}
template <class T>
void perform_swap(T* arr, int index) {
std::swap(arr[index], arr[index + 1]);
}// 内存使用效率分析
template <class T>
class memory_efficient_vector {
private:
// 使用位域优化小对象存储
struct control_block {
std::uint32_t size_ : 24; // 支持最大16M元素
std::uint32_t is_small_ : 1; // 是否使用小对象优化
std::uint32_t reserved_ : 7; // 保留位
};
static constexpr std::size_t small_capacity =
(sizeof(void*) * 2 - sizeof(control_block)) / sizeof(T);
control_block control_;
union storage {
struct {
T* data_;
std::size_t capacity_;
} large_;
alignas(T) char small_[small_capacity * sizeof(T)];
storage() {}
~storage() {}
} storage_;
public:
// 内存使用统计
std::size_t memory_usage() const {
if (control_.is_small_) {
return sizeof(*this);
} else {
return sizeof(*this) + storage_.large_.capacity_ * sizeof(T);
}
}
// 内存效率比率
double memory_efficiency() const {
std::size_t useful_memory = size() * sizeof(T);
std::size_t total_memory = memory_usage();
return static_cast<double>(useful_memory) / total_memory;
}
};
// 内存池使用统计
class memory_pool_stats {
private:
std::atomic<std::size_t> total_allocated_{0};
std::atomic<std::size_t> total_deallocated_{0};
std::atomic<std::size_t> peak_usage_{0};
std::atomic<std::size_t> current_usage_{0};
public:
void record_allocation(std::size_t size) {
total_allocated_.fetch_add(size, std::memory_order_relaxed);
std::size_t current = current_usage_.fetch_add(size, std::memory_order_relaxed) + size;
// 更新峰值使用量
std::size_t expected = peak_usage_.load(std::memory_order_relaxed);
while (current > expected &&
!peak_usage_.compare_exchange_weak(expected, current, std::memory_order_relaxed)) {
// 重试直到成功更新峰值
}
}
void record_deallocation(std::size_t size) {
total_deallocated_.fetch_add(size, std::memory_order_relaxed);
current_usage_.fetch_sub(size, std::memory_order_relaxed);
}
// 获取统计信息
struct stats {
std::size_t total_allocated;
std::size_t total_deallocated;
std::size_t peak_usage;
std::size_t current_usage;
double fragmentation_ratio;
};
stats get_stats() const {
return {
total_allocated_.load(std::memory_order_relaxed),
total_deallocated_.load(std::memory_order_relaxed),
peak_usage_.load(std::memory_order_relaxed),
current_usage_.load(std::memory_order_relaxed),
calculate_fragmentation()
};
}
private:
double calculate_fragmentation() const {
// 简化的碎片率计算
std::size_t current = current_usage_.load(std::memory_order_relaxed);
std::size_t peak = peak_usage_.load(std::memory_order_relaxed);
return peak > 0 ? 1.0 - static_cast<double>(current) / peak : 0.0;
}
};// 性能测试框架
template <class Container>
class container_benchmark {
private:
std::chrono::high_resolution_clock::time_point start_time_;
std::vector<double> measurements_;
public:
void start_timer() {
start_time_ = std::chrono::high_resolution_clock::now();
}
void end_timer() {
auto end_time = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(
end_time - start_time_).count();
measurements_.push_back(duration);
}
// 插入性能测试
void benchmark_insert(std::size_t n) {
Container container;
start_timer();
for (std::size_t i = 0; i < n; ++i) {
container.push_back(i);
}
end_timer();
}
// 随机访问性能测试
void benchmark_random_access(Container& container, std::size_t iterations) {
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, container.size() - 1);
start_timer();
volatile auto sum = 0; // 防止编译器优化
for (std::size_t i = 0; i < iterations; ++i) {
sum += container[dis(gen)];
}
end_timer();
}
// 迭代器遍历性能测试
void benchmark_iteration(const Container& container) {
start_timer();
volatile auto sum = 0;
for (const auto& item : container) {
sum += item;
}
end_timer();
}
// 统计结果
struct benchmark_result {
double mean;
double median;
double std_dev;
double min;
double max;
};
benchmark_result get_statistics() const {
if (measurements_.empty()) {
return {0, 0, 0, 0, 0};
}
auto sorted = measurements_;
std::sort(sorted.begin(), sorted.end());
double sum = std::accumulate(sorted.begin(), sorted.end(), 0.0);
double mean = sum / sorted.size();
double median = sorted.size() % 2 == 0
? (sorted[sorted.size() / 2 - 1] + sorted[sorted.size() / 2]) / 2.0
: sorted[sorted.size() / 2];
double variance = 0.0;
for (double measurement : sorted) {
variance += (measurement - mean) * (measurement - mean);
}
double std_dev = std::sqrt(variance / sorted.size());
return {mean, median, std_dev, sorted.front(), sorted.back()};
}
};
// 使用示例
void run_performance_tests() {
container_benchmark<mystl::vector<int>> vec_bench;
container_benchmark<std::vector<int>> std_vec_bench;
const std::size_t test_size = 100000;
const std::size_t iterations = 10;
// 测试插入性能
for (std::size_t i = 0; i < iterations; ++i) {
vec_bench.benchmark_insert(test_size);
std_vec_bench.benchmark_insert(test_size);
}
auto mystl_stats = vec_bench.get_statistics();
auto std_stats = std_vec_bench.get_statistics();
std::cout << "MyTinySTL vector insert: " << mystl_stats.mean << " μs\n";
std::cout << "std::vector insert: " << std_stats.mean << " μs\n";
std::cout << "Performance ratio: " << std_stats.mean / mystl_stats.mean << "\n";
}通过以上详细的代码阅读与理解分析，我们可以看到MyTinySTL项目在以下方面展现了高质量的设计和实现：
这些分析为后续的缺陷发现、性能优化和功能扩展提供了坚实的基础。