2

我有一个包含数千个对象的 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 是平衡的二叉树，因此搜索/修改速度非常快。但是，我对删除有点困惑。我想在通过索引之一查找对象后删除。锁定weak_ptr 给了我shared_ptr，但它不允许我破坏向量上的对象。有什么方法可以删除向量上的原始对象吗？

4

3 回答 3

2

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

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

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

于 2017-05-04T11:29:16.893 回答
2

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

  1. shared_ptr只能用于表示共享所有权。但是，您发布的代码和您删除指向的对象的愿望表明它Objects实际上是其对象的唯一所有者。
  2. 您vector<shared_ptr<object>>似乎仅用作数据存储容器（通过 id 或名称搜索所需的功能在其他地方实现），但从 avector中删除元素通常很昂贵，因此您最好使用另一种类型的容器。

如果您的对象没有其他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>用来返回对象以允许返回一个或多个。

于 2017-05-04T13:08:07.473 回答
1

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

对于C++11方法，因此必须使用std::map来存储unique_ptrs，这需要加倍的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++14id解决方案的草图，它避免了映射中的和数据的重复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);
}

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

于 2017-05-04T15:34:55.017 回答