CODEWITHSUNDEEP
c++stl
Leslieg
Leslieg

Reputation: 11

STL datastructure with sorting

I need a data structure that could automatically sorted based on a struct.

struct{
  int key;
  int comparisonValue(size of the vector);
}

I need it in the following form:

datastructure<struct, vector<int>>

Where the data structure is automatically sorted based on the comparisonValue and based on the minimum value of the comparison value, I would like to get the vector and add some data to it.

What data structure could I use? Could I use map and is there a custom sorter for map?

What could I do if I need to modify the key, in this case the comparisonValue and still keep the order sorted?

Thanks

Upvotes: 1

Views: 1619

Answers (2)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272457

std::map from the STL.

By default, this sorts key values by comparing them using std::less<Key>, which by default calls operator< on the key values. Therefore, you can define an overload of operator< for your struct type::

bool operator<(const Key &a, const Key &b)
{
    return (a.someField < b.someField);
}

Upvotes: 10

J&#248;rgen Fogh
J&#248;rgen Fogh

Reputation: 7646

"... and based on the minimum value of the comparison value, I would like to get the vector and add some data to it"

If what you mean is that you would like to get the smallest element in the entire collection, you might be better off with a std::priority_queue, assuming that you only ever update the smallest element.

Otherwise std::map is probably what you need, as Oli Charlesworth's suggests. You should probably take a look at map's lower_bound() and upper_bound() methods.

You should also be aware that STL containers keep copies of the objects, so if you want your changes to be reflected elsewhere, you need to store pointers to the objects instead. Then you would use a separate Functor to compare the pointers according to what they point to.

Upvotes: 1

Related Questions