Results 1 to 4 of 4

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

  1. #1
    Join Date
    Jan 2008
    Location
    Germany
    Posts
    80
    Thanks
    6
    Thanked 1 Time in 1 Post
    Qt products
    Qt4
    Platforms
    MacOS X Windows

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

    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...

  2. #2
    Join Date
    Jan 2008
    Location
    Poland
    Posts
    687
    Thanks
    4
    Thanked 140 Times in 132 Posts
    Qt products
    Qt4 Qt5
    Platforms
    Unix/X11 Windows

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

    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:
    Qt Code:
    1. 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.
    Last edited by faldzip; 7th August 2009 at 10:50.
    I would like to be a "Guru"

    Useful hints (try them before asking):
    1. Use Qt Assistant
    2. Search the forum

    If you haven't found solution yet then create new topic with smart question.

  3. The following user says thank you to faldzip for this useful post:

    numbat (7th August 2009)

  4. #3
    Join Date
    May 2009
    Posts
    8
    Thanks
    3
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

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

    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.

  5. #4
    Join Date
    Aug 2008
    Location
    Ukraine, Krivoy Rog
    Posts
    1,963
    Thanked 370 Times in 336 Posts
    Qt products
    Qt3 Qt4 Qt5
    Platforms
    MacOS X Unix/X11 Windows

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

    read this article. it should be helpful.
    Qt Assistant -- rocks!
    please, use tags [CODE] & [/CODE].

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.