0

両端キューの要素を消去したい。構造体を含む両端キューがあり、要素を後ろから前に出力したいが、同じ構造体要素を持つ要素を出力したくない場合、どうすればよいでしょうか?

私はこのような構造体を持っています:

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

両端キューは、前の手順の要素で満たされています。 両端キューにあるすべての要素を出力したいが、出力する各テーブルには一意の "h" が必要です。特定の「h」を持つ最初のテーブルのみを印刷する必要があり、同じ「h」を持つ他のテーブルは印刷しないでください。これは「検索」機能でも実装できると思います。

両端キューの後ろから始まる "h" の値は 0 になり、両端キューの前に向かって値が増加します。

私はこれを試しました：

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]);
            }
        }
    }
}
4

3 に答える 3

2

dequeではなくセットを使用します。どうしても両端キューが必要な場合は、それでもセットを作成します。一意性を反映する適切な基準<を使用して<演算子を定義します。印刷された各要素をセットに挿入します。印刷する前に、要素がセットにすでに存在するかどうかを確認します（検索）。

HTH、マーティン

于 2012-06-17T11:35:26.960 に答える
1

1つの方法は、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上記の場合、要素を順番に挿入したため、並べ替えは必要ありません。

于 2012-06-17T11:37:57.207 に答える
0

@Martinの回答がおそらく最良の解決策だと思います。を返す関数のシグネチャを変更できない場合は、それからaを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()));

これにより、コピーを作成せずにすべての要素が移動します。

于 2012-06-17T12:44:58.783 に答える