Jump to content
  • Advertisement
Sign in to follow this  
JustChris

Pointers for sorted containers

This topic is 2812 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

It seems like, since the nature of an STL vector is to store objects in contiguous memory, any such pointer pointing to one object in the vector will no longer be valid if the vector is sorted and the object is moved somewhere else? I noticed that it's likely the cause of crashes in my program now that I have started to code a class to contain a pointer to a vector of objects I sort by name for each insertion. The pointer to the object gives me garbage data after it's been sorted, and the program can't handle it correctly. So to be sure, is this the case? If so, should I just keep a sorted vector of pointers to an unsorted vector of the deep copies, and copy the pointers when I need to access them?

Share this post


Link to post
Share on other sites
Advertisement
It is most certainly the case for your crashes.

I would store those elements in smart pointers and put those in your container of choice:

#include <vector>
#include <boost/shared_ptr.hpp>

std::vector<boost::shared_ptr<Foo>> data;
data.push_back(boost::make_shared<Foo>("arguments for the constructor"));

As long as there is at least one shared_ptr pointing to a specific Foo, it will remain alive.

Share this post


Link to post
Share on other sites
There are probably a few things you can do, but some questions to make everyone's answers better.
1) Why are you sorting it?
2) Why are you storing pointers to it?
3) what are you actually doing? an actual usecase would likely clarify what the actual solution should be.

Because maybe you need a different container (std::map ?).
Maybe you need a better way to get access to your data ( hash_map? ).
Can't tell without you clarifying what you are doing.

Share this post


Link to post
Share on other sites
If you only need to keep a sorted list, you can use std::list and only compare when insertion, you don't need to sort.
And as KulSeran said, you may also need better container, the simple way is std::map or non standard way to use a skip list, to get better performance.

Share this post


Link to post
Share on other sites
I would think std::set is the natural container to use if you want to keep things sorted and you don't want them to move around in memory. But it would be good to understand the details of what you are doing, as others have said.

Share this post


Link to post
Share on other sites
Well, if you want to keep them sorted, and you don't want to modify them. If you do want to modify them, then std::map.

Share this post


Link to post
Share on other sites

There are probably a few things you can do, but some questions to make everyone's answers better.
1) Why are you sorting it?
2) Why are you storing pointers to it?
3) what are you actually doing? an actual usecase would likely clarify what the actual solution should be.

Because maybe you need a different container (std::map ?).
Maybe you need a better way to get access to your data ( hash_map? ).
Can't tell without you clarifying what you are doing.



1. They need to be sorted by the object's name (in a string) so that I can retrieve them by name.
2. I haven't yet but was considering doing this if I couldn't find anything faster for accessing elements
3. I would want to update potentially hundreds or sometimes thousands of 3D objects per frame (but usually not every single object in the container), to change their position, etc. and they will be updated differently.

So far, the sorted vector has been great at retrieving thousands of random objects. I know there is an std::map and my earlier implementation actually used a map, but insertion got very slow when the map got into the size of the thousands (something like 5k). Pushing objects to a vector and then sorting them with a simple comparison function after every push was not too fast, but still noticeably faster. I access items in the vector with a typical binary search algorithm, and it showed to be just as fast as map::find() with lower_bound or sometimes even faster.

hash_map may have the speed I want without the memory referencing problems that come with sorting vectors, but unfortunately I have no experience writing good hashing functions. std::set sounds like it's a good tradeoff, though. I'll try using this container next to check for speed and memory access.

Edit: never mind, I can't use std::set if I want to modify the elements in them. Making copies for modifying, and replacing them with the old elements in the set sounds like more trouble than it's worth.

Share this post


Link to post
Share on other sites
I recommend you try hash_map or unordered_map. You probably don't need a great hash function, so just try to get something basic working. If you do need advice on a hash function, CRCs are nice for this purpose.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!