What iterator to return for non-existing map How to signkey?

Question

I want to have a function which searches for a key in a collection of maps and returns an iterator to the found key. But what should be returned in case the key cannot be found? I cannot return map::end since the collection of maps can be empty.

Thanks.

map<string, string>::iterator CConfFile::GetKey(const string &SectionName, const string &KeyName)
{
    maps<string, map<string, string> >::const_iterator Section = _Sections.find(SectionName);
    if (Section != _Sections.end()) {

        map<string, string> &Keys = SectionPtr->second;

        map<std::string, string>::const_iterator Key = Keys.find(KeyName);
        if (Key != Keys.end())
            return Key;
    }

    cerr << "Key " << KeyName << "not found\n";
    return WHAT???;
}

Answer 1

You could define your own proxy iterator class, which wraps the map iterator and passes on all operations to it. Then your class can have a special "end" value and you can return that value for not found. Caller then needs a way to get an end proxy iterator, for comparison.

If you want to be really flash, your iterator could know how to "step forward" from the end of one contained map to the beginning of the next one, so that it can be used to iterate over all the maps in the collection. Admittedly not in key order.

Another option is to return a pair of (iterator, bool). Your "deep find" already doesn't return the type that find functions usually return when called with a container (i.e. the iterator type of the container), so you can just go for a total change.

Iterators aren't required to be default-constructible, although they often are. So it's actually a bit tricky to have an "meaningless iterator" and be properly portable. You could try default-constructing your map iterator, though, and if it works in your implementation, use that in the case where the bool is false.

I'm not sure what Boost.Optional does with types which aren't default-constructible, but that might be helpful as a return value.

Answer 2

You could build a special NotAKey-class (see the Null-Object-Pattern), and then have a default map that only contains one object of that class. Whenever no key is found or no map exists, you just return that special iterator.

I think you could also try to write a special iterator to return for such cases yourself, but I never tried that, so I'm not sure.

EDIT: I think sbi's answer is much better than mine, only you should not return a pointer, but a reference, and then use a reference to the Null-Object (could be global singleton) instead of a null-pointer.

Answer 3

If you return an iterator, then that implies that one can actually iterate over all the values. If thats indeed the case, you would have to return a custom iterator type anyway and you should have no problem to denote a special end iterator.

If the iterator isn't intended to be used as an iterator, it might be better to return a pointer to the found object, and a null pointer in case there isn't any.

Answer 4

You should use map::end, since it doesn't point to the last value but it's special value meaning "you've reached end of the list" and doesn't contain any value.

Read http://msdn.microsoft.com/en-US/library/c84shb7e%28v=VS.80%29.aspx

Focus on overview and remarks.

Answer 5

Even if this doesn't answer your question I wanted to post in case this can help you.

I find your problem very interesting. We could define of a new generic multi key map class that allows to behave like a map > and in addition as a map, T> allowing to iterate over all the elements on the collection. Boost.Multi-Index allows to define several index over a collection, but I don't think different index can iterate over different types. I will check this and come back with more info.

I don't know what are the other uses of your map of maps, but if you don't need to iterate over the map of keyName you can transform it into a map, string>, and so you will be able to return just map, string>::end.