通过 std::weak_ptr 删除对象

Question

我有一个包含数千个对象的 std::vector，存储为 shared_ptr。由于该对象具有许多可用于搜索的属性，因此我使用 weak_ptr.

在 std::map 和 std::multimap 上维护此 std::vector 的多个索引

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

由于 map 和 multimap 是平衡二叉树，search/modify 非常快。但是，我对删除有点不知所措。我想在通过其中一个索引查找对象后删除。锁定 weak_ptr 给我 shared_ptr，但它不允许我破坏矢量上的对象。有什么方法可以删除vector上的原始对象吗？

Answer 1

这可能是一个用例，其中 std::set 比 std::vector 更合适。 std::set 保证在对数时间内查找、插入和删除。因此，您可以在您的一个地图对象中按索引查找对象，然后在具有 log(N) 性能的任何容器中删除它。

如果 insertion/removal 操作代表您的应用程序中的性能瓶颈，我会建议这种方法。

顺便说一句，请仔细考虑 shared_ptr 的实际需要，因为 shared_ptr 与 unique_ptr 相比会带来一定的性能开销。您的所有者容器可以使用 unique_ptr 并且各种映射可以简单地使用原始指针。

Answer 2

从你发布的内容来看，你的数据结构似乎不适合你想做的事情。

shared_ptr 只应用于表达共享所有权。但是，您发布的代码和删除对象的愿望表明 Objects 实际上是其对象的唯一所有者。
您的 vector<shared_ptr<object>> 似乎仅用作数据存储容器（按 id 或名称搜索的所需功能已在其他地方实现），但从 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 的迭代器在（其他对象的）插入和删除时保持有效，这样来自查找器的 return 不会因插入和删除而失效。我使用 std::forward_list<obj_it> 到 return 对象以允许 returning none 或几个。

Answer 3

因此，这是另一种选择，基于通过移动 std::unique_ptr<> 导入对象。不幸的是，unique_ptr 不是 std::set 的有用键（因为它们是唯一的），除非你有 C++14，当 set::find() 可以接受另一个参数而不是键时（见下文） .

对于 C++11 方法，因此必须使用 std::map 来存储 unique_ptr，这需要将 id 和 name 条目：一次在 data_t 中，一次作为 map 中的键。这是草图。

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 数据的重复，但是requires/assumes 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);
}

这里可能存在一些错误，尤其是取消引用各种迭代器和指针类型时的错误（尽管一旦编译这些应该没问题）。

通过 std::weak_ptr 删除对象

Deleting an object via std::weak_ptr

c++

boost-smart-ptr

c++11