C++ STL：擦除 std::deque 的最后/前 n 个元素的最有效方法

Question

我正在编写一个 C++ 程序，我必须在其中维护偏移量列表（在数组或文件中），为此我使用 std::deque<size_t>。该列表在读取文件时被填满，其中包含特定字符最后出现的位置——比方说 'a'。因此，在读取文件时，每次出现字符 'a' 时，我都会将其位置推到队列的末尾。

现在，在某些时候我必须删除此列表中小于给定最大大小的所有条目（或者换句话说：距离当前阅读位置超过 x 个字节）。由于队列已排序（通过创建队列的方式），最简单的方法可能是在值较小时将元素从队列中弹出：

void remove_smaller_than(size_t minimum)
{
    size_t element = my_queue.first(); // yes I know, should check if empty here too
    while (element < minimum && !my_queue.empty())
    {
        my_queue.pop_front();
        element = my_queue.first();
    }

}

现在的问题是，每次我必须这样做时，我都必须从另一边迭代队列（出于另一个原因），在 的位置结束=29=]距离太远的第一个元素。只是为了澄清（因为这很难解释），这里又是一个简短的片段：

void iterate_over_matches(size_t minimum)
{
    for (auto it = my_queue.rbegin(), end = my_queue.rend(); it != end && *it > minimum; ++it)
        do_something(*it);
}

（类似的东西，这只是为了演示）

所以我现在的想法是，如果我已经有了 last valid（而不是 first invalid）条目的迭代器，有没有比弹出所有条目更有效的方法来“剪辑”这个位置的双端队列？

长话短说：

如果我有一个 std::deque 的给定迭代器，是否有比在 while 循环中弹出它们更有效的方法来擦除从该迭代器开始直到结束的所有元素？

Answer 1

因为这是一个离散元素的容器，所以对这些元素的任何形式的删除都将涉及对它们的迭代。即使是标准库的擦除元素函数也在内部使用循环。

如果要删除的元素的数量是恒定的（例如，如果您知道总是有 5 个元素要删除），那么您可以省略循环，只写 5 个单独的指令，这样会很小更高效（您将避免循环生成的条件跳转指令）。

Answer 2

If I have a given iterator of a std::deque, is there a more efficient way to erase all elements starting at this iterator up to the end than popping them in a while loop?

是 – 使用带有两个迭代器参数的覆盖调用 erase member function of std::deque。第一个是您的“给定迭代器”，第二个是双端队列对象的 end() 迭代器。

这是一个基于链接的 cppreference 页面中给出的示例：

#include <deque>
#include <iostream>

void print_container(const std::deque<int>& c)
{
    for (auto& i : c) {
        std::cout << i << " ";
    }
    std::cout << '\n';
}

int main()
{
    std::deque<int> c{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    print_container(c);
    auto it = c.begin();
    while (*it != 5) ++it;
    c.erase(it, c.end()); // Erase from a given iterator to the end of the container
//  c.erase(c.begin(), it); // Or to erase the other part
    print_container(c);
    return 0;
}

STL 实现是否使这个 'more efficient' 而不是在容器中迭代自己将取决于几个因素（例如所包含对象的性质），但快速查看 MSVC/clang-cl实现建议 STL 可以使用对 std::move() 的调用来实现这一点（至少对于基本包含的类型）。

Answer 3

虽然从 std::deque 中删除元素的最快方法确实是 erase 方法，但 std::deque 似乎不是适合您情况的理想数据结构。由于您的元素已排序（它们不断增加），您可以在 O(log(n)) 时间内找到您需要删除的索引。不幸的是，std::deque::erase 具有 O(n) 复杂度，因此快速搜索的收益完全消失了。我们可以做得更好。

由于您存储在数据结构中的元素不需要被破坏（因为它们只是整数），因此可以创建一个在恒定时间内擦除这些元素的数据结构。例如，这是一个执行此操作的环形缓冲区实现：

template <typename T>
class RingBuffer
{
public:
    static_assert(std::is_trivially_copyable_v<T>, "T must be trivially copyable!");
    static_assert(std::is_trivially_destructible_v<T>, "T must be trivially destructable!");

    RingBuffer() :
        m_Items(nullptr),
        m_Capacity(0),
        m_StartIndex(0),
        m_EndIndex(0),
        m_Version(0)
    {
    }

    RingBuffer(const RingBuffer&) = delete;
    RingBuffer& operator=(const RingBuffer&) = delete;

    ~RingBuffer()
    {
        delete[] m_Items;
    }

    void Add(T item)
    {
        m_Version++;

        if (m_EndIndex + 1 == m_StartIndex || (m_EndIndex >= m_StartIndex && m_EndIndex >= m_Capacity && m_StartIndex == 0))
            Grow();

        size_t elementIndex;
        if (m_EndIndex >= m_Capacity)
        {
            elementIndex = 0;
            m_EndIndex = 1;
        }
        else
        {
            elementIndex = m_EndIndex++;
        }

        m_Items[elementIndex] = std::move(item);
    }

    void EraseFirstN(size_t eraseCount)
    {
        m_Version++;

        auto count = size();
        assert(eraseCount <= count);

        if (eraseCount == count)
        {
            m_StartIndex = m_EndIndex = 0;
            return;
        }

        m_StartIndex += eraseCount;
        if (m_StartIndex >= m_Capacity)
            m_StartIndex -= m_Capacity;
    }

    size_t size() const
    {
        if (m_EndIndex >= m_StartIndex)
            return m_EndIndex - m_StartIndex;

        return m_Capacity - m_StartIndex + m_EndIndex;
    }

    struct Iterator : std::iterator<std::random_access_iterator_tag, T>
    {
        Iterator() :
            m_Container(nullptr),
            m_Index(0),
            m_Version(0)
        {
        }

        Iterator(RingBuffer<T>* container, size_t index, size_t version) :
            m_Container(container),
            m_Index(index),
            m_Version(version)
        {
        }

        Iterator& operator+=(ptrdiff_t value) { m_Index += value; return *this; }
        Iterator& operator-=(ptrdiff_t value) { m_Index -= value; return *this; }

        T& operator*() { assert(m_Version == m_Container->m_Version); return (*m_Container)[m_Index]; }
        const T& operator*() const { assert(m_Version == m_Container->m_Version); return (*m_Container)[m_Index]; }

        T* operator->() { assert(m_Version == m_Container->m_Version); return &(*m_Container)[m_Index]; }
        const T* operator->() const { assert(m_Version == m_Container->m_Version); return &(*m_Container)[m_Index]; }

        T& operator[](const int& index) { assert(m_Version == m_Container->m_Version); return (*m_Container)[m_Index + index]; }
        const T& operator[](const int& index) const { assert(m_Version == m_Container->m_Version); return (*m_Container)[m_Index + index]; }

        Iterator& operator++() { m_Index++; return *this; }
        Iterator& operator--() { m_Index--; return *this; }
        Iterator operator++(int) { return Iterator(m_Container, m_Index++, m_Version); }
        Iterator operator--(int) { return Iterator(m_Container, m_Index--, m_Version); }
        ptrdiff_t operator-(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return static_cast<ptrdiff_t>(m_Index - other.m_Index); }
        Iterator operator+(const ptrdiff_t& index) const { return Iterator(m_Container, m_Index + index, m_Version); }
        Iterator operator-(const ptrdiff_t& index) const { return Iterator(m_Container, m_Index - index, m_Version); }
        friend Iterator operator+(const ptrdiff_t& index, const Iterator& other) { return other + index; }
        friend Iterator operator-(const ptrdiff_t& index, const Iterator& other) { return Iterator(other.m_Container, index - other.m_Index, other.m_Version); }

        bool operator==(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index == other,m_Index; }
        bool operator!=(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index != other.m_Index; }
        bool operator>(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index > other.m_Index; }
        bool operator<(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index < other.m_Index; }
        bool operator>=(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index >= other.m_Index; }
        bool operator<=(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index <= other.m_Index; }

    private:
        RingBuffer<T>* m_Container;
        size_t m_Index;
        size_t m_Version;
    };

    Iterator begin()
    {
        return Iterator(this, 0, m_Version);
    }

    Iterator end()
    {
        return Iterator(this, size(), m_Version);
    }

    T& operator[](size_t index)
    {
        assert(index < size());

        index += m_StartIndex;
        if (index >= m_Capacity)
            index -= m_Capacity;

        return m_Items[index];
    }

private:
    void Grow()
    {
        auto newCapacity = std::max(m_Capacity * 2, m_Capacity + 4);
        auto newItems = new T[newCapacity];

        if (m_EndIndex >= m_StartIndex)
        {
            memcpy(newItems, m_Items + m_StartIndex, (m_EndIndex - m_StartIndex) * sizeof(T));
            m_EndIndex = m_EndIndex - m_StartIndex;
        }
        else
        {
            memcpy(newItems, m_Items + m_StartIndex, (m_Capacity - m_StartIndex) * sizeof(T));
            memcpy(newItems + m_Capacity - m_StartIndex, m_Items, m_EndIndex * sizeof(T));

            m_EndIndex = m_Capacity - m_StartIndex + m_EndIndex;
        }

        delete[] m_Items;

        m_StartIndex = 0;
        m_Items = newItems;
        m_Capacity = newCapacity;

    }

private:
    T* m_Items;
    size_t m_Capacity;
    size_t m_StartIndex;
    size_t m_EndIndex;
    size_t m_Version;
};

从这个数据结构中删除比使用 std::deque 快得多。这是我使用的基准测试代码：

constexpr size_t kCount = 100 * 1000 * 1000;

size_t everIncreasingIndex = 0;
size_t elementToEraseUpTo = 5674112;

std::deque<size_t> deque;
RingBuffer<size_t> ringBuffer;

std::cout.setf(std::ios::fixed);
std::cout.precision(5);

for (size_t u = 0; u < 10; u++)
{
    for (size_t i = 0; i < kCount; i++)
    {
        deque.push_back(everIncreasingIndex);
        ringBuffer.Add(everIncreasingIndex);

        everIncreasingIndex++;
    }

    {
        Stopwatch stopwatch;

        auto it = std::lower_bound(deque.begin(), deque.end(), elementToEraseUpTo);
        deque.erase(deque.begin(), it);

        auto elapsed = stopwatch.ElapsedSeconds();
        std::cout << "std::deque took " << elapsed * 1000 << " ms." << std::endl;
    }

    {
        Stopwatch stopwatch;

        auto it = std::lower_bound(ringBuffer.begin(), ringBuffer.end(), elementToEraseUpTo);
        ringBuffer.EraseFirstN(it - ringBuffer.begin());

        auto elapsed = stopwatch.ElapsedSeconds();
        std::cout << "Ring buffer took " << elapsed * 1000 << " ms." << std::endl;
    }

    elementToEraseUpTo *= 2;
}

在我的机器上，结果如下：

std::deque took 6.43080 ms.
Ring buffer took 0.00220 ms.
std::deque took 6.40030 ms.
Ring buffer took 0.00170 ms.
std::deque took 12.83000 ms.
Ring buffer took 0.00160 ms.
std::deque took 25.61430 ms.
Ring buffer took 0.00240 ms.
std::deque took 51.16480 ms.
Ring buffer took 0.00280 ms.
std::deque took 102.56710 ms.
Ring buffer took 0.00270 ms.
std::deque took 205.54640 ms.
Ring buffer took 0.00250 ms.
std::deque took 411.39580 ms.
Ring buffer took 0.00250 ms.
std::deque took 170.58990 ms.
Ring buffer took 0.00300 ms.
std::deque took 98.51280 ms.
Ring buffer took 0.00230 ms.

C++ STL：擦除 std::deque 的最后/前 n 个元素的最有效方法

C++ STL: most efficient way to erase the last / first n elements of a std::deque

c++

performance

stl

std

deque

长话短说：