What is the best strategy to store objects ensuring unique name and being able to efficiently retrieve them later, in c++?

Question

I'm coding a Composite class (similar to QObject of Qt) and at the moment I'm storing the children in a std::vector. Each Composite instance has a name and this name has to be unique between all the other instances that are siblings of this one, or probably better said, between the instances that share the same parent.

Each time a new instance is pushed inside the vector, I must look if its name is already used by one of the instances already in the vector, if it does, I must change its name adding a number.

The code I came up with is quite silly and very slow when the number of children become consistent.

here is the 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);
};

this is the constructor and setName implementation:

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

This might be fine for very few children, but when they become hundreds then the setName function really become slow. Imagine this situation:

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

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

the first time is fine, the second time the name is changed in ClashingName0, the third time the name is firstly cahnged into ClashingName0, than it find the clashing with the second instance and set the name to ClashingName1... you got the idea, it is exponential, when it comes at the end of that loop an unacceptable amount of time is passed by.

So the real problem here is how to efficiently find the name clashing and efficiently assign a new name that is not already used? Any std container is fine for me and my compiler support C++11, but I can't/want to use Boost because the project I'm working on is incredibly small (it is basically this class)

I'm not exactly a seasoned user of C++, I was thinking to use map or unordered_map but I'm really hungry for experts' suggestions here.

Answer 1

If you don't mind an additional map per object, you could do the following:

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

Then simply:

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

You can keep the vector for storing descendants.

Answer 2

Either map or unordered_map will do the job, use the count function to test whether a name is in the map or not, and the find function or operator[] to access it.

unordered_map is likely to be a bit faster overall.

map can deal better with your nasty "ClashingName" example, because you can use lower_bound or upper_bound to find the last clashing name in a single lookup, rather than looking up each of ClashingName0 ... ClashingName9999 in turn.

Beware that map by default sorts in lexicographical order, so ClashingName10 comes before ClashingName9. There are also problems to do with what happens when someone provides you with a name that has digits in it, especially at the end.

Fix this with Nim's suggestion -- use a pair of string, int as the map key, and construct the name from that pair as required. Again, you have to do something special when someone supplies you with a name that ends in digits. Make sure that the name "Clash10" can't occur twice, once as ("Clash", 10) and again as ("Clash1", 0). A simple option is to forbid one character from the provided name, and use that as a separator.

Answer 3

IMO, you need to change the way your objects are stored. Something like the following:

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

The key to the map is the prefix, and the index in the vector is the nth Composite object. You would need to provide a custom lookup function which split the passed in name.. e.g.

std::string query = "pipo_10";

In your lookup function,

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
}

EDIT 1: To save all the string operations, you could define your own custom key, which is simply a pair (e.g, std::pair<std::string, int> which is the prefix and the index), and your lookup would simply use the values from this key.

EDIT 2: Thinking about this a little more, better to have a map of map, e.g.

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

Now instead of the index being an index in the vector, it's a lookup in the second map. This handles deletions better, the key will be the composite key as I said before (the pair).

Crediting @Steves' suggestion..

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

Use the lower_bound() trick to locate the last index for the given Composite