c++ - C ++の一意のエントリを持つキュー

Question

C または C++ で一意のエントリ (重複なし) を含むキューを実装する必要があります。キューで既に使用可能な要素の参照を維持することを考えていますが、それは非常に非効率的です。

これに対処するための提案を教えてください。

Answer 1

一意性を追跡するための補助データ構造はどうですか。

std::queue<Foo> q;
std::set<std::reference_wrapper<Foo>> s;

// to add:

void add(Foo const & x)
{
    if (s.find(x) == s.end())
    {
        q.push_back(x);
        s.insert(std::ref(q.back()));  // or "s.emplace(q.back());"
    }
}

または、代わりに、キューとセットの役割を逆にします。

std::set<Foo> s;
std::queue<std::reference_wrapper<Foo>> q;

void add(Foo const & x)
{
    auto p = s.insert(x);       // std::pair<std::set<Foo>::iterator, bool>
    if (s.second)
    {
        q.push_back(std::ref(*s.first));  // or "q.emplace_back(*s.first);"
    }
}

Answer 2

待ち行列:

• std::set を使用して一意の要素のセットを維持します
• std::set に追加できた要素を std::queue に追加します

デキュー:

• std::queue および std::set から要素を削除します

Answer 3

std::queueはコンテナアダプタであり、基になるの比較的少数のメンバーを使用しContainerます。のとの両方unordered_mapを含むカスタムコンテナを簡単に実装できます。少なくともメンバーとが必要です。コンテナが呼び出されたときにその内部を確認し、それに応じて拒否します（おそらくスローします）。完全な例を示すには：reference_wrapper<T>deque<T>frontpush_backhash_mappush_back

#include <iostream>
#include <set>
#include <deque>
#include <queue>
#include <unordered_set>
#include <functional>

namespace std {

// partial specialization for reference_wrapper
// is this really necessary?
template<typename T>
class hash<std::reference_wrapper<T>> {
public:
  std::size_t operator()(std::reference_wrapper<T> x) const 
  { return std::hash<T>()(x.get()); }
};

}

template <typename T>
class my_container {
  // important: this really needs to be a deque and only front
  // insertion/deletion is allowed to not get dangling references
  typedef std::deque<T> storage;
  typedef std::reference_wrapper<const T> c_ref_w;
  typedef std::reference_wrapper<T> ref_w;
public:  
  typedef typename storage::value_type value_type;
  typedef typename storage::reference reference; 
  typedef typename storage::const_reference const_reference; 
  typedef typename storage::size_type size_type;

  // no move semantics
  void push_back(const T& t) {
    auto it = lookup_.find(std::cref(t));
    if(it != end(lookup_)) {
      // is already inserted report error
      return;
    }
    store_.push_back(t);
    // this is important to not have dangling references
    lookup_.insert(store_.back());
  }

  // trivial functions

  bool empty() const { return store_.empty(); }
  const T& front() const { return store_.front(); }
  T& front() { return store_.front(); }

  void pop_front() { lookup_.erase(store_.front()); store_.pop_front();  }
private:
  // look-up mechanism
  std::unordered_set<c_ref_w> lookup_;
  // underlying storage
  storage store_;
};

int main()
{
  // reference wrapper for int ends up being silly 
  // but good for larger objects
  std::queue<int, my_container<int>> q;
  q.push(2);
  q.push(3);
  q.push(2);
  q.push(4);
  while(!q.empty()) {
    std::cout << q.front() << std::endl;
    q.pop();
  }

  return 0;
}

編集：my_containerあなたはコンテナの適切なモデル（おそらくアロケータも）を作りたいと思うでしょうが、これは別の完全な質問です。バグを指摘してくれたChristianRauに感謝します。