std deque的速度非常慢

Question

我只是发现,与我使用预先分配的数组的"自制"堆栈版本相比,标准的std deque非常慢.
这是我的堆栈代码:

template <class T>
class FastStack
{    
public:
    T* st;
    int allocationSize;
    int lastIndex;

public:
    FastStack(int stackSize);
    FastStack();
    ~FastStack();

    inline void resize(int newSize);
    inline void push(T x);
    inline void pop();
    inline T getAndRemove();
    inline T getLast();
    inline void clear();
};

template <class T>
FastStack<T>::FastStack()
{
    lastIndex = -1;
    st = NULL;
}

template <class T>
FastStack<T>::FastStack(int stackSize)
{
    st = NULL;
    this->allocationSize = stackSize;
    st = new T[stackSize];
    lastIndex = -1;
}

template <class T>
FastStack<T>::~FastStack()
{
    delete [] st;
}

template <class T>
void FastStack<T>::clear()
{
    lastIndex = -1;
}

template <class T>
T FastStack<T>::getLast()
{
    return st[lastIndex];
}

template <class T>
T FastStack<T>::getAndRemove()
{
    return st[lastIndex--];
}

template <class T>
void FastStack<T>::pop()
{
    --lastIndex;
}

template <class T>
void FastStack<T>::push(T x)
{
    st[++lastIndex] = x;
}

template <class T>
void FastStack<T>::resize(int newSize)
{
    if (st != NULL)
        delete [] st;
    st = new T[newSize];
}

.
我为deque运行这个简单的基准测试:

std::deque<int> aStack;
int x;

HRTimer timer;
timer.Start();

for (int i = 0; i < 2000000000; i++)
{
    aStack.push_back(i);
    x = aStack.back();
    if (i % 100 == 0 && i != 0)
        for (int j = 0; j < 100; j++)
            aStack.pop_back();
}

double totalTime = timer.Stop();
stringstream ss;
ss << "std::deque " << totalTime;
log(ss.str());

.
使用带有向量的std堆栈作为容器(如'Michael Kohne'建议的那样)

std::stack<int, std::vector<int>> bStack;
int x;

HRTimer timer;
timer.Start();

for (int i = 0; i < 2000000000; i++)
{
    bStack.push(i);
    x = bStack.top();
    if (i % 100 == 0 && i != 0)
        for (int j = 0; j < 100; j++)
            bStack.pop();
}

double totalTime = timer.Stop();
stringstream ss;
ss << "std::stack " << totalTime;
log(ss.str());

.
和我的FastStack一样:

FastStack<int> fstack(200);
int x;

HRTimer timer;
timer.Start();

for (int i = 0; i < 2000000000; i++)
{
    fstack.push(i);
    x = fstack.getLast();
    if (i % 100 == 0 && i != 0)
        for (int j = 0; j < 100; j++)
            fstack.pop();
}

double totalTime = timer.Stop();
stringstream ss;
ss << "FastStack " << totalTime;
log(ss.str());

.
4次运行后的结果如下:
deque 15.529
deque 15.3756
deque 15.429
deque 15.4778

stack 6.19099
stack 6.1834
stack 6.19315
stack 6.19841

FastStack 3.01085
FastStack 2.9934
FastStack 3.02536
FastStack 3.00937

结果是在几秒钟内,我在Intel i5 3570k(默认时钟)上运行代码.我使用VS2010编译器进行了所有可用的优化.我知道我的FastStack有很多限制,但有很多情况,可以使用它,什么时候可以提供很好的提升!(我在一个项目中使用它,与std :: queue相比,我获得了2倍的速度).
所以现在我的问题是:
在C++中是否还有其他人使用的"抑制剂",但没有人知道它们？
编辑:我不想冒犯,我只是好奇你是否知道这样一些未知的"加速".

Answer 1

你正在比较苹果和橘子.dequeue是DOUBLE-ENDED,这要求它在内部与你实现的简单堆栈有很大的不同.尝试运行基准测试std::stack<int, std::vector<int> >,看看你是怎么做的.std :: stack是一个容器适配器,如果你使用vector作为底层容器,它应该几乎和你自己开发的实现一样快.

一个缺点是std :: stack实现没有办法让你预先设置大小,所以在你知道最大大小需要什么的情况下,它最初会慢一点它必须重新分配几次.在那之后,它将几乎相同.

Answer 2

如果您知道在任何给定时间堆栈中的最大元素数量,您应该使用std::vector预先保留容量的数据.即使你不知道容量,对于堆栈你应该使用一个std::vector会增长几倍(成长时比预分配的矢量成本更高)但从不收缩,所以一段时间后它会停止分配内存.

性能问题是std::deque将根据需要分配块,并在不再需要时释放它们(遵循某种策略),因此如果您std::deque经常填写并清除,则会持续进行分配和解除分配.