2

我正在尝试为新项目选择合适的数据类型以满足以下要求：

  • 高度！时间紧迫（用于输入数据）
  • 没有随机插入或对容器中的数据进行任何操作（只读并按顺序插入）
  • 大小将在编译时固定（因此不需要动态分配）
  • 数据将在某个定义的时间段（通过线程或服务）后按顺序删除，并且空白空间必须再次可用于新的数据。

前任。假设将 1,2,3,4,5,6 插入容器中。一段时间后，将删除 6 并插入 7，因此列表将是 7、1、2、3、4、5，然后 5 将被删除等......但大小必须相同。

我想知道从性能和内存的角度来看，哪种数据结构最适合我的情况。

谢谢...

编辑：顺便说一下，它与基本 FIFO 逻辑有点不同，因为假设我们创建了 10 个元素（大小）数据容器，但仅插入了 3 个元素，即使它还没有到达容器的末尾（大小限制），如果指定的时间过去了，它将被删除。

顺便说一句，我正在考虑使用 boost:array 但对 std:vector 和 std:deque 有点困惑。在这种情况下有什么特别的优势吗？

4

5 回答 5

6

您需要的是在固定大小数组上构建的循环缓冲区，这是非常简单且最快的数据结构。

您可以编写自己的循环缓冲区类或尝试使用循环缓冲区的 boost 实现http://www.boost.org/doc/libs/1_54_0/libs/circular_buffer/doc/circular_buffer.html

于 2013-11-05T09:29:50.327 回答
1

看起来您需要一个queue，可能由一些支持 FIFO 的优化的固定大小容器支持。

于 2013-11-05T09:14:16.597 回答
0

从我们的数据结构和算法类中我们都知道，在插入和删除的地方很可能我们应该使用某种链表。不过，我们所知道的可能是错误的。

现代内存正在以极快的速度复制大量数据（因此您不必像考虑复制数据那样担心）并使用缓存进行线性搜索（链表结构将有效地击败）。这两个因素结合起来很可能意味着您应该使用一个好的旧向量或 boost::array。

但不要相信我的话，这里是 Bjarn Stroustrup 解释这一切。

于 2013-11-05T09:42:27.527 回答
0

您需要由 std::vector 支持的具有一些固定容量的 std::queue：

std::vector<YourType> underlying_storage(capacity);
std::queue<YourType, std::vector<YourType>> queue(std::move(underlying_storage));

// Now your queue is backed up by vector with predefined capacity
于 2013-11-05T09:48:39.980 回答
0

最快的解决方案是静态分配的数组，您可以在其中使用 head/tail/count 自己处理队列；例如

#define MAX_NUMBER_OF_ELEMENTS 10

// Use statically-allocated memory
unsigned char raw_buf[MAX_NUMBER_OF_ELEMENTS * sizeof(X)];
X * const buf = (X *)&raw_buf[0];
int head, tail, count;

// Returns the address for a new element on the queue
inline void *add_element_address() {
    void *p = &buf[head];
    if (++head == MAX_NUMBER_OF_ELEMENTS) head = 0;
    count++;
    return p;
}

// Removes oldest element from the queue
inline void remove_element() {
    buf[tail].~X();
    if (++tail == MAX_NUMBER_OF_ELEMENTS) tail = 0;
    count--;
}

// Get the n-th element from the queue where 0 is the
// last added element and count-1 is the oldest one.
X& element(int index) {
    index = head - index - 1;
    if (index < 0) index += MAX_NUMBER_OF_ELEMENTS;
    return buf[index];
}

void add_element(... constructor arguments ...) {
    new (add_element_address()) X(... constructor arguments ...);
}

使用这种方法，缓冲区将位于内存中的固定地址（因此也释放寄存器）并且对象上不需要任何类型的副本（它们是使用placement new直接构建的）。添加、删除和索引访问操作都是O(1).

于 2013-11-05T10:10:20.490 回答