CODEWITHSUNDEEP
c++stlcontainers
FailedDev
FailedDev

Reputation: 26930

FIFO type of container - Which STL Container is most suitable and why?

I was recently tasked on implementing a buffer which will be used as a temporary storage by a logging class. The logging class itself is a singleton and the observer listener pattern is used. You can expect thousands of messages to be logged with this class.

Now the problem lies here :

We have a trace logging option which is used for deguging purposes. When this option is on, the count of messages/second is increased exponentially. In the release code trace logging is disabled, however a buffer which can store a fixed number of messages e.g. 10000 is dumped into the log IF an error occurs, so that the developers can identify the root of the problem.

If the buffer is full the oldest message is removed to free space for the newest message. 

void Log::storeToBuffer(const LogType_E & type_in, const LogDomain_E & domain_in,const int & id_in, const char * msg_in)
{
    if(this->myEnableTraceBuffer)
    {
        if(static_cast<std::list<Message> * >(this->myRingBuffer)->size() < this->myRingBufferMaxSize)
        {
            static_cast<std::list<Message> * >(this->myRingBuffer)->push_back(Message(type_in, domain_in, id_in, msg_in));
        }
        else
        {
            //buffer full so remove oldest element and add new
            if(static_cast<std::list<Message> * >(this->myRingBuffer)->size() > 0) static_cast<std::list<Message> * >(this->myRingBuffer)->pop_front();
            static_cast<std::list<Message> * >(this->myRingBuffer)->push_back(Message(type_in, domain_in, id_in, msg_in));
        }
    }
}

I implemented this with std::list , very simply using push_back/pop_front to exploit the constant delete/insert execution time. (don't ask for the void casting, not my decision).

But since the buffer size is fixed, and not likely to be changed during the lifetime of an object, maybe vector with explicit index manipulation is more suitable? For example there can be two indeces , start/current starting both at position 0. When the vector is full and we add something start moves to position 1 and and current to position 0, thus when printing the result we have the right order.

Maybe another STL container is more suitable for this kind of thing?

Thank your for your patience to read this long wall of text. I am here to answer any questions.

Upvotes: 5

Views: 3963

Answers (4)

Xeo
Xeo

Reputation: 131799

Ever heard of std::deque? :)
It allows amortized constant time random access and constant time push/pop operations on both sides. As such, it can be easily used as a FIFO queue.

That said, since it can be used as such so easily, there is a container adaptor std::queue, though it doesn't offer random access and an iterator interface.

Upvotes: 2

Christian Rau
Christian Rau

Reputation: 45948

What you are looking for is a double ended queue, where elements can be added removed from the front/back and the C++ standard library's version of this is std::deque. It is similar to a std::vector in its functionality (e.g. access by index, but beware, no guaranteed continous storage) but supports fast insertion and deletion at the front and back. I think internally it is actually implemented as a plain array used like a ring buffer.

The only problem I see here is that it doesn't provide a reserve method, I think. So you cannot say from the beginning that it should make room for your potential 10000 elements and have to take some reallocations into account. But these should amortize, like for vectors. Still better than std::list's 10000 or more small allocations. Once it has its size of 10000 elements there shouldn't be any allocations anymore, whereas a std::list would constantly deallocate and allocate new objects.

Actually you can also use std::queue, which by default uses std::deque as its underlying container type and only provides the few functions neccessary for a FIFO queue. But in this case you won't be able to access individual elements or iterate over all elements, which might be needed for your output logic.

Upvotes: 2

je4d
je4d

Reputation: 7838

Whilst the std::list's push_back/pop_front are constant time, they will use heap allocation, which is likely to be your bottleneck here.

The approach you describe with std::vector will eliminate the heap allocation, and likely go faster as a result. Using std::vector as you described is a circular buffer, and if you can use boost then there's a stl compliant one available here: http://www.boost.org/doc/libs/1_47_0/libs/circular_buffer/doc/circular_buffer.html

Upvotes: 2

Mark Ransom
Mark Ransom

Reputation: 308206

The std::deque can efficiently insert or delete at either the beginning or the end, making it an excellent structure for a buffer. It can be used as the template type for std::queue which would be perfect for your application - just check the size of the queue each time you do a push, and pop if the size is over the maximum.

Upvotes: 3

Related Questions