12

最小限の実例。

#include <cassert>
#include <list>
#include <queue>
//#define USE_PQ

struct MyClass
{
    const char* str;
    MyClass(const char* _str) : str(_str) {}
    MyClass(MyClass&& src) { str = src.str; src.str = nullptr; }
    MyClass(const MyClass&) = delete;
};

struct cmp_func
{
    bool operator() (const MyClass&, const MyClass&) const
    {
        return true;
    }
};

typedef std::priority_queue<MyClass, std::vector<MyClass>, cmp_func> pq_type;

#ifdef USE_PQ
MyClass remove_front(pq_type& l)
{
    MyClass moved = std::move(l.top());
    // error from the above line:
    // use of deleted function ‘MyClass::MyClass(const MyClass&)’
    l.pop();
    return std::move(moved);
}
#else
MyClass remove_front(std::list<MyClass>& l)
{
    MyClass moved = std::move(l.front());
    l.erase(l.begin());
    return std::move(moved);
}
#endif

int main()
{
    const char* hello_str = "Hello World!";
    MyClass first(hello_str);
#ifdef USE_PQ
    pq_type l;
    l.push(std::move(first));
    MyClass moved = remove_front(l);
#else
    std::list<MyClass> l;
    l.push_back(std::move(first));
    MyClass moved = remove_front(l);
#endif
    assert(moved.str);
    assert(!first.str);
    return 0;
}

したがって、これは機能します。ここで、4 行目からコメント記号を削除すると、コピー コンストラクターが必要であることが示されます (私の場合は削除されます)。また、それは逃しoperator=ます。質問:

  • ここでの違いは何ですか？
  • 問題は解決できますか? はいの場合はどのように、いいえの場合はなぜですか?

注：回答にboostのpriority_queueを使用することもできますが、同じエラーが発生しました。

4

6 に答える 6

20

の設計上の見落としのようですstd::priority_queue<T>。要素をそこから直接移動する (コピーしない) 方法はないようです。問題は、 が をtop()返すためconst T&、 にバインドできないことT&&です。そしてをpop()返すvoidので、そこから抜け出すこともできません。

ただし、回避策があります。プライオリティ キュー内のオブジェクトが実際には存在しないことが保証されていますconst。それらは通常のオブジェクトであり、キューはそれらへの変更可能なアクセスを提供しません。したがって、これを行うことは完全に合法です。

MyClass moved = std::move(const_cast<MyClass&>(l.top()));
l.pop();

@DyP がコメントで指摘したように、移動元のオブジェクトがまだキューのコンパレータに渡される可能性があることを確認する必要があります。そして、キューの前提条件を維持するためには、以前と同じように比較する必要があると思います (これを達成するのはほぼ不可能です)。

cast & top()したがって、関数内の呼び出しと呼び出しをカプセル化しpop()、その間にキューが変更されないようにする必要があります。これを行うと、移動元のオブジェクトでコンパレータが呼び出されないことを合理的に確信できます。

そしてもちろん、そのような関数は非常によく文書化されている必要があります。

クラスにカスタムのコピー/移動コンストラクターを提供する場合は常に、対応するコピー/移動代入演算子も提供する必要があることに注意してください (そうしないと、クラスの動作に一貫性がなくなる可能性があります)。したがって、クラスに削除されたコピー代入演算子と適切な移動代入演算子を与えるだけです。

(注: はい、move-constructible が必要で、move-assignable ではないクラスが必要な場合がありますが、それらは非常にまれです (そして、それらを見つけた場合は、それらを知ることができます)。経験則として、常に、 ctor と割り当て操作を同時に提供します)

于 2013-11-22T16:28:12.363 に答える
7

プライオリティ キューに格納するタイプに応じて、Angew のソリューションに代わる方法const_castとして、次のように要素タイプをラップすることで、自分自身を撃つ機会を回避し、取り除くことができます。

struct Item {
    mutable MyClass element;
    int priority; // Could be any less-than-comparable type.

    // Must not touch "element".
    bool operator<(const Item& i) const { return priority < i.priority; }
};

