如何将 unique_ptr 从优先队列转移到队列

Question

在"short"中，我有一个priority_queue选择kunordered_set<int>满足一定的条件。我想 return 它们（哈希集）作为 queue。

由于 priority_queue 的创建和维护需要元素交换，我使用指针而不是 unordered_set<int> 作为 priority_queue.

的入口

因此 return 类型应该是 queue< smart_ptr<unordered_set<int>> >.

如果我使用 shared_ptr 代码工作正常，但我希望使用 unique_ptr 因为它更经济并且客户承诺将其用作 unique_ptr。

如何使用unique_ptr实现下面的代码？

--------------------详细说明------------------------ ------

我有一个函数可以从文件中读取并保留 k 行，这些行的大小最接近参考大小。比如说，如果 k=2，参考大小是 5，并且文件包含 6 行大小（该行中的整数个数）3,5,6,20,2,1。 k-closest 行是大小分别为 5 和 6 的两条行。

我使用大小为 k 的 priority_queue 和自定义比较器来实现目标。我决定 return 包含所选 k-closest 行的 queue，因为客户不想知道比较器是如何实现的（比较器是 priority_queue 的参数模板）。

using ptr_type = shared_ptr<unordered_set<int>>;
// ???????????????????????????????????????
// using ptr_type = unique_ptr<unordered_set<int>>; // unique_ptr does not work
// ???????????????????????????????????????
// Is it possible to transfer unique_ptr entries from a priority_queue to a queue?
using pair_comm_type = pair<int,ptr_type>;

queue<pair_comm_type> f() {
    // myFile.txt is a space separated file of integers.
    // Different lines may have different lengths (number of integers)
  string inputFile = "myFile.txt";
  const int TOP_K_LINE = 3;

    // to open a file
  ifstream fin(inputFile.c_str());
  string readBuffer;
  // The file opened

    // to define a priority_queue
    // define customized compare function, such that retained lines have size
    // closest to the reference value.
  double referenceSize = log10(10.0);
  auto comp = [&referenceSize](const pair_comm_type &LHS, const pair_comm_type &RHS)
      { return abs(log10(LHS.first)-referenceSize) 
      < abs(log10(RHS.first)-referenceSize); };
  priority_queue<pair_comm_type, vector<pair_comm_type>, decltype(comp)> myHeap(comp);
  // the priority_queue defined

  int bufIntValue = -1;
  int curMinArraySize = -1; // auxilliary variable, to reduce heap top access
    // to read the file line by line
  while (getline(fin,readBuffer)) {
      // to read int in each line to a hash set
    istringstream S(readBuffer);
    ptr_type lineBufferPtr(new unordered_set<int>);
    while (S>>bufIntValue) lineBufferPtr->insert(bufIntValue);
// one line read

      // to decide retain or not based on the length of this line
    int arraySize = lineBufferPtr->size();
    if (myHeap.size() < TOP_K_LINE) {
      // We can add new lines as long as top-k is not reached
      myHeap.emplace(arraySize,std::move(lineBufferPtr));
      curMinArraySize = myHeap.top().first;
      continue;
    }
    if (arraySize <= curMinArraySize) continue;
    myHeap.emplace(arraySize,std::move(lineBufferPtr));
    myHeap.pop();
    curMinArraySize = myHeap.top().first;
  }
  // all lines read
  fin.close();

    // to transfer values from the priority_queue to a queue
    // ???????????????????????????????????????
    // Is it possible that we can make changes here such that unique_ptr can also work??????
    // ???????????????????????????????????????
  queue<pair_comm_type> Q;
  while (!myHeap.empty()) {
    auto temp = myHeap.top();
    myHeap.pop();
    Q.emplace(temp.first,std::move(temp.second));
  }

  /*
  while (!Q.empty()) {
    printf("%d, ",Q.front().first);
    Q.pop();
  }
  printf("\n");
  */
  return Q;
}

Answer 1

STL 容器设计为移动，当您这样做时，它与使用指针一样高效。事实上，他们在内部使用 pointers，因此您不必这样做。

我会考虑使用这样的值：

using pair_comm_type = pair<int, unordered_set<int>>;

queue<pair_comm_type> f() {

  string inputFile = "myFile.txt";
  const int TOP_K_LINE = 3;

  ifstream fin(inputFile.c_str());
  string readBuffer;

  double referenceSize = log10(10.0);
  auto comp = [&referenceSize](const pair_comm_type &LHS, const pair_comm_type &RHS)
      { return abs(log10(LHS.first)-referenceSize)
      < abs(log10(RHS.first)-referenceSize); };
  priority_queue<pair_comm_type, vector<pair_comm_type>, decltype(comp)> myHeap(comp);

  int bufIntValue = -1;
  int curMinArraySize = -1;

  while (getline(fin,readBuffer)) {
    istringstream S(readBuffer);

    // no need to use pointers here
    unordered_set<int> lineBufferPtr;
    while (S>>bufIntValue)
        lineBufferPtr.insert(bufIntValue);

    int arraySize = lineBufferPtr.size();
    if (myHeap.size() < TOP_K_LINE) {

      myHeap.emplace(arraySize,std::move(lineBufferPtr));
      curMinArraySize = myHeap.top().first;
      continue;
    }
    if (arraySize <= curMinArraySize) continue;
    myHeap.emplace(arraySize,std::move(lineBufferPtr));
    myHeap.pop();
    curMinArraySize = myHeap.top().first;
  }

  fin.close();

  // Use std::move to transfer the top() element which will be
  // just as efficient as using pointers

  queue<pair_comm_type> Q;

  while (!myHeap.empty()) {
    auto temp = std::move(myHeap.top()); // USE MOVES
    myHeap.pop();
    Q.push(std::move(temp));
  }

  return Q;
}

Answer 2

@Galik 的解决方案有效。

对于原问题，简单的回答是否定的。我们无法从 priority_queue.

中转移出 unique_ptr

copy constructor of unique_ptr, of which the argument is a const reference, is deleted. The return type of priority_queue::top() is a const reference。因此我们不能使用 return 值来创建新的 unique_ptr 对象。

如何将 unique_ptr 从优先队列转移到队列

how to transfer a unique_ptr from a priority queue to a queue

c++

stl

smart-pointers

c++11