c++ - 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];
}

.
我为双端队列运行这个简单的基准测试:

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());

.
使用带有 vector 的 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次后结果如下:
双端队列 15.529
双端队列 15.3756
双端队列 15.429
双端队列 15.4778

堆栈 6.19099
堆栈 6.1834
堆栈 6.19315
堆栈 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

您正在比较苹果和橙子。出列是双端的，这要求它在内部与您实现的简单堆栈有很大不同。尝试针对 std::stack<int, std::vector<int> > 运行基准测试相反，看看你怎么做。 std::stack 是一个容器适配器，如果您使用 vector 作为底层容器，它应该几乎与您自己开发的实现一样快。

不利的一面是 std::stack 实现没有办法让你预先设置大小，所以在你知道最大大小需要是多少的情况下，它会有点最初速度较慢，因为它必须重新分配几次。之后，它几乎是一样的。