CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10
  1. #1
    Join Date
    Jun 2017
    Posts
    5

    Lightbulb C++ & Qt optimal way to pass Vector<T> to another object

    Hi

    I recently started to refresh my C++ knowledge - I only done few basic C++ apps before - and Qt.
    Now, I did manage to get my Qt stuff working, including custom QAbstractListModel implementation and although this is not relevant (and knowledge of Qt in general is not needed to answer my question), it may give people who are familiar with it a bit more insight.

    I have a library made of two classes, let's call them Loader and Record. The loader loads data from SQLite database into a Vector<Record>. The class Record contains several strings (std::string), plenty of integers (signed, unsigned, shorts) and also a lot of booleans. This is how my vector is initialized:

    Code:
    // Loader.h
    Vector<Record> records;
    
    // Loader.cpp
    Loader::Loader() {
        records.reserve(30000);
    }
    Having in mind that it will be passed to my QAbstractListModel implementation that must be able to:
    1. Access stored objects by index to read their properties
    2. Update stored objects by index
    3. Remove stored objects by index
    4. Remove stored objects by Record instance (or pointer to it?)
    5. Add new objects at certain positions (to keep the order of elements based on one of their properties)
    6. Ensure uniqueness based on one of the properties [identifier]
    7. Find one of the objects based on some of the properties

    What really should I return from my Loader class and what kind of data structure would be suitable to hold what has been returned from Loader in my QAbstractListModel? (or structures for that matter).

    I came up with such approach:
    1. Return shared_ptr to this Vector<Record> from my Loader
    2. To ensure uniqueness, use std::unordered_set holding identifiers

    As far as I know this will allow me to achieve goals 1, 2, 3, 6 in efficient manner, but I'm unsure about points 4, 5 and 7. This would also mean vector's elements are not copied (or am I wrong?) which is what I'd like to avoid.

    So, would you find my approach correct or is there any room for improvements? Would you suggest another way of doing it, that would either be more performant and still readable or be easier to read and keep performance of my approach?

    Forgive me if this question sounds silly, but I've spent last few years working mainly with PHP, so no pointers and no thinking of what type of data structure / collection is used in most cases.

  2. #2
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: C++ & Qt optimal way to pass Vector<T> to another object

    When you remove a vector object, do you want to keep the existing element order?

    If you want to keep the order, then removing a vector object will mean a partial copy of the vector (how much depends upon the position in the vector). Also inserting an object at any position except at the end also means a partial copy of the vector - or a full copy if the new size of the vector exceeds the vector capacity.

    Remove a vector item based upon value held (record) will require a search of the vector to find the required item. This is also true to finding a record based upon record values.

    Yes, an unordered_set can be used for checking uniqueness of identifiers.

    Which of the required activities will be used the most frequent - insert/deletion or access?

    Have you got control on the code used to access the vector? eg for deletion, rather than actually delete mark the item as not used - but then that means that access code etc needs to be aware of this.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  3. #3
    Join Date
    Jun 2017
    Posts
    5

    Re: C++ & Qt optimal way to pass Vector<T> to another object

    Thank you for the questions (I find questions more rewarding in terms of knowledge than answers to be honest). Let me try to answer them the best way I can.

    When I remove vector element, let's say I have 10 elements in my vector with following IDs:
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

    If I remove element at index 5 (so the ID is 4), I'd like to keep the order, so I'd end up with:
    1, 2, 3, 5, 6, 7, 8, 9, 10.

    When I add a new element with ID 4, I want it back at index 5 assuming the rest of elements are intact by that time.

    So answering your question, yes, I need to keep the order at all times.

    I'm afraid there's no simple answer to question about frequency, because at first there will be plenty of inserts and deletes (because the database needs to be populated), but afterwards I believe most frequent operations are going to be access (read and write) of a specific element.

    To answer your last question, I do have all code available and control over it. If by that you mean the method of Loader class that will return my data (in Vector or anything more suitable for that purpose, if that would be better) to my application, so I can pass it further to my QListModel. So the pseudo code for what I was about to do:
    Code:
    Loader l;
    std::shared_ptr<Vector<Record>> records = l.loadRecords(); // should I return something other than shared_ptr to my records Vector, or perhaps use a different data structure to hold these records
    
    MyListModel *model = new MyListModel();
    model->setData(records);
    As for marking as deleted, this would be easy, indeed. But I'm not sure how I can then filter my list view to display only undeleted items? I think this would be possible if I was using <data structure best suitable for random deletion> (maybe map<int, shared_ptr<Record>> where key would be record index) of pointers to objects as data source for the UI (so I can easily remove the pointer if object is marked as deleted) that would be synchronized with my Vector<Record> instance?

    #EDIT
    Also I'm not entirely sure I need to use shared pointers as opposed to "regular" pointers in this case, I just started with C++11 standard (it was not there back when I was learning C++)
    Last edited by Zikk; June 23rd, 2017 at 10:06 AM.

  4. #4
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: C++ & Qt optimal way to pass Vector<T> to another object

    because at first there will be plenty of inserts and deletes (because the database needs to be populated), but afterwards I believe most frequent operations are going to be access (read and write) of a specific element.
    Over what time-scale - as a vector's (or any container) contents are 'lost' when the program ends unless they saved and then restored when the program is started.

    For many inserts/deletions, a vector is not the best container to use because of the overhead of copying when deleting/inserting (especially when the order has to be maintained). How critical is it to access by position rather than by some key?. If the requirement to access by position rather than by reference to some property (eg identifier) can be removed (in the above example, access by id 4 would be fine but not by index 5), then a map may be more suitable with a key as the identifier and the value the rest of the record?? See http://www.cplusplus.com/reference/map/map/
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  5. #5
    Join Date
    Jun 2017
    Posts
    5

    Re: C++ & Qt optimal way to pass Vector<T> to another object

    Quote Originally Posted by 2kaud View Post
    Over what time-scale - as a vector's (or any container) contents are 'lost' when the program ends unless they saved and then restored when the program is started.

    For many inserts/deletions, a vector is not the best container to use because of the overhead of copying when deleting/inserting (especially when the order has to be maintained). How critical is it to access by position rather than by some key?. If the requirement to access by position rather than by reference to some property (eg identifier) can be removed (in the above example, access by id 4 would be fine but not by index 5), then a map may be more suitable with a key as the identifier and the value the rest of the record?? See http://www.cplusplus.com/reference/map/map/
    Well, I think I didn't make it clear enough, the time-scale is really undefined (but it will be used in two stages, first one will be populating the database, so many inserts and deletions, after a while it will become stable and then the app would be mostly used to edit records). I thought it was rather clear that this data will be persisted back to SQLite (and later, when I deal with schema creation, to flatbuffer based file), so forgive me for leaving this out of the equation.

    Well, it is critical to access by position, because this is how QAbstractListModel and related QListView work, they use indices. So there's basically no other way to do this access by index. Otherwise this thread would not even exist.

    Now that I think of it, I should have provided more details about the application itself. The application will be a GUI for this database (collection of records) editor. I said that at the beginning it will be used for inserts/deletions mostly, but I should have said that they will be added one at a time, by the user. So unless using a vector means that it takes few seconds to insert a new element or it will become slower and slower over time (as in, during a single run, but as far as I understand, vector is kind of a resizable array, so deletions and insertions should not fragment the memory used by it), I am fine with it.

    Also to give you a better picture of the amount of elements to be there, I think it will grow to 30000~ very quickly and then will be mostly used for edition, to grow a bit after some time (let's say 5000 elements added within a week, with 6 months interval).

    Another thing is I will most likely encapsulate my container in a class (since I want to track uniqueness too, so a class containing this vector + unordered_set with mutators to keep them in-sync), I can really use more than two containers, e.g. I could use an additional map of <int, int> that would use row index as a key and vector position as a value. That would mean my Vector could be out of order and the order itself would be enforced by this map:
    model wants row 6 -> check key 6 in map and get value X -> return vector[X]

    Not sure if I didn't miss anything here.
    Last edited by Zikk; June 23rd, 2017 at 12:29 PM.

  6. #6
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: C++ & Qt optimal way to pass Vector<T> to another object

    I could use an additional map of <int, int> that would use row index as a key and vector position as a value. That would mean my Vector could be out of order and the order itself would be enforced by this map:
    model wants row 6 -> check key 6 in map and get value X -> return vector[X]
    Yes, but this adds complexity and potential problems if the two get out of step. Before going down such routes, I would suggest you consider test profiling to see whether the performance from just a vector warrants this. From the initial requirement, just using a vector looks like 4) and 7) would require a search and 3) and 5) would require vector copying. So 3), 4), 5) & 7) could potentially be inefficient. But whether this results in unacceptable performance or not, only test profiling will reveal.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  7. #7
    Join Date
    Jun 2017
    Posts
    5

    Re: C++ & Qt optimal way to pass Vector<T> to another object

    Quote Originally Posted by 2kaud View Post
    Yes, but this adds complexity and potential problems if the two get out of step. Before going down such routes, I would suggest you consider test profiling to see whether the performance from just a vector warrants this. From the initial requirement, just using a vector looks like 4) and 7) would require a search and 3) and 5) would require vector copying. So 3), 4), 5) & 7) could potentially be inefficient. But whether this results in unacceptable performance or not, only test profiling will reveal.
    I see, I also realized that std::map would not be suitable either, because any insert or delete would require me to re-map all index -> vector_index associations (so if I remove by index 3, I need to move 4th element map[4] to map[3] and keep moving all elements after 3 to their index-1). I think I will need a combination of vector + map + set in a way that:
    - vector holds my records
    - map use identifier as a key and index of vector as value
    - set stores identifiers

    This way my set's index will be row index, something like that:
    Code:
    [return type] getRecord(int index) {
        uint16_t identifier = my_set[index];
        size_t vector_index = my_map[identifier]; 
        auto record = (*my_vector_ptr)[vector_index]; // vector is a pointer, just a reminder
         
        /* here I'm also not sure what should be returned really? As far as I understand record will be const_iterator, is returning it a bad thing? */
        return record; 
    }
    Obviously I see the out-of-sync issue here that may lead to problems and exceptions, so I am definitely going to encapsulate it within a class that will allow deletion and insertion of elements and keep all underlying data structures in sync.

  8. #8
    Join Date
    Oct 2008
    Posts
    1,456

    Re: C++ & Qt optimal way to pass Vector<T> to another object

    FYI, the boost multindex library tries to solve exactly these kind of problems ( eg. managing invariants of multiple incapsulated containers ).
    There's a learning curve if you're not accustomed to stl-like containers and boost, but it's worth it considering the complexity of an hand made (quality) solution.

  9. #9
    Join Date
    Oct 2008
    Posts
    1,456

    Re: C++ & Qt optimal way to pass Vector<T> to another object

    that said, unless I got something wrong, personally I would also consider incapsulating sqllite calls behind a thin interface, and focus on more gui oriented data structures instead ( that is, say, in an MVC scenario, the controller should talk to the database model and the view model without any intermidiate data structures, assuming the data is just visualized/edited ) ...

  10. #10
    Join Date
    Jun 2017
    Posts
    5

    Re: C++ & Qt optimal way to pass Vector<T> to another object

    Quote Originally Posted by superbonzo View Post
    FYI, the boost multindex library tries to solve exactly these kind of problems ( eg. managing invariants of multiple incapsulated containers ).
    There's a learning curve if you're not accustomed to stl-like containers and boost, but it's worth it considering the complexity of an hand made (quality) solution.
    That sounds interesing. I may have to take a look at it. Well, I do this project mostly for learning purposes, so I see nothing wrong in actually learning a new thing. I managed to familiar myself with STL containers (at least theoretically) over last few days, I've been working a lot with C# generic collections, so apart from obvious differences between C# and C++, they are very similar in usage. That being said, thank you for bringing up the multindex lib. I know this may sound crazy, since there's ready solution for my problem, but I think I'm willing to give it a try myself, one reason is to learn, another one is to avoid introducing boost dependency.

    Quote Originally Posted by superbonzo View Post
    that said, unless I got something wrong, personally I would also consider incapsulating sqllite calls behind a thin interface, and focus on more gui oriented data structures instead ( that is, say, in an MVC scenario, the controller should talk to the database model and the view model without any intermidiate data structures, assuming the data is just visualized/edited ) ...
    You are definitely right, but while I use SQLite database now to have direct access to data, I have a plan to learn about and practice the use of flatbuffer, so the SQLite database will be replaced by a binary file once I find the right way to complete current task.

    I also wanted to point out that I am completely aware this is probably being a premature optimization and using just the vector (maybe vector of references or pointers) should be more than enough for amount of data I'm dealing with and this would not affect my UI responsiveness. I am looking for the optimal way purely due to curiosity and desire to learn

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured