C++: Queue with efficient get/put of multiple elements?

Question

So, I feel like there should be a good, built-in solution for this in C++, but I'm not sure what it is.

I need a queue (ideally thread-safe, but I can wrap it in synchronization myself if need be) that handles groups of bytes efficiently - allowing reads/writes of different sizes.

so, the interface looks like e.g.

//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)

I can write one myself without too much difficulty, but it seems like this ought to be something that's easily done off the shelf.

The best thing in the STL looks like it might be a stringbuf - I'd have to pair calls to sgetc/pubseekoff by hand, but it seems like it would work.

I'm looking to do this as a drop-in replacement for a current queue implementation that's a performance problem; reading in this implementation is O(N) on the amount of data in the queue. (It's a very naive implementation - every dequeue results in an array copy of the remaining data in the queue.)

Additional requirements (I can implement these in a wrapper if need be): -I need to be able to specify a maximum size of the buffer -Read operations should retrieve all available data if less data is available than was requested -Write operations should do nothing if the requested write would exceed the maximum size and return a failure indicator

So, my questions: 1) is stringbuf sufficient? Are the read/write operations O(1) relative to the amount of data in the buffer, assuming no resizing is necessary? (obviously, they'd potentially be O(n) on the number of items requested.)

2) Is there some other class that I'm not seeing that would suffice?

Thanks in advance!

Answer 1

Hmmm...have you tried the obvious:

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

Sorry, I'm not feeling quite ambitious enough at the moment to add locking and the return values you asked for, but neither should be terribly difficult. Instead of fiddling with your return values, however, I'd change the interface to use iterators (or, if you really insist, a reference to a vector).

This is guaranteed to be linear on the number of elements inserted/removed.

Answer 2

If you want a really fast efficient implementation, I would go with a simple circular buffer implementation which means you can do your reads in one or two copies (depending on whether you're wrapping through the end/beginning of your buffer). This allows you to use memcpy which in my experience almost always out-performs looping through lots of elements to do your copying.

If the performance is less critical though I'd go with Jerry's answer.