Эффективный круговой список

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

A std::list может быть более простой альтернативой созданию списка, чем std::vector. Там также std::queue.

Также забавно, что вы используете vector для реализации круговой очереди , но задаете вопрос о том, как реализовать круговой список . Почему бы не использовать карту?

Answer 3

Вы можете использовать ваши векторы как обычно, а затем создать функцию 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 начинает вращаться с последнего элементавашего вектора, который, конечно, предназначен.

Answer 4

В 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 5

Попробуйте std :: deque. Интерфейс похож на использование std :: vector, но вставка и удаление в начале и конце более эффективны.