2

我正在编写一个 Composite 类（类似于QObjectQt），目前我将孩子存储在std::vector. 每个 Composite 实例都有一个名称，并且该名称在作为该实例的兄弟的所有其他实例之间必须是唯一的，或者更好地说，在共享同一父级的实例之间必须是唯一的。

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

当孩子的数量变得一致时，我提出的代码非常愚蠢而且非常缓慢。

这是课程：

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);
            }
        }
    }
}

这对于很少的孩子来说可能很好，但是当他们变成数百人时，setName功能真的变得很慢。想象一下这种情况：

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

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

第一次很好，第二次在 ClashingName0 中更改名称，第三次首先将名称更改为 ClashingName0，然后找到与第二个实例的冲突并将名称设置为 ClashingName1 ...你明白了，它是指数级的，当它到达该循环的末尾时，会经过一段不可接受的时间。

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

我不是 C++ 的经验丰富的用户，我正在考虑使用map，或者unordered_map但我真的很想在这里获得专家的建议。

4

3 回答 3

2

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

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

映射的键是前缀，向量中的索引是第 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：多考虑一下，最好有一张地图，例如

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

现在，索引不再是向量中的索引，而是在第二张地图中的查找。这可以更好地处理删除，键将是我之前所说的复合键（对）。

归功于@Steves 的建议..

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

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

于 2012-06-27T12:01:04.080 回答
1

要么 要么map将unordered_map完成这项工作，使用count函数来测试名称是否在地图中，以及find函数或operator[]访问它。

unordered_map总体上可能会快一些。

map可以更好地处理您讨厌的"ClashingName"示例，因为您可以使用lower_boundor在单个查找中找到最后一个冲突的名称，而不是依次upper_bound查找每个ClashingName0...。ClashingName9999

请注意，map默认情况下按字典顺序排序，所以ClashingName10在ClashingName9. 当有人为您提供一个包含数字的名字时，尤其是在结尾处，也会出现问题。

用 Nim 的建议解决这个问题——使用一对string, int作为映射键，并根据需要从该对构造名称。同样，当有人为您提供以数字结尾的名称时，您必须做一些特别的事情。确保名称"Clash10"不能出现两次，一次("Clash", 10)和一次("Clash1", 0)。一个简单的选项是从提供的名称中禁止一个字符，并将其用作分隔符。

于 2012-06-27T12:06:09.227 回答
0

如果您不介意每个对象有一个额外的地图，您可以执行以下操作：

// inside Composite definiton
std::map<std::string, int> names_of_descendants;

然后简单地说：

void Composite::setName(const std::string &name)
{
    if (ancestor)
    {
        // for the first usage of certain name, map's operator[]
        // will insert default constructed int (0) in the map
        this->name = name + ancestor->names_of_descendants[name];

        // increment the value for this name, for the next call of setName
        ++names_of_descendants[name];
    }
}

您可以保留用于存储后代的向量。

于 2012-06-27T12:15:20.090 回答