代码来源:
项目介绍
MyTinySTL 是一个简化版的 STL 项目。因为本人能力有限，直接阅读 STL 项目，对于一些 cpp 特性，还有复杂代码的处理不是很娴熟，所以选择了这样一个项目当作自己第一个读源码进行分析的项目。
项目架构
整个项目可以分为下面几个大类：
- 容器：定义好的常用数据结构
- 迭代器：遍历容器的元素，根据不同容器使用了不同算法，实际装元素的东西
- 算法：定义好的常用算法集合
- 空间配置器：管理空间分配
他们之间的关系如下
大类介绍
算法
该类定义了一些函数类和一些算法函数,函数类的类图如下:
这些类都是使用的 struct,作者似乎只是想用来当作一个函数使用,但是函数直接有一定联系,为了抽象,便分成了一元和二元函数.
每个类中只是重载了 () 运算符,使得调用这个类可以以类似函数的方法调用。对于用户来说,似乎就是函数,但是因为抽象了一层,使得能以多态的方式传递,并且不需要传递函数指针,甚至能成为其他类的成员变量。
例如:
// 选择函数：接受一个 pair，返回第二个元素
template <class Pair>
struct selectsecond :public unarg_function<Pair, typename Pair::second_type>
{
const typename Pair::second_type& operator()(const Pair& x) const
{
return x.second;
}
};另外则定义了一些算法函数，以供迭代器和函数类调用。
迭代器
迭代器主要定义在iterator.h中,类图如下:
迭代器中主要分成两个大部分:
迭代器类
xxx_iterator_tag 可以看成对 iterator 行为的分类,iterator 才是真正的迭代器, 通过判断迭代器的类型,调用不同的方法来前进,后退,获得距离等。这样就将所有不同的迭代器抽象为 iterator 类,将行为和类解耦。
例如:
// distance 的 input_iterator_tag 的版本
template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance_dispatch(InputIterator first, InputIterator last, input_iterator_tag)
{
typename iterator_traits<InputIterator>::difference_type n = 0;
while (first != last)
{
++first;
++n;
}
return n;
}
// distance 的 random_access_iterator_tag 的版本
template <class RandomIter>
typename iterator_traits<RandomIter>::difference_type
distance_dispatch(RandomIter first, RandomIter last,
random_access_iterator_tag)
{
return last - first;
}函数重写,通过输入的 iterator_category 来确定到底使用哪一个函数。
萃取迭代器类
该类主要用于提取迭代器类的种类
该类的意义在于用户如果需要创建一个迭代器 class,那么,传递一个 iterator 的 struct 就能完成创建,在 class 会使用 trait 来获取迭代器的种类,确定行为。这样，就不需要建立多个 class,用于只需要通过 xxx_iterator_tag 的拼接,则可以完成五种迭代器的创建,至于细节则和 xxx_iterator_tag 绑定,更加的抽象。
整体的类图如下：
容器
该项目中的容器大概有如下几种：
- 序列容器:随机访问
- basic_string:字符串
- vector:可变长数组
- list:链表
- heap:堆
- stack:栈
- queue:队列
- priority_queue:优先队列,使用堆优化
- deque:双向队列
- 关联容器:key - value 访问
- rb_tree:红黑树
- hashtable:哈希表，使用开链法处理冲突
- set:集合，键值即实值，集合内元素会自动排序，键值不允许重复
- multiset:集合，键值即实值，集合内元素会自动排序，键值允许重复
- unordered_set:功能与用法与 set 类似，不同的是使用 hashtable 作为底层实现机制，容器中的元素不会自动排序
- unordered_multiset:功能与用法与 multiset 类似，不同的是使用 hashtable 作为底层实现机制，容器中的元素不会自动排序
- map:映射，元素具有键值和实值，会根据键值大小自动排序，键值不允许重复
- multimap:映射，元素具有键值和实值，会根据键值大小自动排序，键值允许重复
- unordered_map:功能与用法与 map 类似，不同的是使用 hashtable 作为底层实现机制，容器内的元素不会自动排序
- unordered_multimap:功能与用法与 multimap 类似，不同的是使用 hashtable 作为底层实现机制，容器内的元素不会自动排序
其中特别介绍一下 basic_string
basic_string
看看源代码:
namespace mystl
{
using string = mystl::basic_string<char>;
using wstring = mystl::basic_string<wchar_t>;
using u16string = mystl::basic_string<char16_t>;
using u32string = mystl::basic_string<char32_t>;
}可见,对于不同大小的字符类型,通过模板类的方式赋给 basic_string,这样不同的字符串的行为被抽象统一起来,具体内存大小之类的通过字符类型决定,最后影响的是空间配置器来管理内存,实现了解耦。
容器类中的容器之间没有继承关系，类图如下：
构造析构
容器类中基本都有构造函数,copy 构造函数。
例如 deque 的构造
public:
// 构造、复制、移动、析构函数
deque() //默认构造
{ fill_init(0, value_type()); }
explicit deque(size_type n) //禁止隐式类型转换的带参构造
{ fill_init(n, value_type()); }
deque(size_type n, const value_type& value) //带参构造,pass by reference
{ fill_init(n, value); }
template <class IIter, typename std::enable_if<
mystl::is_input_iterator<IIter>::value, int>::type = 0>
deque(IIter first, IIter last) // 使用 Iterator 的构造
{ copy_init(first, last, iterator_category(first)); }
deque(std::initializer_list<value_type> ilist) //使用 list 的构造
{
copy_init(ilist.begin(), ilist.end(), mystl::forward_iterator_tag());
}
deque(const deque& rhs) // copy 构造 && pass by reference
{
copy_init(rhs.begin(), rhs.end(), mystl::forward_iterator_tag());
}
deque(deque&& rhs) noexcept
:begin_(mystl::move(rhs.begin_)),
end_(mystl::move(rhs.end_)),
map_(rhs.map_),
map_size_(rhs.map_size_)
{
rhs.map_ = nullptr;
rhs.map_size_ = 0;
}例如 deque 的析构:
~deque()
{
if (map_ != nullptr)
{
clear();
data_allocator::deallocate(*begin_.node, buffer_size);
*begin_.node = nullptr;
map_allocator::deallocate(map_, map_size_);
map_ = nullptr;
}
}重载
容器类基本重载了运算符,特别是很多都重载了 == 运算符
// deque 的重载
bool operator==(const deque<T>& lhs, const deque<T>& rhs)
{
return lhs.size() == rhs.size() &&
mystl::equal(lhs.begin(), lhs.end(), rhs.begin());
}
// list 的重载
bool operator==(const self& rhs) const { return node_ == rhs.node_; }
// map 的重载
bool operator==(const multimap<Key, T, Compare>& lhs, const multimap<Key, T, Compare>& rhs)
{
return lhs == rhs;
}另外,仍有不少类重载了 = 运算符,以处理自我赋值。
// list 中对 = 的重载
list& operator=(const list& rhs)
{
if (this != &rhs)
{
assign(rhs.begin(), rhs.end());
}
return *this;
}
list& operator=(list&& rhs) noexcept
{
clear();
splice(end(), rhs);
return *this;
}
list& operator=(std::initializer_list<T> ilist)
{
list tmp(ilist.begin(), ilist.end());
swap(tmp);
return *this;
}空间配置器
空间配置器只有一个类,那就是 allocator 类。
首先，对于构造函数进行了重写，见下列代码：
template <class Ty>
void construct(Ty* ptr)
{
::new ((void*)ptr) Ty();
}可见调用的不是 new 而是 ::new, 这样调用的是 operator new 而不是 new 关键字。operator new 是可以自己重载的，这样就实现了内存管理的自我控制。
那么，回到 allocator 类
template <class T>
void allocator<T>::construct(T* ptr)
{
mystl::construct(ptr);
}可见,这里的 allocator 类调用了刚才写的 construct 方法。
这里我们拿 deque 来举例.我们观察其默认构造函数
deque()
{ fill_init(0, value_type()); }可见调用了一个叫做 fill_init 的函数,这个函数的定义为:
fill_init(size_type n, const value_type& value)
{
map_init(n);
if (n != 0)
{
for (auto cur = begin_.node; cur < end_.node; ++cur)
{
mystl::uninitialized_fill(*cur, *cur + buffer_size, value);
}
mystl::uninitialized_fill(end_.first, end_.cur, value);
}
}这个 mystl::uninitialized_fill 的定义如下
void uninitialized_fill(ForwardIter first, ForwardIter last, const T& value)
{
mystl::unchecked_uninit_fill(first, last, value,
std::is_trivially_copy_assignable<
typename iterator_traits<ForwardIter>::
value_type>{});
}最后可见 mystl::unchecked_uninit_fill 函数
template <class ForwardIter, class T>
void
unchecked_uninit_fill(ForwardIter first, ForwardIter last, const T& value, std::false_type)
{
auto cur = first;
try
{
for (; cur != last; ++cur)
{
mystl::construct(&*cur, value);
}
}
catch (...)
{
for (;first != cur; ++first)
mystl::destroy(&*first);
}
}这个函数调用了 才写的 construct 函数,这里就实现了内存的自我管理和控制。
总结
这个项目的源代码给我很大的启发，特别是抽象方面，iterator 的抽象方法令我耳目一新,对于 OO 的抽象认识进步不少。
但是这个代码并不是一个特别标准的 OOP 项目，其封装性也只是体现在元素的private 保护上,就不做特别多的赘述。
