Looking for the best container class to store several thousands of items

[schall_l]

Hi,

I am wondering what would be the best type of container class to use if I want to store the log of communication of an industrial bus. Each item is a structure, containing a date and time stamp, some kind of identifier and several bytes of data’s. Supposing there is up to 100 items to store per seconds and that it is very unlikely that I need to remove items from the container or to sort the container. I guess that my primary concern would be to find something that is very efficient in the amount of memory used to store my log.

So far QVector seems to be a good choice.

On the other side I am also looking into ways to limit the amount of data’s in the log – for example by implementing a ring buffer which a fixed size – let’s says several thousands of items – so that it can keep the log for the last minutes. With QVector I could only see it work by assigning a fixed size and by working with a firstItem and lastItem indicator. If I do not want to fix the size at the beginning would then QlinkedList or QList be a better choice? Waht would be the downside on the memory consumption ?

Also, as a last indication, I would like to be the list the source of data’s from a QAbstractItemModel class, so that I can attached some views and filtered views to it. I founf out that this may cause the things to be tricky too. For example the filter is usually computed when an item is added to the model; in case I am using a ring buffer, new items may replace older items; in such a case I need to evaluate the filter for the new item, but what's about the replaced item ?

If someone has some experience with such kind of things...

[faldzip]

As I understand, what you really need is fast insertion/prepending/appending, right?

Than QVector isn't the best choice, because:
- insertion is linear - O(n)
- prepending is linear - O(n)
- appending is constant but only in an average case - it can be O(n) in some cases.
QVector (like std::vector) stores it's data in one coherent piece of memory. It gives you fast index lookup (it's rather for reading the data from random indices) but it's 1 bad thing: when number of items exceeds vector size than the whole vector has to be realocated (bigger one-piece fragment of memory has to be allocated and all data has to be copied to that new location).

The fastes insertion/prepending/appending gives you a real linked list - QLinkedList. Ofcourse it has also one bad thing: index lookup in O(n) - so the code:

container.at(n);

container.at(n);

To copy to clipboard, switch view to plain text mode 

works n-times slower than in vector case.
But if you will read data in sequence from begin to end, than use iterator, and there won't be difference.

P.S. If you want to present those data in some view then it would be hard, cause the view will not keep up with displaying new data. If you want to display that log in real time - only QPlainTextEdit has a chance to deal with it. But it's not a view. Maybe you should consider refreshing the view 'on demand' - by pressing a button by user, to get the log for the moment the button was pressed.

[eurodatar]

I would create a custom repository object and use one of the QTL/STL containers as a back-end.

How about using a vector with a good-enough initial size and a sensible resize strategy and expose it as a circular buffer to the clients? You could use another vector as a mask to quickly see which items are expired and which are active.

[spirit]

read this article. it should be helpful.