从零开始写STL-容器-双端队列
基本实现模型 链状数组
双端队列迭代器
template<class T, size_t Bufsize = 0>
struct _deque_iterator : public random_access_iterator<T>
{
typedef _deque_iterator<T> iterator;
// 这里计算的是一个内存块中可以存放多少T类型的实例
static size_t buffer_size()
{
return _deque_buf_size(Bufsize, sizeof(T));
}
_deque_iterator()
{
cur = first = last = NULL;
node = NULL;
}
T* cur;//此迭代器所指缓冲区中的元素
T* first;//缓冲区开头元素
T* last;//缓冲区尾部元素
map_pointer node;//缓冲区控制器
void set_node(map_pointer new_node)
{
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
reference operator*() const
{
return *cur;
}
pointer operator->() const
{
return &(operator*());
}
difference_type operator-(const self& x)const
{
return difference_type(buffer_size())*(node - x.node - 1) + (cur - first) + (x.last - x.cur);// 间隔内存块*每个内存块个数 + 结点offset
}
self& operator++()
{
++cur;
if (cur == last) //到当前内存块最后一个元素，由链状数组 内存分配器 来指向下一个内存块
{
set_node(node + 1);
cur = first;
}
return *this;
}
self operator++(int)
{
self tmp = *this;
++*this;
return tmp;
}
self& operator--()
{
--cur;
if (cur == first)
{
set_node(node - 1);
cur = last;
}
return *this;
}
self operator--(int)
{
self tmp = *this;
--*this;
return tmp;
}
//随机存取
self& operator+=(difference_type n)
{
difference_type offset = n + (cur - first);
if (offset >= 0 && offset < (difference_type)(buffer_size()))
cur += n;//在当前的缓冲块内部
else
{
difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
set_node(node + node_offset);// 计算内存块的偏移量
cur = first + (offset - node_offset*difference_type(buffer_size()));
}
return *this;
}
self operator+(difference_type n) const
{
self tmp = *this;
return tmp += n;
}
self& operator-=(difference_type n)
{
return *this += -n;
}
self operator-(difference_type n)const
{
self tmp = *this;
return tmp -= n;
}
reference operator[](difference_type n) const
{
return *(*this + n);
}
bool operator==(const self &x) { return x.cur == cur; }
bool operator!=(const self &x)
{
return !(*this==x);
}
bool operator<(const self& x)
{
return (node == x.node) ? (cur < x.cur) : (node < x.node);//优先比较缓冲区！
}
};
双端队列源码
typedef 部分
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef size_t size_type;
typedef _deque_iterator<T> iterator;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
typedef pointer* map_pointer;
内部数据
protected:
iterator start, finish;//维护已经使用内存块的头尾
map_pointer map;//指向内存分配器
size_type map_size;//存放数据量
std::allocator<T> data_allocator;//内存分配器
std::allocator<pointer> map_allocator;//注意这个内存分配器是用来分配内存块的
内存分配
void create_map_and_nodes(size_type num_elements)
{
//分配内存结点数量
size_type num_nodes = num_elements / buffer_size() + 1;
map_size = std::max((size_t)8, num_nodes + 2);
map = map_allocator.allocate(map_size);
//取中间部分来存放数据，这样给头围留下较为稳定均衡的增长空间
map_pointer nstart = map + (map_size - num_nodes) / 2;
map_pointer nfinish = nstart + num_nodes - 1;
map_pointer cur;
try
{
//注意这里cur 是 T**
for (cur = nstart; cur <= nfinish; cur++)
{
//分配内存块 这里*cur 是 T*
*cur = data_allocator.allocate(buffer_size());
}
}
catch (...)
{
}
start.set_node(nstart);
finish.set_node(nfinish);
start.cur = start.first;
finish.cur = finish.first + num_elements%buffer_size();
}
//填充值
void fill_initialize(size_t n,const value_type& val)
{
create_map_and_nodes(n);
map_pointer cur;
try
{
for (cur = start.node; cur < finish.node; cur++)
std::uninitialized_fill(*cur, *cur + buffer_size(), val);
std::uninitialized_fill(finish.first, finish.last, val);
}
catch (...)
{
delete this;
throw __uncaught_exception;
}
}
//要增加的内存块数 以及是否在前端添加（便于更加高效移动元素）
void reallocate_map(size_type nodes_to_add, bool add_at_front)
{
size_type old_num_nodes = finish.node - start.node + 1;
size_type new_num_nodes = old_num_nodes + nodes_to_add;
map_pointer new_start;
if (map_size > 2 * new_num_nodes)//无需重新分配内存
{
new_start = map + (map_size - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
if (new_start < start.node)
std::copy(start.node, finish.node + 1, new_start);
else
std::copy_backward(start.node, finish.node + 1, new_start + old_num_nodes);
}
else
{
size_type new_map_size = map_size + std::max(map_size, nodes_to_add) + 2;
map_pointer new_map = map_allocator.allocate(new_map_size);
new_start = new_map + (new_map_size - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
std::copy(start.node, finish.node + 1, new_start);
map = new_map;
map_size = new_map_size;
}
}
void push_front_aux(const value_type& val)
{
if (start.node - map < 1)
reallocate_map(1, true);
*(start.node - 1) = data_allocator.allocate(buffer_size());
try
{
start.set_node(start.node - 1);
start.cur = start.last - 1;
data_allocator.construct(start.cur, val);
}
catch (...)// commit or rollback!
{
start.set_node(start.node + 1);
start.cur = start.first;
data_allocator.deallocate(*(start.node - 1),buffer_size());
throw;
}
}
void push_back_aux(const value_type& val)
{
if (map_size - (finish.node - map) < 2)
reallocate_map(1, false);
*(finish.node + 1) = data_allocator.allocate(buffer_size());
try
{
data_allocator.construct(finish.cur, val);
finish.set_node(finish.node + 1);
finish.cur = finish.first;
}
catch (...)
{
finish.set_node(finish.node - 1);
finish.cur = finish.last;
data_allocator.deallocate(*(finish.node + 1), buffer_size());
throw;
}
}
数据获取相关
iterator begin()
{
return start;
}
iterator end()
{
return finish;
}
reference operator[](size_type n)
{
return start[(difference_type)n];
}
reference front()
{
return *start;
}
reference back()
{
return *(finish - 1);
}
size_type size()
{
return finish - start;
}
size_type max_size() { return size_type(-1); }
bool empty() { return finish == start; }
Modifiers
void push_back(const value_type& val)
{
if (finish.cur != finish.last - 1)
{
//没必要重新分配空间
data_allocator.construct(finish.cur, val);
++finish.cur;
}
else
push_back_aux(val);
}
void push_front(const value_type& val)
{
if (start.cur != start.first)
{
data_allocator.construct(start.cur - 1, val);
--start.cur;
}
else
push_front_aux(val);
}
void clear()
{
for (auto it = start.cur + 1; it < finish.cur; it++)
data_allocator.destroy(it);//销毁内存块中元素
for (auto it = start.node + 1; it <= finish.node; it++)//销毁并回收内存块
map_allocator.destroy(it),map_allocator.deallocate(it,1);
finish = start;
}
void pop_back()
{
if (finish.cur != finish.first)
{
--finish.cur;
data_allocator.destroy(finish.cur);
}
else
{
//回收当前内存块
data_allocator.deallocate(finish.first,buffer_size());
finish.set_node(finish.node - 1);
finish.cur = finish.last - 1;
data_allocator.destroy(finish.cur);
}
}
void pop_front()
{
if (start.cur != start.last - 1)
{
data_allocator.destroy(start.cur);
start.cur++;
}
else
{
destroy(start.cur);
set_node(start.node + 1);
start.cur = start.first;
}
}
iterator erase(iterator pos)
{
iterator next = pos++;
difference_type index = pos - start;
if (index < size() / 2)
{
copy_backward(start, pos, next);
pop_front();
}
else
{
copy(next, finish, pos);
pop_back();
}
return start + index;
}
//这里和vector 删除元素的思路类似
//通过前端 后端 元素数量选择最高效的移动数据方式
iterator erase(iterator first, iterator last)
{
if (first == start&&last == finish)
{
clear();
return finish;
}
else
{
difference_type n = last - first;
difference_type elems_before = first - start;
if (elems_before < (size() - n) / 2)//如果前方的元素较少
{
copy_backward(start, first, last);
iterator new_start = start + n;
for (auto it = start; it < new_start; it++)
data_allocator.destroy(it);
for (auto it = start; it < new_start; it++)
data_allocator.deallocate(it, buffer_size());
start = new_start;
}
else
{
copy(last, finish, first);
iterator new_finish = finish - n;
for (auto it = new_finish; it < finish; it++)
data_allocator.destroy(it);
for (auto it = new_finish; it < finish; it++)
data_allocator.deallocate(it, buffer_size());
finish = new_finish;
}
return start + elems_before;
}
}
iterator insert(iterator pos, const value_type& x)
{
if (pos.cur == start.cur)
{
push_front(x);
return start;
}
else if (pos.cur == finish.cur)
{
push_back(x);
return finish - 1;
}
else
{
difference_type index = pos - start;
value_type x_copy = x;
//通过Push_front 把头元素复制到前一个内存块，然后将原内存块元素移动到对应位置
if (index < size() / 2)
{
push_front(front());
iterator front1 = start;
++front1;
iterator front2 = front1;
++front2;
pos = start + index;
iterator pos1 = pos;
++pos1;
copy(front2, pos1, front1);
}
else
{
push_back(back());
iterator back1 = finish;
--back1;
iterator back2 = back1;
--back2;
pos = start + index;
copy_backward(pos, back2, back1);
}
*pos = x_copy;
return pos;
}
}