c++ - 只保留队列中的唯一元素

Question

我有以下形式的 vector 队列:

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

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

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

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

Answer 1

如果插入顺序很重要，那么我会使用第二种数据结构来跟踪唯一插入的元素，例如 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> ，这归结为在将 vector 插入集合时按字典顺序比较 vector 。