我有一些数据存储在:
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 的实现。
最佳答案
std::lower_bound
不需要我们正在搜索的对象的类型 T
和元素类型之间有任何关系,除了我们必须能够将它们与 cmp 进行比较这一事实(元素,值)
1。我们可以利用这个事实:
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:很多标准算法都这样做。它们被设计为尽可能通用,因此它们对传入的类型的要求尽可能少。
关于c++ - 插入已排序的 vector<unique_ptr<pair<>>> 时避免堆分配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49828466/