c++ - 在 C++ 中，存储对象确保唯一名称并能够在以后有效检索它们的最佳策略是什么？

Question

我正在编写一个 Composite 类(类似于 Qt 的 QObject)，目前我将子级存储在 std::vector 中。 每个复合实例都有一个名称，并且该名称在该实例的所有其他同级实例之间必须是唯一的，或者更好的说法是，在共享同一父级的实例之间是唯一的。

每次将新实例插入 vector 时，我必须查看其名称是否已被 vector 中已有的实例之一使用(如果已使用) ，我必须更改其名称并添加一个数字。

当 child 的数量变得一致时，我想出的代码非常愚蠢并且非常慢。

这是类(class):

class Composite
{
public:
    Composite(const std::string &name, Composite *ancestor=NULL);
    ~Composite();

private:
    std::string name;
    Composite *ancestor;
    std::vector<Composite*> descendants;

public:
    void setName(const std::string &name);
};

这是构造函数和 setName 实现:

Composite::Composite(const std::string &name, Composite *ancestor)
{
    this->ancestor = ancestor;
setName(name);
if (ancestor!=NULL)
    ancestor->descendants.push_back(this);

}

.

void Composite::setName(const std::string &name)
{
    this->name = name;

    if (ancestor!=NULL)
    {
        CompositeList::iterator dIt;
        for( dIt=ancestor->descendants.begin(); dIt!=ancestor->descendants.end(); dIt++)
        {
            if ((*dIt)==this)
            {
                continue;
            }
            else if (this->name == (*dIt)->getName())
            {
                 int trailingNumber = stringToInt(getTrailingNumber(this->name));
                 std::string cleanName = removeTrailingNumber(this->name);
                 this->name = cleanName+intToString(trailingNumber+1);
            }
        }
    }
}

这对于很少的 child 来说可能没问题，但是当他们变成数百个时，setName 函数真的会变得很慢。 想象一下这种情况:

Composite *parent = new Composite("pippo");

for (int i=0; i<10000; i++)
{
    Composite("ClashingName", parent);
}

第一次没问题，第二次在ClashingName0中更改名称，第三次名称首先更改为ClashingName0，然后它发现与第二个实例发生冲突并将名称设置为ClashingName1...你得到了这个想法，它是指数级的，当它到达循环结束时，就会过去 Not Acceptable 时间量。

所以这里真正的问题是如何有效地找到名称冲突并有效地分配一个尚未使用的新名称？ 任何 std 容器对我来说都很好，我的编译器支持 C++11，但我不能/不想使用 Boost，因为我正在处理的项目非常小(基本上就是这个类)

我并不是一个经验丰富的 C++ 用户，我想使用 map 或 unordered_map 但我真的很渴望专家的建议。

Answer 1

IMO，您需要更改对象的存储方式。类似于以下内容:

std::map<std::string, std::vector<Composite> >

映射的关键是前缀， vector 中的索引是第n个Composite目的。您需要提供一个自定义查找函数来分割传入的名称..例如

std::string query = "pipo_10";

在您的查找函数中，

Composite* lookup(std::string const& key)
{
  // split the key to get the prefix and the index
  // lookup in the map using the prefix
  // return the index
}

编辑1:要保存所有字符串操作，您可以定义自己的自定义键，它只是一对(例如std::pair<std::string, int>，它是前缀和索引)，以及您的查找将简单地使用此键中的值。

<罢工> 编辑2:再多考虑一下，最好有一张 map ，例如

std::map<std::string, std::map<int, Composite> >

现在，索引不再是 vector 中的索引，而是第二个映射中的查找。这可以更好地处理删除，键将是复合键，正如我之前所说的(成对)。

相信@Steves的建议..

std::map<std::pair<std::string, int>, Composite>

使用lower_bound()找到给定 Composite 的最后一个索引的技巧