對包含struct的雙端隊列排序

我想根據節點struct中包含的整型值對一個雙端隊列進行排序。我的程序的結構是這樣的：對包含struct的雙端隊列排序

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; 
}

來源

2015-06-26 Mohsin Anees

是否有您不使用'的std :: sort'理由嗎？ – TartanLlama

請指導我如何在這種情況下使用此功能。我不知道這個功能。 –

我想按照g的降序對deque進行排序。 –

在你的代碼，你去出界時j迭代高達size - 1，這將導致在j+1等於size這是出的界限。

您可以使用std::sort這是一個內置的C++函數。

語法是std::sort(t.begin(), t.end())其中t是要排序的對象。

由於您正在使用一個結構，您將不得不定義一個排序，即如何小於等於計算。您可以重載內置運算符，也可以定義一個新函數並將其作爲第三個參數傳遞給sort函數。

來源

2015-06-26 09:23:11 therainmaker

你要出界的時候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; 
});

來源

2015-06-26 09:22:28

您可以使用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;

來源

2015-06-26 09:25:31

爲什麼你認爲OP需要'multimap'？請注意'deque'被選中，這很可能意味着經常在開始/結束時添加/刪除。排序可能需要添加/刪除最小/最大值。儘管在這種情況下heap是更直觀的選擇，但deque可以提供一些好處（至少heap是不太知名的容器） –

@AndyT：我原則上同意，但添加到multimap中並不一定很昂貴，它實際上取決於應用。但是，當你需要比插入提取值並對其進行排序更頻繁的時候，使用排序後的容器顯然會給你帶來好處，因爲通常情況下，這種類型的複雜性與最壞情況下的插入相當。 –

對包含struct的雙端隊列排序

回答

相關問題