An effecient datastructure to hold structure variable with sorting capability

Question

Hi ppl,

I have a structure

struct dbdetails
{
    int id;
    string val;
};

I need a data structure in C++ that can hold structure variable with a sort capability. Is it possible? im a newbie. Sorry If this questions is wrong. I was looking at vector, which can hold structure variable, but I will not be able to sort it based on id , coz it is a structure member. Any suggestions? Thanks in advance !!

Answer 1

You can sort a vector based on struct members. You just need a custom comparator.

Answer 2

You can have a vector of struct's and then sort them as:

std::sort(vectStruct.begin(), vectStruct.end(), &vectStructSort);

bool vectStructSort(Try const& lhs, Try const& rhs) { // try is keyword.
    return lhs.id < rhs.id;
}

Answer 3

You need a custom functor for comparing your tries. This should do the trick:

#include <algorithm>
#include <vector>
// try is a keyword. renamed
struct sorthelper : public std::binary_function<try_, try_, bool>
{
    inline bool operator()(const try_& left, const try_& right)
    {   return left.id < right.id;  }
};

...
std::vector<try_> v;
// fill vector 
std::sort(v.begin(), v.end(), sorthelper());
...

Please feel free to ask if you have any follow-up questions. Do you possess the Stroustrup book?

Edit: Suggestion of Matteo:

struct try_
{
    int id;
    string val;
    bool operator<(const try_& other) const
        {return id < other.id;}

}; // no s here plz.

...
std::vector<try_> v;
// fill vector 
std::sort(v.begin(), v.end());
...

Answer 4

It depends by what requirements you have on your data container. You may find useful a set (in Stl, Set is a Sorted Associative Container to store objects of type Key). Or even a Hash set, or a sorted array.

If you know that you need your elements to be sorted, it is maybe better to use a sorted container, instead of sorting it each time you need to.

Answer 5

You could use a std::map. They are sorted by key, so you could do:

std::map<int, std::string> myStuff;

This is a map with an int as key and std::string as value. When you iterate over the map, you’ll find that it’s automatically sorted by the key.

Note you would no longer need your struct with this solution. If you absolutely need the data in a struct (perhaps to interface with some external library) you could always copy data from the map into a struct as needed.

Answer 6

All ordered containers (std::set, std::map, std::multiset, std::multimap) are, well, ordered. Non ordered containers (std::list, std::vector, std::deque) can be ordered by providing a comparison function an using std::sort (vector, deque) or by providing that comparator to a member method (list).

It all boils down to what you actually need. If you need to keep the elements sorted at all times, then a sorted container might be more efficient than modifying the container and resorting. On the other hand, if having the container sorted at all times is not a requirement, but being able to modify the elements then you might prefer a vector. Sorted containers maintain the keys as constant objects, as modification of the keys would break the sort invariant.

In some cases the container needs to be sorted at all times, but it does not change after some initialization phases. In that case a non-sorted container that gets sorted after initialization can be fine.