Поиск необработанных указателей для наборов unique_ptrs
Мне часто хочется написать такой код:
class MyClass
{
public:
void addObject(std::unique_ptr<Object>&& newObject);
void removeObject(const Object* target);
private:
std::set<std::unique_ptr<Object>> objects;
};
Однако большая часть интерфейса std::set бесполезна с std::unique_ptrs, поскольку функции поиска требуют параметров std:: unique_ptr (которых у меня, очевидно, нет, поскольку они принадлежат самому набору).
Я могу придумать два основных решения этого.
Создайте временный unique_ptr для поиска. Например, вышеупомянутый метод removeObject() может быть реализован следующим образом:
void MyClass::removeObject(const Object* target) { std::unique_ptr<Object> targetSmartPtr(target); objects.erase(targetSmartPtr); targetSmartPtr.release(); }Замените набор картой необработанных указателей на unique_ptrs.
// ... std::map<const Object*, std::unique_ptr<Object>> objects; };
Тем не менее, оба кажутся мне немного глупыми. В решении 1 erase() не исключение, поэтому временный unique_ptr может удалить объект, который ему на самом деле не принадлежит, а 2 требует ненужного удвоения хранилища для контейнера.
Я знаю о контейнерах указателей Boost, но их текущие возможности ограничены по сравнению с современными стандартными контейнерами C++11.
Недавно я читал о C++14 и наткнулся на "Добавление поиска гетерогенного сравнения в ассоциативные контейнеры". Но, исходя из моего понимания, типы поиска должны быть сопоставимы с ключевыми типами, но необработанные указатели не сопоставимы с unique_ptrs.
Кто-нибудь знает более элегантное решение или грядущее дополнение к C++, которое решает эту проблему?
6 ответов
В C++14std::set<Key>::find это template функционировать, если Compare::is_transparent существует. Тип, который вы передаете, не обязательно должен быть Key, просто эквивалент под вашим компаратором.
Итак, напишите компаратор:
template<class T>
struct pointer_comp {
typedef std::true_type is_transparent;
// helper does some magic in order to reduce the number of
// pairs of types we need to know how to compare: it turns
// everything into a pointer, and then uses `std::less<T*>`
// to do the comparison:
struct helper {
T* ptr;
helper():ptr(nullptr) {}
helper(helper const&) = default;
helper(T* p):ptr(p) {}
template<class U, class...Ts>
helper( std::shared_ptr<U,Ts...> const& sp ):ptr(sp.get()) {}
template<class U, class...Ts>
helper( std::unique_ptr<U, Ts...> const& up ):ptr(up.get()) {}
// && optional: enforces rvalue use only
bool operator<( helper o ) const {
return std::less<T*>()( ptr, o.ptr );
}
};
// without helper, we would need 2^n different overloads, where
// n is the number of types we want to support (so, 8 with
// raw pointers, unique pointers, and shared pointers). That
// seems silly:
// && helps enforce rvalue use only
bool operator()( helper const&& lhs, helper const&& rhs ) const {
return lhs < rhs;
}
};
тогда используйте это:
typedef std::set< std::unique_ptr<Foo>, pointer_comp<Foo> > owning_foo_set;
сейчас, owning_foo_set::find приму unique_ptr<Foo> или же Foo* или же shared_ptr<Foo> (или любой производный класс Foo) и найдите правильный элемент.
За пределами C++14 вы вынуждены использовать map в unique_ptr подход, или что-то эквивалентное, как подпись find чрезмерно ограничительный. Или написать свой set эквивалент.
Еще одна возможность, близкая к принятому ответу, но немного другая и упрощенная.
Мы можем использовать тот факт, что стандартный компаратор std::less<> (без аргументов шаблона) является прозрачным. Затем мы можем предоставить наши собственные функции сравнения в глобальном пространстве имен:
// These two are enough to be able to call objects.find(raw_ptr)
bool operator<(const unique_ptr<Object>& lhs, const Object* rhs) {
return std::less<const Object*>()(lhs.get(), rhs);
}
bool operator<(const Object* lhs, const unique_ptr<Object>& rhs) {
return std::less<const Object*>()(lhs, rhs.get());
}
class MyClass
{
// ...
private:
std::set<std::unique_ptr<Object>, std::less<>> objects; // Note std::less<> here
};
Хотя это определенно хак, я только что понял, что можно создать временный "тупой" unique_ptr с новым размещением без перераспределения рисков. removeObject() можно написать что-то вроде этого:
void MyClass::removeObject(const Object* target)
{
alignas(std::unique_ptr<Object>)
char dumbPtrData[sizeof(std::unique_ptr<Object>)];
objects.erase(
*::new (dumbPtrData) std::unique_ptr<Object>(const_cast<Object *>(target)));
}
Это решение будет работать для std::unordered_set, std::map ключи и std::unordered_map ключи, все с использованием только стандартного C++11, с практически нулевыми ненужными издержками.
Вы можете попробовать использовать boost::multi_index_container с дополнительной индексацией по Object*. Что-то вроде этого:
typedef std::unique_ptr<Object> Ptr;
typedef multi_index_container<
Ptr,
indexed_by<
hashed_unique<Ptr>,
ordered_unique<const_mem_fun<Ptr,Object*,&Ptr::get> >
>
> Objects;
Для получения дополнительной информации см. Документацию Boost Multi-index Containers.
Или, может быть, вы можете использовать std::shared_ptr везде, или вместо этого использовать сырые указатели в наборе?
Зачем вам нужен поиск по сырому пинтеру? Если вы храните его где-нибудь и проверяете, что объект с этим указателем действителен, тогда лучше использовать std::shared_ptr для хранения в контейнере и std::weak_ptr для других объектов. В этом случае перед использованием вам вообще не нужен поиск по необработанному указателю.
ОБНОВЛЕНИЕ 2: Якк прав, нет способа сделать это со стандартными контейнерами C++11 без существенных компромиссов. Либо что-то будет работать в линейном времени в худшем случае, либо есть те обходные пути, которые вы напишите в своем вопросе.
Есть два обходных пути, которые я бы рассмотрел.
Я бы попробовал отсортированный std::vectorАналогично boost:: container:: flat_set. Да, вставки / стирания будут линейными по времени в худшем случае. Тем не менее, это может быть намного быстрее, чем вы думаете: смежные контейнеры очень удобны для кэширования по сравнению с контейнерами на основе узлов, такими как std::set, Пожалуйста, прочитайте, что они пишут в boost:: container:: flat_set. Приемлем ли этот компромисс для вас, я не могу сказать / измерить.
Другие также упоминали std::share_ptr, Я лично стараюсь их избегать, главным образом потому, что "разделяемый указатель так же хорош, как и глобальная переменная" (Шон Родитель). Еще одна причина, по которой я не использую их, заключается в том, что они имеют большой вес, отчасти из-за многопоточности, которая мне обычно не нужна. Тем не мение, boost::shared_ptr, когда BOOST_SP_DISABLE_THREADS определяется, удаляет все накладные расходы, связанные с многопоточностью. Я верю, используя boost::shared_ptr было бы самым простым решением в вашем случае.
ОБНОВЛЕНИЕ: Как любезно указал Якк, мой подход имеет линейную сложность по времени...:(
(Первая версия.)
Вы можете сделать это, передав пользовательский компаратор std::lower_bound(), Вот элементарная реализация как:
#include <algorithm>
#include <cassert>
#include <iostream>
#include <memory>
#include <set>
#include <string>
using namespace std;
template <typename T>
class Set {
private:
struct custom_comparator {
bool operator()(const unique_ptr<T>& a, const T* const & b){
return a.get() < b;
}
} cmp;
set<unique_ptr<T>> objects; // decltype at begin() and end()
// needs objects to be declared here
public:
auto begin() const -> decltype(objects.begin()) { return objects.begin(); }
auto end() const -> decltype(objects.end() ) { return objects.end(); }
void addObject(unique_ptr<T>&& newObject) {
objects.insert(move(newObject));
}
void removeObject(const T* target) {
auto pos = lower_bound(objects.begin(), objects.end(), target, cmp);
assert (pos!=objects.end()); // What to do if not found?
objects.erase(pos);
}
};
void test() {
typedef string T;
Set<T> mySet;
unique_ptr<T> a{new T("a")};
unique_ptr<T> b{new T("b")};
unique_ptr<T> c{new T("c")};
T* b_ptr = b.get();
mySet.addObject(move(a));
mySet.addObject(move(b));
mySet.addObject(move(c));
cout << "The set now contains: " << endl;
for (const auto& s_ptr : mySet) {
cout << *s_ptr << endl;
}
mySet.removeObject(b_ptr);
cout << "After erasing b by the pointer to it:" << endl;
for (const auto& s_ptr : mySet) {
cout << *s_ptr << endl;
}
}
int main() {
test();
}
Вы используете уникальные пинтеры здесь. Это означает, что ваш набор обладает уникальным владением объектами. Теперь это должно означать, что если объект существует, он либо находится в наборе, либо у вас есть уникальный указатель с ним. Вам даже не нужно искать набор в этом случае.
Но мне кажется, что это не так. Я полагаю, вам лучше использовать совместно используемый указатель в этом случае. Просто храните общие указатели и передавайте их, так как кто-то рядом с этим набором явно хранит их.