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

Question

Я хочу простой, но эффективный круглый буфер/очередь. Если я использую std::vector, я должен сделать это:

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

Есть ли простое решение?

Answer 1

Вы хотите сохранить размер буфера, перезаписав старые элементы. Просто переписывайте старые с течением времени. Если вы хотите иметь дело с случаем, когда nItems < limit, то вам нужно будет справиться с этим, это просто простой пример использования modulo для вставки в буфер фиксированного размера.

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.

Это также смешно, что вы используете вектор реализовать круговую очереди но задать вопрос о том, как реализовать круговой список. Почему бы не использовать карту?

Answer 3

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

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%10] = i; 
}