C++:具有多个元素的高效获取/放置的队列？

Question

所以,我觉得在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).(这是一个非常天真的实现 - 每个dequeue都会导致队列中剩余数据的数组副本.)

附加要求(如果需要,我可以在包装器中实现这些要求): - 我需要能够指定缓冲区的最大大小 - 如果可用的数据少于请求的数据,则读取操作应该检索所有可用数据 - 写操作应该执行如果请求的写入超过最大大小并返回失败指示,则不执行任何操作

所以,我的问题:1)stringbuf是否足够？假设不需要调整大小,读/写操作O(1)是否相对于缓冲区中的数据量？(显然,他们可能是所请求项目数量的O(n).)

2)还有其他一些我没有看到的课程就够了吗？

提前致谢!

Answer 1

嗯......你有没有尝试过这个显而易见的事情:

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);
    }
};

对不起,我现在感觉还不够雄心勃勃地添加锁定和你要求的返回值,但两者都不应该非常困难.但是,我没有改变您的返回值,而是更改接口以使用迭代器(或者,如果您真的坚持,则引用向量).

这保证在插入/移除的元素数量上是线性的.

Answer 2

您可以使用使用std::stringstream推入队列并write使用 弹出队列的位置吗read？