C++ 高效循环列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9516711/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Efficient circular list
提问by mahmood
I want a simple yet efficient circular buffer/queue. If I use std::vector, I have to do this:
我想要一个简单而高效的循环缓冲区/队列。如果我使用std::vector，我必须这样做：
if ( v.size() >= limit ) {
std::vector<int> it = v.begin();
v.insert( it, data );
v.erase( it+1 );
}
Is there any simpler solution?
有没有更简单的解决方案？
回答by Tom Whittock
You want to maintain the size of the buffer, overwriting older items. Just overwrite the old ones as time goes on. If you want to deal with the case where nItems < limit, then you would need to deal with that, this is just a simple example of using modulo to insert into a fixed size buffer.
您想保持缓冲区的大小，覆盖旧项目。随着时间的推移，只需覆盖旧的。如果您想处理 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;
}
That method of insertion will keep the last 10 elements in the buffer.
这种插入方法将保留缓冲区中的最后 10 个元素。
回答by Luchian Grigore
A std::listmight be an easier alternative to building a list than std::vector. There's also std::queue.
Astd::list可能比std::vector. 还有std::queue。
It's also funny that you're using a vectorto implement a circular queuebut ask a question on how to implement a circular list. Why not use a map?
同样有趣的是，您使用向量来实现循环队列，但问了一个关于如何实现循环列表的问题。为什么不使用地图？
回答by Fantastic Mr Fox
In c++11for a fixed size alternative you should be using std::array:
在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;
}
回答by Reza Hajianpour
You can use your vectors as usual, and then create a get_element(index) function to make it feel circular. It's pretty fast and straight-forward, since it's just integer manipulation.
你可以像往常一样使用你的向量，然后创建一个 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];
}
Then use it like:
然后像这样使用它：
int result = get_element<int>(myvec, 256);
Note that any index smaller than 0 starts rotating from the last element of your vector, which is of course intended.
请注意，任何小于 0 的索引都从向量的最后一个元素开始旋转，这当然是有意的。
回答by Reza Hajianpour
Try std::deque. The interface is like using a std::vector but insert and removal at beginning and end are more efficient.
试试 std::deque。接口就像使用 std::vector 但在开始和结束时插入和删除更有效。
