快速可索引堆栈
4.95/5 (13投票s)
我提供了一个快速增长的可索引堆栈的实现，
引言
ootl::stack 是一个类似于 std::vector 的模板类，它提供了极快的元素增长速度：平均和最坏情况下的复杂度均为 O(1)，而不是 std::vector 在最坏情况下的 O(N) 复杂度。 ootl::stack 模板还提供快速索引，其性能比 std::deque 高出 6 倍或更多。
反向倍增数组列表
ootl::stack 模板基于一种称为“反向倍增数组列表”的数据结构（据我所知，这是原创的，但如果有人知道其他情况，请告诉我）。反向倍增数组列表是一个数组的链表，每个数组的大小是下一个数组的两倍。当第一个节点（或者你想把它想象成最后一个节点，取决于你如何设想它）的数组被填充到容量时，将创建一个新的节点，其容量是前一个节点的两倍。由于原始数据不会移动，因此在任何给定时间只使用 2N 内存，不会发生取消分配，并且不需要 N 次销毁和复制构造操作。
很明显，这种数据结构支持高效的增长，因为没有副本，并且浪费的空间更少。然而，有点违反直觉的是，这种数据结构平均提供具有恒定复杂度的随机元素访问。 以 O(1) 复杂度实现索引的关键是列表必须从最大的节点遍历到最小的节点。
分析索引的复杂度
反向倍增数组列表的前半部分元素位于第一个节点中，1/4 的元素位于第二个节点中，1/8 的元素位于第三个节点中，依此类推，直到达到某个下限。 平均而言，你会在两个元素后找到你想要的节点，在最坏的情况下，你会在 O(Log N) 时间复杂度内找到它。 原因如下：忽略查找操作，使用索引查找访问元素所需的平均节点数由以下公式表示
(1/2)n + (2/4)n + (3/8)n + ... + (i/2^i)n / n
商中的 n 的因子是无限级数 1/2 + 2/4 + 3/8 + 4/16 + ... + (i/2^i)。 这个系列收敛于 2 的值。 为了理解为什么会这样，请考虑它等价于以下无限和的无限和
(1/2 + 1/4 + 1/8 + ...) + (1/4 + 1/8 + 1/16 + ...) +
(1/8 + 1/16 + 1/32 + ...) + ...
这些无限级数是众所周知的，并且很容易识别为等于
1 + 1/2 + 1/4 + ...
基准测试
我进行了一些非正式的测试，以比较所描述的堆栈类与 std::vector 和 std::vector 实现的性能，这些实现来自 C++ 标准库的 STLPort 4.6.2 实现。 以下结果是在 Windows XP Service Pack 2 下获得的，运行在配备 512 MB 内存的 Intel Celeron 1.80 GHZ 机器上，使用具有完整优化的 MinGW GCC 3.4 编译器
// appending 12.8 million integers
std::vector = 1015 msec
std::deque = 734 msec
ootl::stack = 577 msec
// indexing speeds of 12.8 million integers
std::vector = 593 msec
std::deque = 6733 msec
ootl::stack = 1171 msec
这些是从完整的基准测试套件中提取的相当具有代表性的摘录。
接口
ootl::stack 模板本身（稍后列出）非常复杂，所以首先是它简化的接口
template<typename
class stack
{
public:
// public
typedef T value_type;
typedef stack self;
// 'structors
stack();
stack(self& x);
stack(int nsize, const T& x = T());
~stack();
// model the OOTL Indexable concept
T& operator[](int n);
int count();
// model the OOTL Stackable concept
void push(const T& x = T());
void pop();
bool is_empty();
T& top();
// model the OOTL Iterable concept
tempate<Procedure>
void for_each(Procedure& p);
};
实现
这是庞大的实现
// Public Domain by Christopher Diggins
// http://www.ootl.org
#ifndef OOTL_STACK_HPP
#define OOTL_STACK_HPP
#include <cstdlib>
#include <cassert>
#include <memory>
#include <algorithm>
#include <iostream>
namespace ootl {
template<
typename T,
int Factor_N = 2,
int Initial_N = 8,
typename Alloc = std::allocator<T>
>
struct indexable_stack_impl
{
public:
typedef T value_type;
typedef indexable_stack_impl self;
private:
// local buffer type
struct buffer {
buffer(int n, int i = 0, buffer* x = NULL) :
size(n), index(i), prev(x), begin(a.allocate(n)), end(begin + n)
{ }
~buffer() {
a.deallocate(begin, size);
}
template<typename Procedure>
void for_each(Procedure& proc, T* end) {
if (prev != NULL) {
prev->for_each(proc, prev->end);
}
T* p = begin;
while (p != end) {
proc(*p++);
}
}
int index;
int size;
T* begin;
Alloc a;
T* end;
buffer* prev;
};
private:
// begin fields
buffer* buff;
T* last;
int cnt;
int cap;
int init;
public:
indexable_stack_impl() {
initialize(Initial_N);
}
indexable_stack_impl(self& x) {
initialize(x.capacity());
x.for_each(stacker(*this));
}
indexable_stack_impl(int nsize, const T& x = T()) {
if (nsize >= Initial_N) {
initialize(nsize);
}
else {
initialize(Initial_N);
}
last = buff->begin + nsize;
while (cnt < nsize) {
buff->a.construct(buff->begin + cnt++, x);
}
assert(last == buff->begin + cnt);
}
~indexable_stack_impl() {
while (cnt > 0) {
pop();
}
assert(buff != NULL);
delete buff;
}
// implementation of OOTL Indexable
T& operator[](int n) {
if (n >= buff->index) {
return buff->begin[n - buff->index];
}
buffer* curr = buff->prev;
loop:
if (n >= curr->index) {
return curr->begin[n - curr->index];
}
curr = curr->prev;
goto loop;
}
int count() const {
return cnt;
}
// implementation of OOTL Stack concept
void push(const T& x = T()) {
assert(last >= buff->begin);
assert(last <= buff->end);
if (last == buff->end) {
add_buffer();
}
buff->a.construct(last++, x);
++cnt;
}
void pop() {
assert(last >= buff->begin);
assert(last <= buff->end);
if (last == buff->begin) {
remove_buffer();
}
assert(buff != NULL);
buff->a.destroy(--last);
--cnt;
}
bool is_empty() {
return count() == 0;
}
T& top() {
return *(top_pointer());
}
// implementation of OOTL Iterable concept
template<typename Procedure>
void for_each(Procedure& proc) {
buff->for_each(proc, last);
}
private:
void initialize(int ncap) {
assert(ncap >= Initial_N);
buff = new buffer(ncap);
cnt = 0;
cap = ncap;
last = buff->begin;
}
T* top_pointer() {
assert(!is_empty());
assert(last >= buff->begin);
assert(last <= buff->end);
if (last == buff->begin) {
return buff->prev->end - 1;
}
else {
return last - 1;
}
}
void add_buffer() {
buff = new buffer(buff->size * Factor_N, cap, buff);
cap += buff->size;
last = buff->begin;
assert(count() < capacity());
}
void remove_buffer() {
buffer* tmp = buff;
cap -= buff->size;
buff = buff->prev;
tmp->prev = NULL;
last = buff->end;
delete(tmp);
}
int capacity() const {
return cap;
}
};
///////////////////////////////////////////////////////////////
// A stack_extension contains additional functions which
// can be easily derived from a stack
template
<
typename Implementation,
typename Inherited
>
struct stack_extension : Inherited
{
// public typedef
typedef Inherited inh;
typedef Implementation impl;
typedef typename inh::value_type value_type;
// constructors
stack_extension() : inh() { }
stack_extension(impl& x) : inh(x) { }
stack_extension(int nsize, const value_type& x = value_type()) :
inh(nsize, x) { }
// implementation of OOTL Growable concept
void grow(int n = 1, const value_type& x = value_type()) {
while (n > 0) inh::push(x);
}
// implementation of OOTL Shrinkable concept
void shrink(int n = 1) {
while (n--) inh::pop();
}
// implementation of OOTL Resizable concept
void resize(int n, const value_type& x = value_type()) {
while (n > inh::count()) inh::push(x);
while (n < inh::count()) inh::pop();
}
// implementation of OOTL Sortable concept
bool lt(int i, int j) {
return inh::operator[](i) < inh::operator[](j);
}
void swap(int i, int j) {
std::swap(inh::operator[](i), inh::operator[](j));
}
// utility functions
void clear() {
while (!inh::is_empty()) {
inh::pop();
}
}
void dup() {
inh::push(inh::top());
}
void reverse() {
int max = inh::count() - 1;
int n = inh::count() / 2;
for (int i=0; i < n; ++i) {
inh::swap(i, max - i);
}
}
};
///////////////////////////////////////////////
// The contract checks the preconditions and
// postconditions of the functions
template
<
typename Implementation,
typename Inherited
>
struct stack_contract : Inherited
{
// public typedef
typedef Inherited inh;
typedef Implementation impl;
typedef typename inh::value_type value_type;
// constructors
stack_contract() : inh() { }
stack_contract(impl& x) : inh(x) { }
stack_contract(int nsize, value_type x = value_type())
: inh(nsize, x) { }
// public functions
void pop() {
int old = inh::count();
assert(!inh::is_empty());
inh::pop();
assert(count() == old - 1);
}
void push(const value_type& x) {
int old = inh::count();
inh::push(x);
assert(inh::count() == old + 1);
}
value_type& top() {
assert(!inh::is_empty());
value_type& ret = inh::top();
value_type& tmp = inh::operator[](inh::count() - 1);
assert(&ret == &tmp);
return ret;
}
int count() {
int ret = inh::count();
assert(ret >= 0);
assert(ret > 0 ? !inh::is_empty() : inh::is_empty());
return ret;
}
bool is_empty() {
bool ret = inh::is_empty();
assert(ret ? inh::count() == 0 : inh::count() > 0);
return ret;
}
value_type& operator[](int n) {
assert(n >= 0);
assert(n < inh::count());
return inh::operator[](n);
}
};
/////////////////////////////////////////////////////////
// The final version of the stack
#ifndef _NDEBUG
template
<
typename T,
typename Implementation = indexable_stack_impl<T>,
typename Contract = stack_contract<Implementation, Implementation>,
typename Extension = stack_extension<Implementation, Contract>
>
struct stack : Extension
{
typedef Implementation impl;
typedef Extension inh;
stack() : inh() { }
stack(impl& x) : inh(impl& x) { }
stack(int nsize, const T& x = T()) : inh(nsize, x) { }
};
#else
template
<
typename T,
typename Implementation = indexable_stack_impl<T>,
typename Extension = stack_extension<Implementation, Implementation>
>
struct stack : Extension
{
typedef Implementation impl;
typedef Extension inh;
stack() : inh() { }
stack(impl& x) : inh(x) { }
stack(int nsize, const T& x = T()) : inh(nsize, x) { }
};
#endif
}
#endif
结束语
不幸的是，该代码无法按原样用于 Visual C++ 7.1 之前的版本。 您需要进行一些修剪才能使其工作。 该代码是公共领域，因此可以随意使用它。 如果您能在论坛上快速回复一下，让我知道此代码在什么样的应用程序中找到了归宿，我会很高兴知道。 如果您想发布一个更便携的版本，我相信其他读者会非常感激！