This is a continuation of Part I

In Part I, we learned about the Sorted Vector as a replacement for map where iteration, lookups and memory overhead per element matter, while we cared little about insertions and removals.

However the examples were rather simple: Keys are strings or integers.

What happens when the Key is a more complex structure?

Wait, why would we want a more complex structure?

Imagine the following problem, solved using a map:

//Declarations...
typedef std::string String;
struct Foo
{
    String m_name;
    Vector3 m_position;
    /* other data */
    Foo( const String &name ) : m_name( name ), /* ... */
    {
    }
};
typedef std::map<String, Foo*> FooMap;

//Relevant code
FooMap myMap;
if( myMap.find( "Name of Foo" ) != myMap.end() )
    myMap["Name of Foo"] = new Foo( "Name of Foo" );

This looks fine?? NO IT’S NOT.

For starters, the snippet is using a String instead of a hashed string for the key. But let’s forget about that. We’re doubling the amount of memory required for m_name, as it appears in both the key and the value.

This problem can be solved by using an std::set and a custom predicator/comparison function. And that’s exactly what we’re going to do, except we’ll be using the sorted vector. (note that when using sets, it’s not clear whether the memory saving by using a comparison function doesn’t come with slower performance to just using map due to little details in implementation differences between map and set).

// If m_name is private, declare this function as friend of Foo, to avoid using a getter.
inline bool OrderFooByName( const Foo *_left, const Foo *_right )
{
        return _left->m_name < _right->m_name;
}

typedef std::vector<Foo*> FooVec;
FooVec myVec;
Foo dummyFoo( "Name of Foo" );

//Search, using the pred.
FooVec::iterator it = std::lower_bound( myVec.begin(), myVec.end(), &dummyFoo, OrderFooByName );
if( it != myVec.end() && (*it)->m_name != myVec.end() )
{
    myVec.insert( it, new Foo( "Name of Foo" ) );
}

A “Dummy Foo” is needed for lookup. In this case we could’ve new’ed Foo, and if the entry was already there, delete it. Otherwise insert it. But when you’re just searching an entry by its key, the dummy is needed.

We can get rid of the dummy though:

struct OrderFooByName
{
    inline bool operator () ( const Foo *_left, const String &_right ) bool
    {
        return _left->m_name < _right;
    }
    inline bool operator () ( const String &_left, const Foo *_right ) bool
    {
        return _left < _right->m_name;
    }
};

typedef std::vector<Foo*> FooVec;
FooVec myVec;
FooVec::iterator it = std::lower_bound( myVec.begin(), myVec.end(), "Name of Foo", OrderFooByName() );
if( it != myVec.end() && (*it)->m_name != myVec.end() )
{
    myVec.insert( it, new Foo( "Name of Foo" ) );
}

Summary

With this little trick, we can replace a set and often, a map, with just a sorted vector and a predicator function. Even if the structure is complex or a pointer and not just ints and floats.
To someone not used to the pattern, it may look alien; but it’s easy to pick up once you know how it works.
Remember that sorted vectors are great for iteration and performing lookups compared to maps and sets, which makes them great for game development. But they trade insertion and removal performance.