c++ - 插入已排序的 vector>> 时避免堆分配

Question

我有一些数据存储在: std::vector<std::unique_ptr<std::pair<Key, Data>>>其中 Data是一些大尺寸的物体，Key唯一标识 Data .我们可以假设 Key 上没有重复项并且此 vector 根据 Key 升序排序.

我已经实现了insert按照以下方式(按照标准容器)

bool compare(const std::unique_ptr<std::pair<Key,Data>>& elem,
             const std::unique_ptr<std::pair<Key,Data>>& input)
{
  return elem->first < input->first;
}

typedef std::vector<std::unique_ptr<std::pair<Key, Data>>> DataStore;

std::pair<DataStore::iterator, bool>
insert(DataStore& vec, const Key& k, const Data& d)
{
  using namespace std::placeholders; // for using bind

  // vvv-- This heap allocation seems unnecessary when element already exists.
  // seems mainly needed for lower_bound to work
  std::unique_ptr<std::pair<Key,Data>> valPtr(new std::pair<Key,Data>(k,d));

  auto location = std::lower_bound(std::begin(vec),
                                   std::end(vec), valPtr,
                                   std::bind(&compare, _1, _2));
  // exists, return element location 
  if(location != vec.end() && (*location)->first == k) {
    return std::make_pair(location, false);
  }

  // non-existing element, add it to the right location
  auto addedLocation = vec.emplace(location, std::move(valPtr));
  return std::make_pair(addedLocation, true);
}

有人可以建议避免在 insert 中分配的方法吗？在上面的评论位置？

我不想自己编写 lower_bound/binary_search 的实现。

Answer 1

std::lower_bound不需要我们正在搜索的对象的类型 T 和元素类型之间有任何关系，除了我们必须能够将它们与 cmp 进行比较这一事实(元素，值)¹。我们可以利用这个事实:

std::pair<DataStore::iterator, bool>
insert(DataStore& vec, const Key& k, const Data& d)
{
  // Note: since you are using C++11, you can use lambdas rather than `std::bind`.
  // This simplifies your code and makes it easier for the compiler to optimize
  auto location = std::lower_bound(std::begin(vec), std::end(vec), k,
    [](const std::unique_ptr<std::pair<Key,Data>>& elem, const Key& key) {
      return elem->first < key;
    });

  // exists, return element location 
  if(location != vec.end() && (*location)->first == k) {
    return std::make_pair(location, false);
  }

  // non-existing element, add it to the right location
  auto addedLocation = vec.emplace(location, new std::pair<Key,Data>(k,d));
  return std::make_pair(addedLocation, true);
}

^{1:很多标准算法都这样做。它们被设计为尽可能通用，因此它们对传入的类型的要求尽可能少。}