我最初使用矢量存儲「傳入項目」，但即使使用大量的RAM，這也不實用。因此，我決定存儲最後收到的X個項目。C++最佳數據結構來存儲最後X個傳入項目？
什麼是最好的數據結構使用？我正在考慮一個std ::隊列？這是僞代碼，我在想：
if(queue.size() == max_size){
queue.pop()
}
queue.push(new_item);
的數據結構的使用將存儲的事件，如果使用的歷史，會因此給rollback-通過結構中每個項目迭代。
嘗試雙端隊列，IMO這是你要搜索的內容：
就這樣我知道 - 如果我只是加入一個，並從另一端刪除，爲什麼我需要一個deque而不是一個隊列？ – user997112
@ user997112在大多數實現中，默認情況下，deque和queue類使用相同的數據結構。其實這裏是它的聲明： 'template
我會使用一個ring buffer數據結構。 C++ STL不提供一個，但它是微不足道的。所有你需要的是一個固定大小的數組和一個索引。
下面是一個示例實現，類似於一個我用：
#include <iostream>
template <typename T, size_t TSize>
struct RingBuffer{
enum{array_size = TSize+1};
T array[array_size];
size_t read;
size_t write;
RingBuffer():read(0),write(0){}
T& pop(){
T* p = NULL; //Return NULL reference if empty intentionally
if(read!=write){
p=array+read;
read = (read+1)%array_size;
}
return *p;
}
bool is_empty(){return write==read;}
bool is_full(){return (write+1)%array_size == read;}
void push(T& v){
array[write]=v;
write = (write+1)%array_size;
//Gracefully handle write overflow
if(write==read)read=(read+1)%array_size;
}
};
int main(int argc, const char * argv[])
{
RingBuffer<int, 10> r;
for(int i=0;i<15;++i) r.push(i);
while (!r.is_empty()) std::cout<<r.pop()<<"\n";
return 0;
}
是的，帶有一個std :: vector和一個索引指針。這比一個隊列/ deque恕我直言更有效率。 –
@AlexandreVaillancourt因爲連續的記憶？ – user997112
@ user997112因爲當您按下或彈出某個項目時，無需移動內存。 –
'std :: deque' .... –
我認爲一個德克是如果你想添加/刪除項目雙方？我只想將項目添加到一端並從另一端刪除？ – user997112
@LuchianGrigore：'std :: queue'缺省使用'std :: deque' ... – Jarod42