当元素类型为 std::pair<int, const std::string &> 时，无法将元素推入优先级队列

Question

我想按索引对一些字符串进行排序。而且我不想使用两种不同类型的优先级队列。

#include <string>
#include <queue>
#include <utility>

int main() {
    const std::string &a = "hello";
    std::pair<int, const std::string &> p = std::make_pair(1, a);
    
    std::priority_queue<std::pair<int, const std::string &>> pq;
    
    pq.push(p);
    
    return 0;
}

那么如何让它发挥作用呢？不能用clang或gcc编译。

clang++ -o /cplayground/cplayground /cplayground/code.cpp
-I/cplayground/include -L/cplayground/lib -std=c++14 -O0 -Wall -no-pie -lm -pthread In file included from /cplayground/code.cpp:5: In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/queue:62: /usr/bin/../lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/stl_heap.h:141:29: error: object of type 'std::pair<int, const std::__cxx11::basic_string<char> &>' cannot be assigned because its copy assignment operator is implicitly deleted
          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
                                   ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/stl_heap.h:215:12: note: in instantiation of function template specialization 'std::__push_heap<__gnu_cxx::__normal_iterator<std::pair<int, const std::__cxx11::basic_string<char> &> *, std::vector<std::pair<int, const std::__cxx11::basic_string<char> &>, std::allocator<std::pair<int, const std::__cxx11::basic_string<char> &> > > >, long, std::pair<int, const std::__cxx11::basic_string<char> &>, __gnu_cxx::__ops::_Iter_comp_val<std::less<std::pair<int, const std::__cxx11::basic_string<char> &> > > >' requested here
      std::__push_heap(__first, _DistanceType((__last - __first) - 1),
           ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/stl_queue.h:643:7: note: in instantiation of function template specialization 'std::push_heap<__gnu_cxx::__normal_iterator<std::pair<int, const std::__cxx11::basic_string<char> &> *, std::vector<std::pair<int, const std::__cxx11::basic_string<char> &>, std::allocator<std::pair<int, const std::__cxx11::basic_string<char> &> > > >, std::less<std::pair<int, const std::__cxx11::basic_string<char> &> > >' requested here
        std::push_heap(c.begin(), c.end(), comp);
             ^ /cplayground/code.cpp:14:8: note: in instantiation of member function 'std::priority_queue<std::pair<int, const std::__cxx11::basic_string<char> &>, std::vector<std::pair<int, const std::__cxx11::basic_string<char> &>, std::allocator<std::pair<int, const std::__cxx11::basic_string<char> &> > >, std::less<std::pair<int, const std::__cxx11::basic_string<char> &> >
>::push' requested here
    pq.push(p);
       ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/stl_pair.h:315:17: note: copy assignment operator is implicitly deleted because 'pair<int, const std::__cxx11::basic_string<char> &>' has a user-declared move constructor
      constexpr pair(pair&&) = default;         ///< Move constructor
                ^ In file included from /cplayground/code.cpp:5: In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/queue:62: /usr/bin/../lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/stl_heap.h:145:32: error: object of type 'std::pair<int, const std::__cxx11::basic_string<char> &>' cannot be assigned because its copy assignment operator is implicitly deleted
      *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
                               ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/stl_pair.h:315:17: note: copy assignment operator is implicitly deleted because 'pair<int, const std::__cxx11::basic_string<char> &>' has a user-declared move constructor
      constexpr pair(pair&&) = default;         ///< Move constructor
                ^ 2 errors generated.

Answer 1

您需要自定义比较器才能使 priority_queue 正常工作。

基本上priority_queue意味着如果一个新项目具有更高的优先级或价值，它的位置将被放在队列的顶部。因此，您用于 priority_queue 的类型必须具有可比性。对于大多数内置类型都是如此，但对于像 pair 这样的类型，您必须自己提供比较。

类似于：

auto compare = [](pair<int, const std::string &> a, pair<int, const std::string &> b) { // comparison between two pairs... return  }

std::priority_queue<std::pair<int, const std::string &>, decltype(compare)>> pq(compare);

Answer 2

这个

const std::string& a = "hello";
std::pair<int, const std::string&> p = std::make_pair(1, a);

这会导致悬空引用，因为make_pair返回的类型是pair<int, string>，但是你使用pair<int, const string&>接收它，使得const string&绑定新创建的pair<int, string>中的string，在make_pair结束后销毁

另外，因为你的pair包含一个reference类型，pair的复制赋值运算符被隐式删除，pq.push(p)会调用这个删除的算子复制一个pair，这是禁止的

您可以使用 std::reference_wrapper 来包装 const string&:

#include <string>
#include <queue>
#include <utility>

using ref_pair = std::pair<int, std::reference_wrapper<const std::string>>;

int main() {
  const std::string& a = "hello";
  ref_pair p = {1, a};
  auto cmp = [](ref_pair x, ref_pair y) {
    return x.first == y.first ? x.second.get() < y.second.get()
                              : x.first < y.first;
  };
  std::priority_queue<ref_pair, std::vector<ref_pair>, decltype(cmp)> pq(cmp);
  pq.push(p);
}

Demo.

当元素类型为 std::pair<int, const std::string &> 时，无法将元素推入优先级队列

Can't push element into priority queue, when element type is std::pair<int, const std::string &>

c++

std-pair