擦除Deque容器的元素

Question

我想擦除deque的元素。當你有一個包含結構的雙端隊列並且你想從後到前打印這些元素，但是你不想打印具有相同結構元素的元素時，你如何做呢？

我有這樣的結構：

struct New_Array {      
    array<array<int,4>,4> mytable;  
    int h; 
}; 

雙端隊列充滿了從前面的過程元素。 您想要打印所有位於雙側的元素，但您打印的每個表格必須具有唯一的「h」。只有您找到的具有特定「h」的第一張表必須打印，其他具有相同「h」的表不應打印。我認爲這也可以用「查找」功能來實現。

我們將從deque後面開始找到的「h」值將爲0，並且它將增加其對deque前面的值。

我已經試過這樣：

void Find_Solution_Path(deque<New_Array> Mydeque) 
{ 
    while(Mydeque.size()>0) 
    { 
     New_Array y=Mydeque.back(); 
     PrintBoard(y);   //this is a function that prints the 4x4 array. 
     Mydeque.pop_back(); 
     for(unsigned int i=0; i<Mydeque.size(); i++) 
     { 
      New_Array xxx=Mydeque[i]; 
      if(xxx.h==y.h) 
      { 
       Mydeque.erase(Mydeque[i]); 
      } 
     } 
    } 
} 

Answer 1

我不會用一個雙端隊列，而是一組。如果你絕對需要這個deque，那麼創建一個集合。用適當的標準<來定義一個<運算符，以反映唯一性。您將每個打印的元素插入到集合中。在打印之前，檢查元素是否已經存在於集合（查找）中。

HTH，馬丁

Answer 2

的一種方法是使用std::unique_copy。

#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <deque> 

struct New_Array { 
    array<array<int,4>,4> mytable; 
    int h; 
    // unique_copy needs this: 
    bool operator==(const New_Array& other) { return h == other.h; } 
}; 

ostream& operator<<(ostream& out, const New_Array& v) 
{ 
    return out << v.h; 
} 

int main() 
{ 
    std::deque<New_Array> q; 
    New_Array temp; 

    // {1, 1, 2, 2, 3, 3} 
    temp.h = 1; 
    q.push_back(temp); 
    q.push_back(temp); 
    temp.h = 2; 
    q.push_back(temp); 
    q.push_back(temp); 
    temp.h = 3; 
    q.push_back(temp); 
    q.push_back(temp); 

    unique_copy(q.begin(), q.end(), ostream_iterator<New_Array>(cout, "\n")); 
} 

範圍必須分類爲unique_copy正常工作。由於我們按順序插入了元素，所以在上面的例子中不需要排序。

Answer 3

我相信@Martin的答案可能是最好的解決方案。如果你不能爲函數返回一個deque更改簽名，你可以從它構建一個set，所有的副本會自動消失：

// First you need to declare a compare function for NewArray objects 
struct NewArrayComp { 
    bool operator()(const NewArray& a1, const NewArray& a2) const { 
     return a1.h < a2.h; 
    } 
}; 

// Then you can construct a set from the deque 
deque<NewArray> dq; 
// ... 
std::set<NewArray, NewArrayComp> s(dq.begin(), dq.end()); 

// Finally you can just print the arrays (without duplicates) 
for (const auto& a : s) 
    PrintBoard(a); 

這個方案有一個爲O（n log n）的複雜性，同時你的代碼是O（n^2）。

此外，如果你不想重複支付從deque要素成本進入set您可以在C++ 11使用移動語義：

std::set<NewArray, NewArrayComp> s; 
std::move(dq.begin(), dq.end(), std::inserter(s, s.begin())); 

這將只是移動的所有元素沒有製作它們的副本。