【游戏编程扯淡精粹】TinySTL源码阅读
实际看了，会发现也并没有很难，比起阅读《C++标准库》这样的砖头API书籍，要更为容易和高效
学习目标
学习路线
从单元测试开始看起
进度清单
编译问题
TinySTL\Detail\Vector.impl.h(55): error C2572: ‘TinySTL::vector<T,Alloc>::resize’: redefinition of default argument: parameter 1
默认参数只能定义一次，这里是一个模板函数拆分了声明和实现，在实现处也加了默认参数
iostream问题
没有include <iostream>，self-contained问题
测试方法
STL也有的容器，和TinySTL做相同的操作，然后比较容器相等即可
pair
test case
- ctor
- copy ctor
- make_pair
- cmp
- swap
container_equal
有点鸭子类型的味道
template<class Container1, class Container2>
static inline bool container_equal(const Container1 &pair1, const Container2 &pair2) {
return (pair1.first == pair2.first && pair1.second == pair2.second);
}
template alias
为模板起别名
template<typename T>
using stdPair = std::pair<T, T>;
template<typename T>
using tsPair = TinySTL::pair<T, T>;
...
stdPair<int> p1(5, 5);
tsPair<int> p2(5, 5);
swap
swap T，是指两个T互换数据，不是first和second互换
这是一个类型递归概念，每个类型都需要实现swap语义
具体代码没什么难的
template<class T>
void swap(T &a, T &b) {
T temp = a;
a = b;
b = temp;
}
template<class T1, class T2>
struct pair {
void swap(pair &pr);
template<class T1, class T2>
friend void swap(pair<T1, T2> &x, pair<T1, T2> &y);
}
template<class T1, class T2>
void pair<T1, T2>::swap(pair<T1, T2> &pr) {
TinySTL::swap(first, pr.first);
TinySTL::swap(second, pr.second);
}
template<class T1, class T2>
void swap(pair<T1, T2> &x, pair<T1, T2> &y) {
x.swap(y);
}
...
foo.swap(bar);
ctor
TODO EASTL比这复杂得多，move
template<class T1, class T2>
struct pair {
public:
typedef T1 first_type;
typedef T2 second_type;
public:
T1 first;
T2 second;
public:
pair() {}
template<class U, class V>
pair(const pair<U, V> &pr);
pair(const first_type &a, const second_type &b);
pair &operator=(const pair &pr);
}
cmp operator
重载比较运算符，运算符被标记为friend，可以访问private成员
template<class T1, class T2>
struct pair {
public:
template<class T1, class T2>
friend bool operator==(const pair<T1, T2> &lhs, const pair<T1, T2> &rhs);
template<class T1, class T2>
friend bool operator!=(const pair<T1, T2> &lhs, const pair<T1, T2> &rhs);
template<class T1, class T2>
friend bool operator<(const pair<T1, T2> &lhs, const pair<T1, T2> &rhs);
template<class T1, class T2>
friend bool operator<=(const pair<T1, T2> &lhs, const pair<T1, T2> &rhs);
template<class T1, class T2>
friend bool operator>(const pair<T1, T2> &lhs, const pair<T1, T2> &rhs);
template<class T1, class T2>
friend bool operator>=(const pair<T1, T2> &lhs, const pair<T1, T2> &rhs);
template<class T1, class T2>
friend void swap(pair<T1, T2> &x, pair<T1, T2> &y);
};
...
assert(!(foo == bar));
assert(foo != bar);
assert(foo < bar);
assert(!(foo > bar));
assert(foo <= bar);
assert(!(foo >= bar));
make_pair
在ctor上套了一层
vector
test case
- ctor
- push_back
- iterator
- reverse_iterator
- resize
- reserve
- front
- data
- swap
- pop_back
- insert
- erase
ctor
存储三个指针
EASTL的构造会写的比较晦涩，重点关注内存分配，分离new的malloc和调用ctor两个操作
template<class T, class Alloc = allocator<T>>
class vector{
private:
T *start_;
T *finish_;
T *endOfStorage_;
typedef Alloc dataAllocator;
public:
typedef T value_type;
typedef T* iterator;
typedef const T* const_iterator;
typedef reverse_iterator_t<T*> reverse_iterator;
typedef reverse_iterator_t<const T*> const_reverse_iterator;
typedef iterator pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
public:
vector()
:start_(0), finish_(0), endOfStorage_(0){}
explicit vector(const size_type n);
vector(const size_type n, const value_type& value);
template<class InputIterator>
vector(InputIterator first, InputIterator last);
vector(const vector& v);
vector(vector&& v);
vector& operator = (const vector& v);
vector& operator = (vector&& v);
~vector();
}
- dector，析构每个item，一起释放内存
- 传入n，
T()调用默认构造函数 - 传入n和v，调用v的拷贝构造
- 拷贝构造，调用每个item的拷贝构造
- 移动构造，将v对items所有权转交
- 迭代器范围构造，调用每个item的拷贝构造
template<class T, class Alloc>
vector<T, Alloc>::~vector(){
destroyAndDeallocateAll();
}
template<class T, class Alloc>
vector<T, Alloc>::vector(const size_type n){
allocateAndFillN(n, value_type());
}
template<class T, class Alloc>
vector<T, Alloc>::vector(const size_type n, const value_type& value){
allocateAndFillN(n, value);
}
template<class T, class Alloc>
template<class InputIterator>
vector<T, Alloc>::vector(InputIterator first, InputIterator last){
vector_aux(first, last, typename std::is_integral<InputIterator>::type());
}
template<class T, class Alloc>
vector<T, Alloc>::vector(const vector& v){
allocateAndCopy(v.start_, v.finish_);
}
template<class T, class Alloc>
vector<T, Alloc>::vector(vector&& v){
start_ = v.start_;
finish_ = v.finish_;
endOfStorage_ = v.endOfStorage_;
v.start_ = v.finish_ = v.endOfStorage_ = 0;
}
template<class T, class Alloc>
vector<T, Alloc>& vector<T, Alloc>::operator = (const vector& v){
if (this != &v){
allocateAndCopy(v.start_, v.finish_);
}
return *this;
}
template<class T, class Alloc>
vector<T, Alloc>& vector<T, Alloc>::operator = (vector&& v){
if (this != &v){
destroyAndDeallocateAll();
start_ = v.start_;
finish_ = v.finish_;
endOfStorage_ = v.endOfStorage_;
v.start_ = v.finish_ = v.endOfStorage_ = 0;
}
return *this;
}
tsVec<int> temp2(10, 0);
填充temp2，10个0
堆栈如下，跑了一些模板type_traits，关键是先用Alloc分配内存，然后*first = value;调用拷贝构造
template<class T, class Alloc>
void vector<T, Alloc>::allocateAndFillN(const size_type n, const value_type& value){
start_ = dataAllocator::allocate(n);
TinySTL::uninitialized_fill_n(start_, n, value);
finish_ = endOfStorage_ = start_ + n;
}
template<class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first,
Size n, const T& x){
typedef typename _type_traits<T>::is_POD_type isPODType;
return _uninitialized_fill_n_aux(first, n, x, isPODType());
}
template<class ForwardIterator, class Size, class T>
ForwardIterator _uninitialized_fill_n_aux(ForwardIterator first,
Size n, const T& x, _true_type){
return fill_n(first, n, x);
}
template<class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T& value)
{
for (; n > 0; --n, ++first)
*first = value;
return first;
}
tsVec<std::string> v2(10, "zxh");
同样的接口，string不是POD，走placement_new
这里封装了一下placement_new，更加清晰
template<class ForwardIterator, class Size, class T>
ForwardIterator _uninitialized_fill_n_aux(ForwardIterator first,
Size n, const T& x, _false_type){
int i = 0;
for (; i != n; ++i){
construct((T*)(first + i), x);
}
return (first + i);
}
封装new和delete，以及array版本，所以是四个函数
template<class T1, class T2>
inline void construct(T1 *ptr1, const T2& value){
new(ptr1) T1(value);
}
template<class T>
inline void destroy(T *ptr){
ptr->~T();
}
template<class ForwardIterator>
inline void _destroy(ForwardIterator first, ForwardIterator last, _true_type){}
template<class ForwardIterator>
inline void _destroy(ForwardIterator first, ForwardIterator last, _false_type){
for (; first != last; ++first){
destroy(&*first);
}
}
template<class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last){
typedef typename _type_traits<ForwardIterator>::is_POD_type is_POD_type;
_destroy(first, last, is_POD_type());
}
tsVec<std::string> v6(std::begin(arr), std::end(arr));
可以理解为拷贝一个容器的一部分
NOTE InputIterator要区分一下是否是指针，和函数resolve有关
template<class T, class Alloc>
template<class InputIterator>
vector<T, Alloc>::vector(InputIterator first, InputIterator last){
vector_aux(first, last, typename std::is_integral<InputIterator>::type());
}
template<class T, class Alloc>
template<class InputIterator>
void vector<T, Alloc>::allocateAndCopy(InputIterator first, InputIterator last){
start_ = dataAllocator::allocate(last - first);
finish_ = TinySTL::uninitialized_copy(first, last, start_);
endOfStorage_ = finish_;
}
auto v3(std::move(temp1));
template<class T, class Alloc>
vector<T, Alloc>::vector(vector&& v){
start_ = v.start_;
finish_ = v.finish_;
endOfStorage_ = v.endOfStorage_;
v.start_ = v.finish_ = v.endOfStorage_ = 0;
}
push_back
template<class T, class Alloc>
void vector<T, Alloc>::push_back(const value_type& value){
insert(end(), value);
}
insert
在索引n处插入若干item
分两步：
- 在n处切一刀，把右半部分往右挪，挖个洞出来
- 在洞里填充插入的item
第一步可能触发扩容，直接重新分配一大块内存依次填充数据
？ 这里怎么是placement new，应该是拷贝构造
template<class T, class Alloc>
template<class Integer>
void vector<T, Alloc>::insert_aux(iterator position, Integer n, const value_type& value, std::true_type){
assert(n != 0);
difference_type locationLeft = endOfStorage_ - finish_;
difference_type locationNeed = n;
if (locationLeft >= locationNeed){
auto tempPtr = end() - 1;
for (; tempPtr - position >= 0; --tempPtr){
construct(tempPtr + locationNeed, *tempPtr);
}
TinySTL::uninitialized_fill_n(position, n, value);
finish_ += locationNeed;
}
else{
reallocateAndFillN(position, n, value);
}
}
erase
insert的逆向操作，但是不会触发扩容
直接调用拷贝构造，T自己去处理相关释放
template<class T, class Alloc>
typename vector<T, Alloc>::iterator vector<T, Alloc>::erase(iterator first, iterator last){
difference_type lenOfTail = end() - last;
difference_type lenOfRemoved = last - first;
finish_ = finish_ - lenOfRemoved;
for (; lenOfTail != 0; --lenOfTail){
auto temp = (last - lenOfRemoved);
*temp = *(last++);
}
return (first);
}
iterator
简单的指针。。
typedef T value_type;
typedef T* iterator;
typedef const T* const_iterator;
typedef reverse_iterator_t<T*> reverse_iterator;
typedef reverse_iterator_t<const T*> const_reverse_iterator;
iterator begin(){ return (start_); }
const_iterator begin()const{ return (start_); }
const_iterator cbegin()const{ return (start_); }
iterator end(){ return (finish_); }
const_iterator end()const{ return (finish_); }
const_iterator cend()const{ return (finish_); }
reverse_iterator rbegin(){ return reverse_iterator(finish_); }
const_reverse_iterator crbegin()const{ return const_reverse_iterator(finish_); }
reverse_iterator rend(){ return reverse_iterator(start_); }
const_reverse_iterator crend()const{ return const_reverse_iterator(start_); }
resize
difference_type size()const{ return finish_ - start_; }
difference_type capacity()const{ return endOfStorage_ - start_; }
bool empty()const{ return start_ == finish_; }
void resize(size_type n, value_type val = value_type());
void reserve(size_type n);
void shrink_to_fit();
vector维护了三个指针，将n与size和capacity进行比较，分三种情况讨论：
- n < size，析构多余元素
- size < n < capacity，构造若干item到n个
- n > capacity，拷贝并指向到新的一块n大小的内存上，释放掉原有内存 // 最耗的扩容操作
reserve就是扩容，略
template<class T, class Alloc>
void vector<T, Alloc>::resize(size_type n, value_type val){
if (n < size()){
dataAllocator::destroy(start_ + n, finish_);
finish_ = start_ + n;
}
else if (n > size() && n <= capacity()){
auto lengthOfInsert = n - size();
finish_ = TinySTL::uninitialized_fill_n(finish_, lengthOfInsert, val);
}
else if (n > capacity()){
auto lengthOfInsert = n - size();
T *newStart = dataAllocator::allocate(getNewCapacity(lengthOfInsert));
T *newFinish = TinySTL::uninitialized_copy(begin(), end(), newStart);
newFinish = TinySTL::uninitialized_fill_n(newFinish, lengthOfInsert, val);
destroyAndDeallocateAll();
start_ = newStart;
finish_ = newFinish;
endOfStorage_ = start_ + n;
}
}
template<class T, class Alloc>
void vector<T, Alloc>::reserve(size_type n){
if (n <= capacity())
return;
T *newStart = dataAllocator::allocate(n);
T *newFinish = TinySTL::uninitialized_copy(begin(), end(), newStart);
destroyAndDeallocateAll();
start_ = newStart;
finish_ = newFinish;
endOfStorage_ = start_ + n;
}
string
- 当作
vector<char>，维护三个指针 - npos，size_t最大值，用-1初始化，索引默认值
这块还是看其他库把
class string{
public:
static const size_t npos = -1;
private:
char *start_;
char *finish_;
char *endOfStorage_;
typedef TinySTL::allocator<char> dataAllocator;
public:
string() :start_(0), finish_(0), endOfStorage_(0){}
string(const string& str);
string(string&& str);
string(const string& str, size_t pos, size_t len = npos);
string(const char* s);
string(const char* s, size_t n);
string(size_t n, char c);
template <class InputIterator>
string(InputIterator first, InputIterator last);
string& operator= (const string& str);
string& operator= (string&& str);
string& operator= (const char* s);
string& operator= (char c);
~string();
}
|