Looking for a suitable container
Hi, I'm looking for the best suiting std:: container to replace my poorly written own. Mine works for now, but I think it might be wise not to invest time into reinventing the wheel.
What I have written myself is a vector of pointers to objects. Objects are dynamically allocated, and their pointers are stored in the vector. When a pointer is removed from the pointer vector I delete the object aswell.
The reason why I went with a vector of pointers, as opposed to a vector of objects, is because I don't want objects to be reallocated every time the vector expands. This is because I need to access objects elswhere in code and I have no guarantee that my vector hasn't expanded and reallocated in the meantime. For that reason I can't really use vector indices to reference objects either, because the indices of objects in a vector may change if elements are erased in the middle.
The container itself doesn't need to support insertion in middle, and it doesn't matter much where the insertion happens either(front or back), but it does need to support removal in the middle. The container must ensure that pointers are consistent, and must allocate and deallocate them dynamically as they are added||removed.
Is there a std:: container that can do that for me, or should I keep working on my own one?
I was thinking that maybe if I store unique pointers to objects in a vector, and pass a regular pointer to non-owners, then the memory will be managed by the unique pointer, and the container stuff will be handled by the very convenient vector, but I don't have enough experience to be sure that there isn't going to be a huge obvious problem down the road.
What I have written myself is a vector of pointers to objects. Objects are dynamically allocated, and their pointers are stored in the vector. When a pointer is removed from the pointer vector I delete the object aswell.
The reason why I went with a vector of pointers, as opposed to a vector of objects, is because I don't want objects to be reallocated every time the vector expands. This is because I need to access objects elswhere in code and I have no guarantee that my vector hasn't expanded and reallocated in the meantime. For that reason I can't really use vector indices to reference objects either, because the indices of objects in a vector may change if elements are erased in the middle.
The container itself doesn't need to support insertion in middle, and it doesn't matter much where the insertion happens either(front or back), but it does need to support removal in the middle. The container must ensure that pointers are consistent, and must allocate and deallocate them dynamically as they are added||removed.
Is there a std:: container that can do that for me, or should I keep working on my own one?
I was thinking that maybe if I store unique pointers to objects in a vector, and pass a regular pointer to non-owners, then the memory will be managed by the unique pointer, and the container stuff will be handled by the very convenient vector, but I don't have enough experience to be sure that there isn't going to be a huge obvious problem down the road.
| I was thinking that maybe if I store unique pointers to objects in a vector, and pass a regular pointer to non-owners, then the memory will be managed by the unique pointer, and the container stuff will be handled by the very convenient vector, but I don't have enough experience to be sure that there isn't going to be a huge obvious problem down the road. |
That would be the best IMO. Alternatively you could use red-black trees(std::set and std::map), but accessing elements in those is O(log n) not O(1) as in vectors. If you use Red-Black trees, those won't touch the objects you got stored inside when you increase their size, so it's a trade off.
Last edited on
| I need to access objects elswhere in code and I have no guarantee that my vector hasn't expanded and reallocated in the meantime. |
When you delete an object from the vector, you must be certain to remove all those other pointers to the object.
Do you ever need to access objects in the vector by index? Since you say you don't care where they go in the vector, I suspect that the answer is no. In that case, look at std::set as Golden Lizard says. But be sure to check if it guarantees that the objects don't move.
It also sounds like the only purpose of the vector may be to hold the objects for memory management purposes. If that's true, then consider getting rid of it altogether and using shared pointers instead.
i am trying to guess at what all you might be doing, but I am thinking you might like a hash map of a thin object.
By thin object, i mean wrap the pointer to your big object along with some KEY that identifies that object. 2, maybe 3 data elements to your class, and not much more than a dtor and ctor.
Now you can hash that off the KEY and get O(1) access, knowing what is in each pointer without having to iterate and dereference the pointers. As you have it, to search for an item in your list of objects, you have to iterate the vector and look into each pointer. This way, you just key into the map and fetch the item directly, and iteration over all objects is still possible. Or a vector of the thin class might work, if you only iterate and don't need random access / instant access.
Is this a direction you might like?
If you really want to save space in the container, instead of a class, roll out a C style struct with no functions attached to it, data only, and that could reduce it to really 2 integers (pointer is effectively an integer, and the key could be an integer). It would have a fairly tiny footprint.
By thin object, i mean wrap the pointer to your big object along with some KEY that identifies that object. 2, maybe 3 data elements to your class, and not much more than a dtor and ctor.
Now you can hash that off the KEY and get O(1) access, knowing what is in each pointer without having to iterate and dereference the pointers. As you have it, to search for an item in your list of objects, you have to iterate the vector and look into each pointer. This way, you just key into the map and fetch the item directly, and iteration over all objects is still possible. Or a vector of the thin class might work, if you only iterate and don't need random access / instant access.
Is this a direction you might like?
If you really want to save space in the container, instead of a class, roll out a C style struct with no functions attached to it, data only, and that could reduce it to really 2 integers (pointer is effectively an integer, and the key could be an integer). It would have a fairly tiny footprint.
Last edited on
> I was thinking that maybe if I store unique pointers to objects in a vector,
> and pass a regular pointer to non-owners, then the memory will be managed
> by the unique pointer, and the container stuff will be handled by the very convenient vector.
Yes. Yes.
> "pass a regular pointer to non-owners"
That is canonical - use regular pointers where ownership semantics are not involved.
CppCoreGuidelines:
For general use, take T* or T& arguments rather than smart pointers
https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Rf-smart
Take smart pointers as parameters only to explicitly express lifetime semantics
https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Rr-smartptrparam
> "store unique pointers to objects in a vector"
Yes. Avoid falling into the newbie trap of using shared ownership semantics everywhere.
Designs involving needless shared ownership of resources tend to get ugly very soon.
In general: Prefer unique_ptr over shared_ptr. Prefer unique ownership over shared ownership.
Prefer unique_ptr over shared_ptr unless you need to share ownership
https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Rr-unique
> and pass a regular pointer to non-owners, then the memory will be managed
> by the unique pointer, and the container stuff will be handled by the very convenient vector.
Yes. Yes.
> "pass a regular pointer to non-owners"
That is canonical - use regular pointers where ownership semantics are not involved.
CppCoreGuidelines:
For general use, take T* or T& arguments rather than smart pointers
https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Rf-smart
Take smart pointers as parameters only to explicitly express lifetime semantics
https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Rr-smartptrparam
> "store unique pointers to objects in a vector"
Yes. Avoid falling into the newbie trap of using shared ownership semantics everywhere.
Designs involving needless shared ownership of resources tend to get ugly very soon.
In general: Prefer unique_ptr over shared_ptr. Prefer unique ownership over shared ownership.
Prefer unique_ptr over shared_ptr unless you need to share ownership
https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Rr-unique
Thanks for your input guys. There is definitely some reading to be done, regarding the last link to cpp guidelines.
Since I don't access random elements by index(I only access elements by index when I iterate through the entire container), a map seems to work out well for me. I've never used maps before, so it's kind of an excuse to expand my experience, while also making my code more failsafe.
Since I don't access random elements by index(I only access elements by index when I iterate through the entire container), a map seems to work out well for me. I've never used maps before, so it's kind of an excuse to expand my experience, while also making my code more failsafe.
Topic archived. No new replies allowed.