Can't push element into priority queue, when element type is std::pair<int, const std::strin-CodePudding

I want to order some strings by their indexes. And I don't want to use two different types of priority queue.

#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;
}

So how to let it work? Can't be compiled by clang or 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.

CodePudding user response：

This

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

This will result in a dangling reference, because the type returned by make_pair is pair<int, string>, but you use pair<int, const string&> to receive it, which makes const string& bind the string in the newly created pair<int, string>, and it will be destroyed after make_pair ends.

In addition, because your pair contains a reference type, the copy assignment operator of the pair is implicitly deleted, and pq.push(p) will call this deleted operator to copy a pair, which is forbidden.

You can use std::reference_wrapper to wrap the 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.

CodePudding user response：

You need a custom comparator for priority_queue to work.

Basically priority_queue means that the position of a new item would be put on the top of the queue if it has higher priority or value. So the type you use for priority_queue has to be comparable. This is true for most built-in types, but for a type like pair you must provide the comparison yourself.

Something like:

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