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.

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.

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++)

Quote:

---

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/

Quote:

---

Originally Posted by 2kaud

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.

Quote:

---

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.

Quote:

---

Originally Posted by 2kaud

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.

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

Quote:

---

Originally Posted by superbonzo

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

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 :)