c++ - 高效循环列表

Question

我想要一个简单而高效的循环缓冲区/队列。如果我使用std::vector，我必须这样做：

if ( v.size() >= limit ) {
    std::vector<int> it = v.begin();
    v.insert( it, data );
    v.erase( it+1 );
}

有没有更简单的解决方案？

Answer 1

您想保持缓冲区的大小，覆盖旧项目。随着时间的推移，只需覆盖旧的。如果要处理 nItems < 限制的情况，则需要处理，这只是使用模数插入固定大小缓冲区的简单示例。

std::vector<int> data(10);

for (int i = 0 ; i < 100 ; ++i)
{
    data[i%10] = i;
}

for (std::vector<int>::const_iterator it = data.begin() ; it !=data.end(); ++it)
{
     std::cout << *it << std::endl;
}

这种插入方法会将最后 10 个元素保留在缓冲区中。

Answer 2

Astd::list可能是比构建列表更容易的替代方法std::vector。还有std::queue。

同样有趣的是，您使用向量来实现循环队列，但提出一个关于如何实现循环列表的问题。为什么不使用地图？

Answer 3

对于c++11固定大小的替代方案，您应该使用std::array：

const unsigned int BUFFER_SIZE = 10;
std::array<int, BUFFER_SIZE> buffer; // The buffer size is fixed at compile time.
for (i = 0; i < 100; ++i) {
    buffer[i % BUFFER_SIZE] = i;
}

Answer 4

尝试 std::deque。该接口就像使用 std::vector 一样，但在开头和结尾插入和删除更有效。

Answer 5

你可以像往常一样使用你的向量，然后创建一个 get_element(index) 函数来让它感觉循环。它非常快速且直接，因为它只是整数操作。

template<typename T>
T get_element(std::vector<T> vec, int index) {
    int vector_size = vec.size();
    int vector_max = vector_size - 1;
    int vector_min = 0;
    int index_diff = 0;
    int refined_index = 0;

    // index_diff is the amount of index-out-of-range. Positive means index was
    // bigger than the vector size, negative means index was smaller than 0
    if (index > vector_max) {
        index_diff = index - vector_max;
    } else if (index < vector_min) {
        index_diff = index;
    } else {
        index_diff = 0;
    }

    // Make the indexing feel circular
    // index mod 16 yields a number from 0 to 15
    if (index_diff > 0) {
        refined_index = index % vector_size;
    } else if (index_diff < 0) {
        int temp_index = index % vector_size;

        if (temp_index != 0) {
            refined_index = vector_size - std::abs(temp_index);
            // if the negative mod equals to 0, we can't have 16 - 0 = 16 index,
            // so we set it to 0 manually
        } else {
            refined_index = 0;
        }
    } else {
        refined_index = index;
    }

    return vec[refined_index];
}

然后像这样使用它：

int result = get_element<int>(myvec, 256);

请注意，任何小于 0 的索引都从向量的最后一个元素开始旋转，这当然是有意的。