Сортировка deque, содержащего структуру

Question

Я хочу сортировать deque в соответствии со значением int g, содержащимся в struct node. Структура моей программы заключается в следующем:

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

deque<node> open; 

Это функция сортировки Я пытаюсь, но это дает значения мусора. Пожалуйста, наставит меня:

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

В коде, вы выходите за пределы, когда j итерацию Шифрование до size - 1, что приводит к j+1 равен size, который находится вне границ.

Вы можете использовать std::sort, который является встроенной функцией C++.

Синтаксис std::sort(t.begin(), t.end()) где t - объект, который вы хотите отсортировать.

Поскольку вы используете структуру, вам нужно будет определить порядок, т. Е. Как меньше и равно рассчитанному. Вы можете либо перегрузить встроенные операторы, либо определить новую функцию и передать это в качестве третьего параметра функции sort.

Answer 2

Вы выходите за пределы, когда i == 0: вы итерацию j до size - 1 включительно, а затем j + 1 == size.

Во всяком случае, есть намного проще и быстрее, решение - использовать только std::sort:

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

Answer 3

Вы можете использовать std::sort:

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

Я обычно говорю: если вы хотите, отсортированные контейнеры, вероятно, нужно, чтобы получить узлы по данному g. Используйте std::multimap вместо std::deque, который позволит отобразить g значения узлов:

std::multimap<int, node> nodes;