C++：高效地获取/放入多个元素的队列？

所以，我觉得在C++中应该有一个很好的内置解决方案，但我不确定它是什么。C++：高效地获取/放入多个元素的队列？

我需要一个队列（理想的线程安全的，但我可以在自己的同步包裹它如果需要的话）能够有效地处理字节组 - 允许读取/不同尺寸的写入。

因此，界面看起来像例如

//removes the first bytesToRead elements from the front of the queue and places them in array; returns the actual number of bytes dequeued 
int dequeue(unsigned char *array, int bytesToRead) 
//Adds bytesToWrite elements from array to the end of the queue; does nothing and returns 0 if this would exceed the queue's max size 
int enqueue(unsigned char *array, int bytesToWrite)

我可以写一个自己不会有太大困难，但看起来这应该是东西是很容易现成的完成。

在STL中最好的东西看起来像它可能是一个stringbuf - 我必须手动配对调用sgetc/pubseekoff，但它似乎会工作。

我正在寻找这样做，作为性能问题的当前队列实现的插入替换;在这个实现中读取的是队列中的数据量的O（N）。（这是一个非常天真的实现 - 每个出队导致队列中剩余数据的阵列副本。）

附加要求（如果需要，我可以在包装中实现这些要求）： - 我需要能够指定缓冲区 - 读取操作的最大大小，如果较少的数据可用比请求 - 写入操作应该做什么，如果所要求的写会超出最大尺寸，并返回一个失败指示

所以应该检索所有可用的数据，我的问题： 1）stringbuf是否足够？假设不需要调整大小，读/写操作O（1）是否与缓冲区中的数据量有关？（显然，他们会潜在地为O（n）上的项数要求。）

2）是否有我没有看到这就够了一些其他类？

在此先感谢！

来源

2011-03-28 Sbodd

我怀疑，除非你只是传递指针通过一个链表实现队列，你不必将数据复制到出队将会失去其复制或分配时的额外开销获得任何好处，以缓冲你入选它。 – 2011-03-28 22:19:48

@Jon：听起来好像它不是正在复制的出队元素，而是将整个剩余的队列向下移动。有很多数据结构比这更好。 – 2011-03-28 22:27:26

啊，好的，我没有从OP的描述中得到。 – 2011-03-28 22:29:49

您可以使用std::stringstream哪里你推入队列与write和弹出队列read？

来源

2011-03-28 21:50:59

嗯......你试过明显：

class queue { 
     std::deque<unsigned char> data; 
public: 
    int enqueue(unsigned char *array, int bytesToWrite) { 
     data.insert(data.end(), array, array+bytesToWrite); 
    } 

    int dequeue(unsigned char *array, int bytesToRead) { 
     std::copy(data.begin(), data.begin()+bytesToRead, array); 
     // or, for C++11: std::copy_n(data.begin(), bytesToRead, array); 

     data.erase(data.begin(), data.begin()+bytesToRead); 
    } 
};

对不起，我不是现在感觉相当宏大，足以增加了锁定，并要求您提供的返回值，但也应该是可怕的难。然而，我并不是摆弄你的返回值，而是改变接口来使用迭代器（或者，如果你真的坚持的话，可以引用一个向量）。

这是保证插入/删除元素的数量是线性的。

来源

2011-03-28 22:09:46

它应该是'阵列+ bytesToWrite' – 2011-03-28 22:20:46

@Mikael佩尔森：哎呀 - 谢谢你。固定。 – 2011-03-28 22:25:17

在你出列功能，您可以使用指针算术，在我看来，该标准明确表示，双端队列不允许“通过指针算术安全访问”。或者我错了。 http://www.cplusplus.com/reference/stl/deque/ – 2011-03-28 23:12:23

如上所述，std::stringstream可能是最简单和最好的解决方案。

另一种替代方法是std::deque，它会为您提供您想要的效率（从队列的任何一端进行所有读取/写入的常量分摊，并且通常远小于容量耗尽时重新分配的O（N））。唯一的缺点是，std::deque不支持指针运算（因为所有的元素不一定是连续的（成块）），所以你不会是能够做到的读/写操作的模块，你将不得不遍历，具体如下：

std::deque<unsigned char> buf; 

int dequeue(unsigned char *array, int bytesToRead) { 
    int result = std::min(bytesToRead, buf.size()); 
    std::copy(buf.begin(), buf.begin() + result, array); 
    buf.erase(buf.begin(), buf.begin() + result); 
    return result; 
}; 

int enqueue(unsigned char *array, int bytesToWrite) { 
    buf.insert(buf.end(), array, array + bytesToWrite); 
    return bytesToWrite; 
};

你应该让后面的实现检查是否达到了最大容量并因此调整结果值。

来源

2011-03-28 22:16:10

如果你想要一个真正快速高效的实现，我会去用一个简单的循环缓冲区执行，这意味着你可以做你读取一个或两个拷贝（取决于你通过你的缓冲区的末尾/包开始）。这允许你使用memcpy，在我的经验中，它几乎总是通过很多元素循环执行你的复制。

如果性能不那么重要，虽然我跟杰里的回答去。

来源

2011-03-28 22:28:35

C++：高效地获取/放入多个元素的队列？

回答

相关问题