要素をキューから移動すると、次のようになります。

MyClass moved = std::move(l.top().element);
l.pop();

そうすれば、無効化されたオブジェクトの順序関係を保持するための移動セマンティクスに関する特別な要件はなくMyClass、優先キューの不変条件が無効化されるコードのセクションはありません。

于 2016-07-06T10:54:51.817 に答える
6

std::priority_queue基になるコンテナーを保護されたメンバーとして公開するため、拡張は簡単です。

template <
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>>
class extended_priority_queue : public std::priority_queue<T, Container, Compare> {
public:
  T top_and_pop() {
    std::pop_heap(c.begin(), c.end(), comp);
    T value = std::move(c.back());
    c.pop_back();
    return value;
  }
  
protected:
  using std::priority_queue<T, Container, Compare>::c;
  using std::priority_queue<T, Container, Compare>::comp;
};

インスタンスの外に要素を移動する必要がある場合は、ヘルパー関数を実装するためにstd::priority_queue使用できます。extended_priority_queue

template<typename PriorityQueue>
auto priority_queue_top_and_pop(PriorityQueue& queue) ->
    typename PriorityQueue::value_type {
  return static_cast<extended_priority_queue<
      typename PriorityQueue::value_type,
      typename PriorityQueue::container_type,
      typename PriorityQueue::value_compare>&>(queue).top_and_pop();
}

アップデート。@FrançoisAndrieux が指摘したように、実際のコードでは次のことをおpriority_queue_top_and_pop勧めします。不要な暗黙の変換を避けるために、非公開で継承extended_priority_queueします。std::priority_queue

于 2018-07-16T19:23:01.433 に答える
5

非 (const-ref) top() がないのには、非常に正当な理由がある可能性があります。オブジェクトを変更すると、priority_queue の不変条件が壊れます。したがって、その const_cast トリックは、直後にポップした場合にのみ機能する可能性があります。

于 2014-03-29T23:59:09.817 に答える
1

ここでの違いは何ですか？

MyClass remove_front(pq_type& l)
{
    MyClass moved = std::move(l.top()); // PROBLEM
    l.pop();
    return std::move(moved);
}

std::priority_queue::topを返すconst value_type&ので、呼び出すことはできませんstd::move(これは を受け取りますT&&)。

MyClass remove_front(std::list<MyClass>& l)
{
    MyClass moved = std::move(l.front());
    l.erase(l.begin());
    return std::move(moved);
}

std::list::frontには参照を返すオーバーロードがあるため、 にバインドする方法がありT&&ます。

const 以外のオーバーロードがない理由がわかりtopません (標準の見落としの可能性がありますか?)。を使用const_castしてそれを回避できますが、何をしているのか、その理由を説明する詳細なコメントを必ず書いてください。

于 2013-11-22T16:34:05.800 に答える
0

上位の回答は良さそうですが、残念ながら と互換性がありません-D_GLIBCXX_DEBUG。例：

#include <iostream>
#include <memory>
#include <queue>
#include <vector>

struct T {
  int x;
  std::shared_ptr<int> ptr;
  T(int x, std::shared_ptr<int> ptr) : x(x), ptr(ptr) {}
};
struct Compare {
  bool operator()(const T& x, const T& y) {
    return *x.ptr < *y.ptr;
  }
};
int main() {
  auto ptr1 = std::make_shared<int>(3);
  auto ptr2 = std::make_shared<int>(3);
  std::priority_queue<T, std::vector<T>, Compare> f;
  f.emplace(3, ptr1);
  f.emplace(4, ptr2);
  T moved = std::move(const_cast<T&>(f.top()));
  f.pop();
  std::cerr << moved.x << "\n";
}

これをg++ foo.cpp -D_GLIBCXX_DEBUG -O0 -g -std=c++11 && ./a.outGCC で実行すると (clang ではありません。その場合、マクロは何もしません)、コンパレーターで null ポインターの逆参照をトリガーします。

于 2018-02-08T16:27:02.857 に答える