Jump to content
  • Advertisement
Sign in to follow this  
freeworld

i need a good container that can be easly sorted

This topic is 3630 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

Beyond std::vector I'm not too comfortable with any other container, but I'm in need of one that can easily and quickly be sorted by two different values. The sorting I can do on my own I just need one that can remove objects and insert objects, with random access.

Share this post


Link to post
Share on other sites
Advertisement
If the order is not important when the list is not sorted, then items can be inserted and removed from std::vector in O(1). Just insert with push_back, and remove by replacing the removed item with back() and pop_back() the copy. Otherwise you probably need to use a O(N log(N)) container like std::map (or more than one, if you need to index the objects two different ways).

Share this post


Link to post
Share on other sites
can the sort algorithim work with vector if the stored values are structures... ie can I choose what variable it sorts the vector by?

Share this post


Link to post
Share on other sites
If your object has an operator< it will use that by default, otherwise you can specify a comparison function or functor as a third parameter to std::sort.


struct Foo
{
int i;
std::string s;
};

// Sort by Foo::i, then by Foo::s
bool isFooLess(const Foo &a, const Foo &b)
{
if (a.i != b.i)
{
return a.i < b.i;
}
return a.s < b.s;
}


void sortFooVector(std::vector<Foo> &foo)
{
std::sort(foo.begin(), foo.end(), isFooLess);
}


Share this post


Link to post
Share on other sites
std::set? or any of the STL containers which have insert and erase methods would probably be a good fit depending on what you are going to be doing most often with them.

You can use std::sort (the 3 parameter version) to specify your own sorting methods, however re-sorting a group of objects can get pretty expensive depending on which container type you're using. Keep in mind you should keep your comparison methods pretty simple as std::sort is O(n log n).

If you're rarely adding/removing relative to the number of times you're reading through and resorting you may want to consider keeping the data in a container and keeping containers of each way you want them sorted as references to the real data... there are very many options depending on your expected use.

hh10k beat me to the std::sort mention, but you should still really examine what you're mostly going to be doing with this container of data and do some performance tests with different container types and different sorting methods.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!