只保留队列中的唯一元素

Question

我有以下形式的向量队列：

queue<vector<unsigned> > a;
vector<unsigned> b;
b.push_back(10); b.push_back(12); b.push_back(15);
a.push(b);
vector<unsigned> b2;
b1.push_back(15); b1.push_back(19); b1.push_back(18);
vector<unsigned> b1;
b1.push_back(10); b1.push_back(12); b1.push_back(15);

我只想在队列中输入唯一向量。例如，在上面的示例中，我只想保留矢量元素：(10,12,15),(15,19,18) 即在这里我删除了重复元素：(10,12,15) 并保留了它的只复制一次。

检查向量是否已存在于队列中的一种方法是对其进行迭代。有没有其他方法可以检查向量是否已经存在于队列中或效率不高？

我使用的gcc版本：gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

Answer 1

队列不是可让您通过元素值进行高效搜索的数据结构（它们本质上类似于向量）。集合是，但它们不保证元素的顺序。

使用 std::unique 将尝试针对实际队列组织提供最佳解决方案。

Answer 2

如果插入顺序很重要，那么我会使用第二种数据结构来跟踪唯一插入的元素，例如 std::set.

#include <cassert>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

template <typename T>
class unique_queue {
private:
    std::queue<T> m_queue;
    std::set<T> m_set;
public:
    bool push(const T& t) {
        if (m_set.insert(t).second) {
            m_queue.push(t);
            return true;
        }
        return false;
    }

    void pop() {
        assert(!m_queue.empty());
        const T& val = front();

        typename std::set<T>::iterator it = m_set.find(val);
        assert(it != m_set.end());

        m_set.erase(it);
        m_queue.pop();
    }

    const T& front() const {
        return m_queue.front();
    }
};

int main(int argc, char *argv[]) {
    unique_queue<std::vector<unsigned> > q;

    std::vector<unsigned> b1;
    b1.push_back(10); b1.push_back(12); b1.push_back(15);
    std::cout << "pushed: " << q.push(b1) << std::endl;

    std::vector<unsigned> b2;
    b2.push_back(15); b2.push_back(17); b2.push_back(18);
    std::cout << "pushed: " << q.push(b2) << std::endl;

    std::vector<unsigned> b3;
    b3.push_back(10); b3.push_back(12); b3.push_back(15);
    std::cout << "pushed: " << q.push(b3) << std::endl;

    q.pop();
    q.pop();
    std::cout << "pushed: " << q.push(b3) << std::endl;
}

默认情况下，std::set<T> 将使用 std::less<T> 来比较其元素。对于 std::vector<unsigned>，这归结为在将向量插入集合时按字典顺序比较向量。

Answer 3

如果你有这样的特殊需求，我倾向于不直接使用标准容器。相反，我先定义一个接口：

class my_queue {
public:
    typedef vector<unsigned> element_type;
    void push(element_type const&);
    bool empty() const;
    element_type pop();

然后，由于您希望元素是唯一的，我将使用常规队列和集合：

private:
    queue<element_type> m_queue;
    set<element_type> m_set;
};

我想你明白了，我懒得启动编译器来实际测试它。 ;)

一些进一步的说明：

尽管它更复杂，但矢量只是一种数据类型，因此可以对其进行赋值、复制和比较。这种比较被例如使用。 std::set.
这可以优化，因为两者的数据存储实际上是冗余的。然后我将实际元素存储在集合中，并将它们的顺序存储在队列中（即存储集合迭代器）。
除非您在队列中存储许多元素，否则对队列进行线性搜索（例如使用 std::deque 作为替代）可能是一种性能更好的替代方法。
不清楚插入副本是否会影响顺序。另外，如果元素已经被删除然后又被添加回来怎么办？在任何情况下，编写测试以确保队列具有所需的行为。

只保留队列中的唯一元素

Retaining just unique elements in a queue

c++

vector