Sort a deque containing struct

Question

I want to sort a deque according to the int g value contained in the node struct. The structure of my program is this:

struct node
{
    int x;
    int y;
    int g;  
};

deque<node> open;

This is the sorting function I am trying but it gives garbage values. Please guide me:

deque<node> sort(deque<node> t)
{
    deque<node>::iterator it;
    int size= t.size();
    node te;
    for(int i=0; i<size; i++)
    {
        for(int j=0; j<size-i; j++)
        {
            if(t[j].g < t[j+1].g)
            {
                te.x = t[j].x;
                te.y = t[j].y;
                te.g = t[j].g;

                t[j].x = t[j+1].x;
                t[j].y = t[j+1].y;
                t[j].g = t[j+1].g;

                t[j+1].x = te.x;
                t[j+1].y = te.y;
                t[j+1].g = te.g;
            }
        }
    }

    for(it=t.begin();it!=t.end();it++)
    {   
        te = *it;
        cout<<te.x<<","<<te.y<<","<<te.g<<endl;
    }

    return t;
}

Answer 1

In your code, you go out of bounds when j iterates upto size - 1, which results in j+1 being equal to size which is out of bounds.

You can use std::sort which is an inbuilt C++ function.

The syntax is std::sort(t.begin(), t.end()) where t is the object you want to sort.

Since you are using a struct, you will have to define an ordering, i.e. how is less than and equal to calculated. You can either overload the inbuilt operators, or define a new function and pass that as a third parameter to the sort function.

Answer 2

You are going out of bounds when i == 0: you iterate j up to size - 1 inclusively, but then j + 1 == size.

Anyway, there's much simpler and faster solution - just use std::sort:

std::sort(t.begin(), t.end(), [](const node& a, const node& b) { 
    return a.g > b.g;
});

Answer 3

You can use std::sort:

struct {
    bool operator()(node a, node b)
    {   
        return a.g < b.g;
    }   
} customLess;
std::sort(s.begin(), s.end(), customLess);

I'd generally say: if you want sorted containers, you probably need to get nodes by a given g. Use a std::multimap instead of std::deque, which will allow you to map g values to nodes:

std::multimap<int, node> nodes;