对包含结构的双端队列进行排序

Question

我想根据节点结构中包含的 int g 值对双端队列进行排序。我的程序结构是这样的：

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

当 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 2

在您的代码中，当 j 迭代到 size - 1 时，您超出了范围，这导致 j+1 等于 size，这超出了范围。

您可以使用 std::sort，这是一个内置的 C++ 函数。

语法为 std::sort(t.begin(), t.end())，其中 t 是您要排序的对象。

由于您使用的是结构，因此您必须定义一个顺序，即如何计算小于和等于。您可以重载内置运算符，或定义一个新函数并将其作为第三个参数传递给 sort 函数。

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;

对包含结构的双端队列进行排序

Sort a deque containing struct

c++

deque