Удаление объекта с помощью std :: weak_ptr

У меня есть std :: vector с тысячами объектов, которые хранятся как shared_ptr. Поскольку объект имеет много атрибутов, которые можно использовать для поиска, я поддерживаю несколько индексов для этого std :: vector в std :: map и std :: multimap, используя слабый_птр.

std::vector<std::shared_ptr<Object>> Objects;
std::map<int,std::weak_ptr<Object>> IndexByEmployeeId;
std::multimap<std::string,std::weak_ptr<Object>> IndexByName;

Поскольку карта и мультикарта являются сбалансированными двоичными деревьями, поиск / изменение выполняются очень быстро. Тем не менее, я немного забочусь об удалении. Я хочу удалить после поиска объекта через один из индексов. Блокировка слабого_птра дает мне shared_ptr, но не позволяет уничтожить объект в векторе. Есть ли способ удалить исходный объект на вектор?

2

Решение

Из того, что вы опубликовали, кажется, что ваши структуры данных не соответствуют тому, что вы хотите сделать.

  1. shared_ptr следует использовать только для выражения совместной собственности. Тем не менее, ваш опубликованный код и ваше желание удалить объекты, указанные, чтобы указать, что Objects фактически является единственным владельцем своих объектов.
  2. Ваш vector<shared_ptr<object>> кажется, используется только как контейнер для хранения данных (требуемая функциональность поиска по идентификатору или имени реализована в другом месте), но удаляет элементы из vector как правило, дорого, так что вы можете использовать другой тип контейнера.

Если нет других shared_ptr к вашим объектам, то ваш дизайн оставляет желать лучшего. В этом случае вы не должны использовать какие-либо умные указатели, а просто container<object> и карты в это. Например что-то вроде этого (не проверено, даже не скомпилировано):

struct data_t { std::string name; /* more data */ };
using objt_map = std::map<std::size_t,data_t>;
using object   = objt_map::value_type;    // pair<const size_t,data_t>
using obj_it   = objt_map::iterator;
using name_map = std::multimap<std::string, obj_it>;
objt_map Objects;
name_map NameMap;

std::forward_list<obj_it> find_by_name(std::string const&name) const
{
auto range = NameMap.equal_range(name);
std::forward_list<obj_it> result;
for(auto it=range.first; it!=range.second; ++it)
result.push_front(it->second);
return result;
}

std::forward_list<obj_it> find_by_id(std::size_t id) const
{
auto it = Objects.find(name);
return {it == Objects.end()? 0:1, it};
}

void insert_object(std::size_t id, data_t const&data)
{
auto it = Objects.find(id);
if(it != Objects.end())
throw std::runtime_error("id '"+std::to_string(id)+"' already known");
Objects[id] = data;
NameMap.emplace(data.name, Objects.find(id));
}

void delete_object(obj_it it)
{
if(it==Objects.end())
throw std::runtime_error("attempt to delete invalid object");
auto range = NameMap.equal_range(it->second.name);
for(auto i=range.first; i!=range.second; ++i)
if(i->second==it) {
NameMap.erase(i);
break;
}
Objects.erase(it);
}

Обратите внимание на итераторы std::map остаются действительными при вставке и удалении (других объектов), так что возврат от искателей не будет аннулирован вставкой и удалением. я использую std::forward_list<obj_it> возвращать объекты, чтобы можно было вернуть ни одного, ни несколько.

2

Другие решения

Это может быть случай, когда std::set это правильный выбор std::vector, std::set гарантирует поиск, вставку и удаление в логарифмическом времени. Таким образом, вы можете искать объект по индексу в одном из ваших объектов карт, а затем удалять его в любом контейнере с log(N) спектакль.

Я бы предложил этот подход, если операции вставки / удаления представляют собой узкое место в производительности вашего приложения.

Кстати, внимательно рассмотрите фактическую необходимость shared_ptr, так как shared_ptr приходит с определенными накладными расходами производительности в отличие от unique_ptr например. Ваш владелец контейнер может использовать unique_ptr и различные карты могут просто использовать сырые указатели.

2

Итак, вот еще один вариант, основанный на импорте объектов путем перемещения std::unique_ptr<>, К несчастью, unique_ptrs не являются полезными ключами для std::set (поскольку они уникальны), если у вас нет C ++ 14, когда set::find() может принимать другой аргумент, чем ключ (см. ниже).

Для C ++ 11 подход, поэтому необходимо использовать std::map хранить unique_ptrс, что требует удвоения id а также name записи: один раз в data_t и однажды в качестве ключей в maps. Вот эскиз.

