从0开始写STL—容器—vector
typedef 简析
public:
typedef T value_type;
typedef value_type* pointer;
typedef value_type* iterator;
typedef T& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
Alloctor 简析
内存分配相关函数->动态分配内存
该内存模型的实现形式
destroyanddeallocate函数
void destroyanddeallocate()
{
if(capacity()==0)
{
return ;
}
for(auto it = start; it != End; it++)
{
destroy(it);//对所有元素调用析构函数
}
data_allocator.deallocate(start,end_of_storage-start);//由allocator回收内存
}
~vector()
{
destroyanddeallocate();
}
reallocate 函数 重新分配内存
void reallocate(size_type new_size = 0)
{
if(new_size == 0)
{
new_size = size() == 0 ? 1 : 2 * size();
}
iterator new_start = data_allocator.allocate(new_size);//首先分配一块新的内存
if(new_start == nullptr)
{
//分配失败的处理
//直接终止程序（内存不足）
}
iterator new_End = ministl::uninitialized_copy(start, End, new_start);//移动元素
DestroyAndDeallocateAll();//销毁元素 并且 回收内存
start = new_start;
End = new_End;
end_of_storage = start + new_size;// 设置指针位置
}
代码分析(异常安全)
//这三行提供基本的异常安全保证
if(new_size == 0)
{
new_size = size() == 0 ? 1 : 2 * size();
}
iterator new_start = data_allocator.allocate(new_size);//首先分配一块新的内存
if(new_start == nullptr)
{
//分配失败的处理
//进行内存回收
}
iterator new_End = ministl::uninitialized_copy(start, End, new_start);//may throw
DestroyAndDeallocateAll();//析构函数 noexcept保证
//在最后替换成员指针，提供了强类型的异常安全保证
start = new_start;
End = new_End;
end_of_storage = start + new_size;// 设置指针位置
构造函数
vector()
{
End = end_of_storage = start = nullptr;//避免野指针
}
vector(size_t n, value_type val = value_type())//要求value_type 有一个默认构造函数
{
start = data_allocator.allocate(n);
End = end_of_storage = start + n;
ministl::uninitialized_fill_n(start, n, val);// 使用默认构造函数的值进行拷贝构造
}
vector(iterator first, iterator last)
{
start = data_allocator.allocate(last - first);
End = end_of_storage = uninitialized_copy(first, last, start);
}
vector(const vector<T, Alloc> &rhs)
{
assign(rhs.start, rhs.End);//Dont repeat yourself!//dont repeat yourself
}
vector(vector<T, Alloc> &&rhs)
{
if (this != &rhs)
{
DestroyAndDeallocateAll();
start = rhs.start, End = rhs.End, end_of_storage = rhs.end_of_storage;
rhs.start = rhs.end_of_storage = rhs.End = nullptr;//将移动后的右值置于可析构的状态
}
}
Element Access 相关函数
value_type& operator [](size_type n)
{
if (n >= size())
{
std::cerr << "Out of range" << std::endl;
std::exit(1);
}
return *(start + n);
}
value_type& front()
{
if (empty())
{
std::cerr << "front on empty vector" << std::endl;
std::exit(1);
}
return *(start);
}
value_type& back()
{
if (empty())
{
std::cerr << "back on empty vector" << std::endl;
std::exit(1);
}
return *(End - 1);
}
Modify 修改相关函数
void resize(size_type new_size, value_type val = value_type())
{
if (new_size < size())// 无需重新分配内存
{
// 销毁不需要的元素，无需回收内存
for (iterator it = start + new_size; it != End; it++)
{
destroy(it);
}
End = start + new_size;// 重新设置最后一个元素位置
}
else if (new_size < capacity())//小于申请到的内存容量
{
//只需将后面未初始化的内存初始化一下
uninitialized_fill_n(End, new_size - size(), val);
End = start + new_size;
}
else // 重新分配内存
{
reallocate(new_size);
uninitialized_fill_n(End, new_size - size(), val);
End = start + new_size;
}
}
void reserve(size_type n)
{
if (n <= capacity()) return;
reallocate(n); // 重新分配内存
}
bool empty()
{
return start == End;
}
//Modifiers
void push_back(value_type data)
{
if (capacity() == size())//判断容量
reallocate();
construct(End++, data);//更改End位置并进行初始化
}
void pop_back()
{
if (empty())
{
std::cerr << "pop on empty" << std::endl;
std::exit(1);
}
End--;
destroy(End);//析构
}
template<class InputIterator>
void assign(InputIterator first, InputIterator last)
{
DestroyAndDeallocateAll();
start = data_allocator.allocate(last - first);//申请内存
End = end_of_storage = uninitialized_copy(first, last, start);//初始化
}
void assign(size_type n, const value_type &v)
{
DestroyAndDeallocateAll();
start = data_allocator.allocate(n);
End = end_of_storage = start + n;
uninitialized_fill_n(start, n, v);
}
iterator insert(iterator pos, const value_type &v)
{
if (pos == end())//特殊情况
{
push_back(v);
return &back();
}
if (size() == capacity())//内存申请
reallocate();
iterator new_end = End + 1;
data_allocator.construct(new_end, v);//要进行初始化否则会报错
copy_backward(pos, End, new_end);//移动pos后面的元素到最终位置
*pos = v;//赋值
End = new_end;
end_of_storage++;
return pos;
}
/*
这个函数比较复杂，一定注意End pos 的含义变化
*/
iterator insert(iterator pos, const size_type &n, const value_type &val)
{
size_type index = pos - start;
if (n + size() > capacity())//判断内存容量
reserve(n + size());
pos = start + index;// 插入元素的位置
iterator new_end = End + n; // 元素插入后 结束点的位置
size_type after_num = End - pos;// 插入点后面的元素个数
if (after_num > n) // 如果后面元素个数比要插入的元素多
{
uninitialized_copy(End - n, End, End);// 将End-n 到 End 的元素放置到最正确位置
End += n; // 重新设置End 的位置
copy_backward(pos, End - n, End);// 将pos到End-n的元素放置正确位置
fill(pos, pos + n, val);// 填充出去
return pos + n;// 返回插入最后一个元素的位置
}
else //插入元素个数很多
{
iterator old_end = End;
uninitialized_fill_n(End, n - after_num, val);//填充n-afternum个元素，后面的元素没必要初始化因为后面的元素将会是afternum个插入节点后面的元素
End += n - after_num;
uninitialized_copy(pos, old_end, End);// 拷贝afternum个插入节点后面的元素
End += after_num;
fill(pos, old_end, val);// 填充
return pos + n;
}
}
/*
这个和上面大同小异
*/
template<class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last)
{
size_type add_num = last - first, index = pos - start, after_num = End - pos;
if (add_num + size() > capacity())
reserve(add_num + size());
pos = start + index;
if (pos > End) pos = End;
if (pos <= End - add_num)
{
uninitialized_copy(End - add_num, End, End);
copy_backward(pos, End - add_num, End);
copy(first, last, pos);
End += add_num;
}
else
{
iterator new_end = End + add_num;
uninitialized_copy(pos, End, new_end - after_num);
copy_n(first, after_num, pos);
uninitialized_copy_n(first + after_num, add_num - after_num, End);
End += add_num;
}
}
iterator erase(iterator pos)
{
copy(pos + 1, End, pos);
destroy(End - 1);
End--;
return pos;
}
iterator erase(iterator first, iterator last)
{
copy(last, End, first);
for (auto it = End - (last - first); it != End; it++)
destroy(it);
End = End - (last - first);
return last;
}
void clear()
{
DestroyAndDeallocateAll();
End = start;
}
void swap(vector<T, Alloc> &rhs)
{
iterator tmp;
tmp = start, start = rhs.start, rhs.start = tmp;
tmp = End, End = rhs.End, rhs.End = tmp;
tmp = end_of_storage, end_of_storage = rhs.end_of_storage, rhs.end_of_storage = tmp;
}
bool operator==(vector<T, Alloc>& rhs)
{
if (size() != rhs.size())//首先size 要相同
return false;
else
{
auto it = begin();
auto j = rhs.begin();
for (; it != end(); )
{
if (*it != *j)
return false;
else
it++, j++;
}
return true;
}
}
bool operator!=(vector<T, Alloc>& rhs)
{
return !(*this == rhs);
}
void operator=(const vector<T, Alloc>& rhs)
{
if (this != &rhs)
{
//assign(rhs.begin(), rhs.end());
//or
vector<T,Alloc> tmp = rhs;
swap(tmp); // tmp 交换后存储的是原数组的元素，再函数结尾调用析构函数释放内存
}
}
};
template<class T>
void swap(vector<T>& a, vector<T>& b)
{
a.swap(b);
}
怎样高效使用