Is std::string an object?

Question

just looking in optimizing some std::map code. The map contains objects, accessed via the string-identifier.

Example:

std::map<std::string, CVeryImportantObject> theMap;

...

theMap["second"] = new CVeryImportantObject();

Now, when using the find-function as theMap->find("second"), the String is converted into std::string("second"), which causes new string allocations (over all when using IDL=2 with Visual Studio).

1. Is there a possibility to use a string-only class to avoid such allocations?

Intentionally I've tried to use another String-Class as well:

std::map<CString, CVeryImportantObject> theMap;

This code works also. But CString indeed is an object.

And: If you remove an object from the map, I'll need to release both the related object and the key, do I?

Any suggestions?

Answer 1

Now, when using the find-function as theMap->find("second"), the String is converted into std::string("second"), which causes new string allocations

Not necessarily. VC uses Small-String Optimisation (SSO). This means that for a string as short as "second", no allocation on the heap should take place at all; the characters will instead be stored directly in the temporarily created std::string object.

This is still not free (because the std::string has to be created, albeit without any dynamic allocation happening inside), but should be good enough. Is it really a concern for you? Chances are very high that it does not cause any measurable performance decrease.

1. Is there a possibility to use a string-only class to avoid such allocations?

Not really, except of the C++14 fix mentioned in other answers. Using char const * as the key type is very dangerous, because std::map will only store the actual addresses, not copies of the keys.

If I were you and if I really experienced performance problems, I'd just not use std::map directly but create my own container class to wrap a std::map<char const *, T, CustomComparison> and do the hard pointer work inside.

template <class ValueType>
class FastStringMap
{
private:

    struct Comparison
    {
        bool operator()(char const *lhs, char const *rhs) const
        {
            return strcmp(lhs, rhs) > 0;
        }
    };

    typedef std::map<char const *, ValueType, Comparison> WrappedMap;

    WrappedMap m_map;

public:
    typedef typename WrappedMap::iterator iterator;
    typedef typename WrappedMap::const_iterator const_iterator;

    bool insert(char const *key, ValueType const &value)
    {
        if (m_map.find(key) != m_map.end())
        {
            return false;
        }
        else
        {
            char *copy = new char[strlen(key) + 1];
            strcpy(copy, key);

            try
            {
                return m_map.insert(std::make_pair(copy, value)).second;
            }
            catch (...)
            {
                delete copy;
                throw;
            }
        }
    }

    ~FastStringMap()
    {
        for (iterator iter = m_map.begin(); iter != m_map.end(); ++iter)
        {
            delete[] iter->first;
        }
    }

    iterator find(char const *key)
    {
        return m_map.find(key);
    }

    const_iterator find(char const *key) const
    {
        return m_map.find(key);
    }

    // further operations
};

To be used like this:

FastStringMap<int> m;
m.insert("AAA", 1);
m.insert("BBB", 2);
m.insert("CCC", 3);
std::cout << m.find("AAA")->second;

Note that you can possibly make this more sophisticated by templatising also on the character type (for std::wstring support) or by providing "real" iterator classes (using Boost Iterator Facade).

And: If you remove an object from the map, I'll need to release both the related object and the key, do I?

If you use std::string, no. If you use char const * and if the pointers point to memory allocated dynamically (as in my example), then yes.

Answer 2

If you always use string constants as keys, you can use const char * as key type in map when you use proper comparator:

struct PCharCompare {
    bool operator()( const char *s1, const char *s2 ) const { return strcmp( s1, s2 ) < 0; }
}; 

std::map< const char *, CVeryImportantObject, PCharCompare> theMap;

Note: you have to be careful and need to understand how it works, as it can easily lead to UB:

void foo() {
    char buffer[256];
    snprintf( buffer, sizeof( buffer ), "blah" );
    theMap.insert( std::make_pair( buffer, Object ) );
} // ups dangled pointer in the map

As for optimization, it is very unlikely that std::string creation is a culprit. you may try to use std::unordered_map or something similar for optimization

Answer 3

Now, when using the find-function as theMap->find("second"), the String is converted into std::string("second"), which causes new string allocations (over all when using IDL=2 with Visual Studio).

This is a Standard issue, which is fixed in C++14 for ordered containers. The newest version of VS, VS 14 CTP (which is a pre-release) contains a fix for this issue, as will new versions of other implementations.

If you need to avoid allocations, you can try a class like llvm::StringRef which can refer to std::string or string literals interchangably, but then you will be left trying to handle the ownership externally.

You can try something like unique_ptr<char[], maybe_delete> that sometimes deletes the contents. This is a bit of a mess to interface with though.

And: If you remove an object from the map, I'll need to release both the related object and the key, do I?

The map will automatically destruct the key and value for you. For a class which frees it's own resources like std::string, which is the only sane way to write C++, then you can erase without worrying about resource cleanup.