Error while trying to sort std::map

Question

I am trying to order a std::map, this map has an int as key and a class as a second element. This is the code:

#include <vector>
#include <algorithm>
#include <map>


class Position {


public:
    bool operator < (const Position & pos) {
        return x < pos.x;
    }
    bool operator > (const Position & pos) {
        return x > pos.x;
    }
    int x;
    int y;
};

class Element {
public:
    bool operator < (const Element & pos) {
        return position.x < pos.position.x;
    }
    bool operator > (const Element & pos) {
        return position.x > pos.position.x;
    }
    int order;
    Position position;
};

bool IsGreater(const std::pair<int, Element>& e1,const std::pair<int, Element>& e2) {
    return e1.second.position.x > e2.second.position.x;
}

using namespace std;

int main()
{
    std::map<int,Element> elements;
    Element e1;
    Element e2;
    Element e3;
    e1.position.x = 2;
    e2.position.x = 1;
    e3.position.x = 0;
    elements.insert(std::pair<int, Element>(2, e1));
    elements.insert(std::pair<int, Element>(1, e2));
    elements.insert(std::pair<int, Element>(0, e3));

    std::sort(elements.begin(), elements.end(), IsGreater);

    for (unsigned int x = 0; x < elements.size(); x++) {
        printf("Element %d order: %d\n", x, elements.at(x).order);
    }

    return 0;
}

Basically I have 2 class which are Position (contains an x and a y coordinate) and an Element (conains the index and the position). I need to order this map by the x coordinate in the position, but when I try to compile the code I have this 3 Issues:

Error   C2676   binary '-': 'const std::_Tree_unchecked_iterator<std::_Tree_val<std::_Tree_simple_types<std::pair<const int,Element>>>>' does not define this operator or a conversion to a type acceptable to the predefined operator  TestSort    C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.25.28610\include\algorithm   3506    
Error   C2672   '_Sort_unchecked': no matching overloaded function found    TestSort    C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.25.28610\include\algorithm   3506    
Error   C2780   'void std::_Sort_unchecked(_RanIt,_RanIt,iterator_traits<_Iter>::difference_type,_Pr)': expects 4 arguments - 3 provided    TestSort    C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.25.28610\include\algorithm   3506

Initially I've tried to call std::sort with elements.begin() and elements.end(), no use, then I tried to include the operator oveload "<" and ">" on the element class... no luck, then I've tried to add the operator overload "<" and ">"... but again no luck! I've tried to use a lambda expression as third agrument of the sort method, nothing... and at the end I've tried to create a separate function for the sorting which returns a bool... but nothing worked. I simply cannot understand the problem and I cannot work out what's wrong. My question are: 1) What this error is telling me? 2) How can I solve it? Thanks in advance for any help!

Something like an unsorted map does not exist, so you can't and don't need to sort it in the first place. (and the sorting is done by the keys, irrelavant of their values) — Lukas-T, May 12 '20 at 08:33
in principle you can, but it wont have any observable effect. — 463035818_is_not_an_ai, May 12 '20 at 08:36
`std::map` is already sorted by design: ["`std::map` is a sorted associative container that contains key-value pairs with unique keys"](https://en.cppreference.com/w/cpp/container/map). — Evg, May 12 '20 at 08:37
But when I try to do it with an it can be done and I see that in fact is reordered, shouldn't this be a problem in the class or in the implementation? — shadow1390, May 12 '20 at 08:38
@Evg so basically I can sort by the key and not the Element? Or I should use less inside the declaration of the element? — shadow1390, May 12 '20 at 08:41
`std::map` is sorted by keys. If you want to sort it by values, you need another container (like `std::vector`), you can't (re)sort `std::map` itself. This question may be helpful: [Sorting std::map using value](https://stackoverflow.com/questions/5056645/sorting-stdmap-using-value). — Evg, May 12 '20 at 08:43

score 2 · Answer 1 · answered May 12 '20 at 09:07

2

You cannot use std::sort on a std::map because

std::sort required random access iterators but std::map<Key, T>::iterator is only a bidirectional iterator.
std::map<Key, T>::value_type is std::pair<const Key, T>, so you cannot change the Key of a value, as would be required in std::sort. The reason for this is precisely because std::map is by design sorted, so you should not manually try to 're-sort` the values; doing so would essentially break the container leading to undefined behaviour.

If you want to sort the values in map by some other condition, you should either re-evaluate whether a std::map is really what you want; maybe a std::vector<std::pair<Key, T>> would be better, or you'll have to copy values or take references into some other container (i.e. a std::vector) and sort that instead.

answered May 12 '20 at 09:07

Daniel

8,179
6
31
56

The things that scares me it the word "copy" because I wanna have a low memory footprint becuase there il be lots and lots of elements inside it, Can I, maybe, use the map to store the element and the vector with pair with a pointer to the element? What i menai is std::map std::vector> – shadow1390 May 12 '20 at 09:50
You can do that if you want (although you're not going to save a great deal of memory). Why do you think that you need a `std::map`? if you're really that concerned about memory then `std::map` is almost certainly not the way to go - it rarely is. – Daniel May 12 '20 at 09:55
I was using it assuming i would use the key in a different way, like a guid or a string – shadow1390 May 12 '20 at 09:59

Error while trying to sort std::map

1 Answers1