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

我不会使用双端队列而是一组。如果您绝对需要双端队列，请创建一个集合。使用反映唯一性的适当标准 < 定义 < 运算符。您将每个打印的元素插入到集合中。在打印之前检查元素是否已经存在于集合中（查找）。

HTH，马丁

于 2012-06-17T11:35:26.960 回答
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可以从中构造 a 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 回答