CODEWITHSUNDEEP
c++dictionarythread-safetycontainersdeque
Ernie Mur
Ernie Mur

Reputation: 561

Which C++ stl container should I use?

Imagine the following requirements:

measurement data should be logged and the user should be able to iterate through the data.

uint32_t timestamp;
uint16_t place;
struct SomeData someData;

EDIT: - The container should all the memory which is not used otherwise, therefore it can be large.

I am not sure which container I should use. It is an embedded system and should not use boost etc.

I see the following possibilities:

std::vector - drawbacks: The insertion at the end requires that all objects are copied and during this time another thread cannot access the vector. Edit: This can be avoided by implementing it as a circular buffer - see comments below. When iterating throught the vector, I have to test the place ID. Maybe it might also be a problem to allocate much memory as one block - because the memory could be segmented?

std::deque - compared to std::vector insertion (and pop_back) is faster but memory requirement? Iterators do not become invalid if the insertion is at the end. But I still have to iterate and test the second ID ("place"). I think it does not need to allocate all the memory in one big block as it is the case with vector or array. If an element is added in front and another one is removed at the end (or removed first and added after), I guess there does no memory allocation take place?

std::queue - instead of deque, I should rather use a queue? Is it true that in many implementations a queue ist implented just as a deque?

std::map - Like deque any iterators to existing elements will not become invalid. If I make the key a combination of place and timestamp, then iteration through the map is maybe faster because it is already sorted? Memory requirements of a map?

std::multimap - as the number of places is not constant I cannot make a multimap with "place" as the index.

std::list - has no advantage over deque here?

Some suggested the use of a circular buffer. If I do not want that the memory is allocated as one big block I still have to use a container and most questions above stay valid.

Update: I will use a ring buffer as suggested here but using a deque as the underlying container. In order to being able to scroll fast through the datasets with the preselected "place" I will eventually introduce two additional indices into the data struct which will point to the previous and the next index with the same place.

How much memory will be used? In my special case the size of the struct is 56 bytes. The gnu lib uses 512 bytes as minimum block size, the IAR compiler 16 bytes. Hence the used block size will be 512 or 56 bytes respectively. Besides two iterators (using 4 pointers each) and the size there will be a pointer stored for each block. Therefore in the implementation of the iar compiler (block size 56 bytes) there will be 7 % overhead (on a 32 bit system) compared to the use of a std::vector or array. In the gcc implementation there will fit 9 objects in the block (504 bytes) while 512 + 4 bytes are needed per block which is 2 % more.

The block size is not large but the continuous memory size needed for the pointer array is already relatively large, especially for the implementation where one block is one struct.

A std::list would need 2 pointers per struct which is 14 % overhead in my case on 32 bit systems.

Upvotes: 2

Views: 649

Answers (1)

Useless
Useless

Reputation: 67733

  1. std::vector

    ... the memory could be segmented?

    No, std::vector allocates contiguous memory, as is documented in that link. Arrays are also contiguous, but you might just as well use vector for this.

  2. std::deque is segmented, which you said you didn't want. Or do you want to avoid a single large allocated block? It's not clear.

    Anyway, it has no benefit over vector if you really want a circular buffer (because you'll never be adding/removing elements from the front/back anyway), and you can't control the block size.

  3. std::queue

    ... Is it true that in many implementations a queue is implented just as a deque?

    Yes, that's the default in all implementations. See the linked documentation or any decent book.

    It doesn't sound like you want a FIFO queue, so I don't know why you're considering this one - the interface doesn't match your stated requirement.

  4. 'std::map`

    ... iteration through the map is maybe faster because it is already sorted?

    On most modern server/desktop architectures, map will be slower because advancing an iterator involves a pointer chase (which impairs pipelining) and a likely cache miss. Your anonymous embedded architecture may be less sensitive to these effects, so map may be faster for you.

    ... Memory requirements of a map?

    Higher. You have the node size (at least a couple of pointers) added to each element.

Upvotes: 1

Related Questions