struct data_t {
const std::size_t id;       // changing these would
const std::string name;     // lead to confusion
/* more data */
};
using data_ptr = std::unique_ptr<data_t>;
using data_map = std::map<std::size_t,data_ptr>;
using obj_it   = data_map::iterator;
using name_map = std::multimap<std::string,obj_it>;
data_map DataSet;
name_map NameMap;

std::vector<data_t*> find_by_name(std::string const&name) const
{
auto range = NameMap.equal_range(name);
std::vector<data_t*> result;
result.reserve(std::distance(range.first,range.second));
for(auto it=range.first; it!=range.second; ++it)
result.push_back(it->second->get());
return result;
}

data_t* find_by_id(std::size_t id) const
{
auto it = DataSet.find(id);
return it == DataSet.end()? nullptr : it->second.get();
}

// transfer ownership here
void insert_object(data_ptr&&ptr)
{
const auto id = ptr->id;
if(DataSet.count(id))
throw std::runtime_error("id '"+std::to_string(id)+"' already known");
auto itb = DataSet.emplace(id,std::move(ptr));
auto err = itb.second;
if(!err)
err = NameMap.emplace(itb.first->name,itb.first).second;
if(err)
throw std::runtime_error("couldn't insert id  "+std::to_string(id));
}

// remove object given an observing pointer; invalidates ptr
void delete_object(data_t*ptr)
{
if(ptr==nullptr)
return;                 // issue warning or throw ?
auto it = DataSet.find(ptr->id);
if(it==DataSet.end())
throw std::runtime_error("attempt to delete an unknown object");
auto range = NameMap.equal_range(it->second->name);
for(auto i=range.first; i!=range.second; ++i)
if(i->second==it) {
NameMap.erase(i);
break;
}
DataSet.erase(it);
}

Вот эскиз для C ++ 14 решение, которое позволяет избежать дублирования id а также name данные на картах, но требует / предполагает, что data_t::id а также data_t::name неизменны.

struct data_t {
const std::size_t id;       // used as key in set & multiset:
const std::string name;     // must never be changed
/* more data */
};

using data_ptr = std::unique_ptr<data_t>;

struct compare_id {
using is_transparent = std::size_t;
static bool operator(data_ptr const&l, data_ptr const&r)
{ return l->id < r->id; }
static bool operator(data_ptr const&l, std::size_t r)
{ return l->id < r; }
static bool operator(std::size_t l, data_ptr const&r)
{ return l < r->id; }
};

using data_set = std::set<data_ptr,compare_id>;
using data_it  = data_set::const_iterator;

struct compare_name {
using is_transparent = std::string;
static bool operator(data_it l, data_it r)
{ return (*l)->name < (*r)->name; }
static bool operator(data_it l, std::string const&r)
{ return (*l)->name < r; }
static bool operator(std::string const&l, data_it r)
{ return l < (*r)->name; }
};

using name_set = std::multiset<data_it,compare_name>;

data_set DataSet;
name_set NameSet;

std::vector<data_t*> find_by_name(std::string const&name) const
{
auto range = NameSet.equal_range(name);
std::vector<data_t*> result;
result.reserve(std::distance(range.first,range.second));
for(auto it=range.first; it!=range.second; ++it)
result.push_back((*it)->get());
return result;
}

data_t* find_by_id(std::size_t id) const
{
auto it = DataSet.find(id);
return it == DataSet.end()? nullptr : it->get();
}

// transfer ownership here
void insert_object(data_ptr&&ptr)
{
const auto id = ptr->id;
if(DataSet.count(id))
throw std::runtime_error("id '"+std::to_string(id)+"' already known");
auto itb = DataSet.emplace(std::move(ptr));
auto err = itb.second;
if(!err)
err = NameSet.emplace(itb.first).second;
if(err)
throw std::runtime_error("couldn't insert id  "+std::to_string(id));
}

// remove object given an observing pointer; invalidates ptr
void delete_object(data_t*ptr)
{
if(ptr==nullptr)
return;                 // issue warning or throw ?
auto it = DataSet.find(ptr->id);
if(it==DataSet.end())
throw std::runtime_error("attempt to delete an unknown object");
auto range = NameSet.equal_range(ptr->name);
for(auto i=range.first; i!=range.second; ++i)
if((*i)==it) {
NameSet.erase(i);
break;
}
DataSet.erase(it);
}

Здесь могут быть некоторые ошибки, в частности ошибки с разыменованием различных типов итераторов и указателей (хотя после компиляции все должно быть в порядке).

1
По вопросам рекламы [email protected]