#define UNIT r2_bsearch
#include <vector>
#include <string>

class token;

class flat_map
{
    std::vector< std::pair< std::string, token > > _data;
public:
    bool emplace( std::string k, int v );
    int index( const std::string &k ) const;
    int index_or_throw( const std::string &k ) const;
    token &at( const std::string &k );
    const token &at( const std::string &k ) const;
    token &operator[]( const std::string &k );
};

#include "test_main.cpp"

int flat_map::index( const std::string &k ) const
{
    int low = 0, high = _data.size();

    while ( low < high )
    {
        int mid = ( low + high ) / 2;

        if ( k < _data[ mid ].first )
            high = mid;
        else if ( k > _data[ mid ].first )
            low = mid + 1;
        else
            return mid;
    }

    assert( low <= int( _data.size() ) );
    return low;
}

bool flat_map::emplace( std::string k, int v )
{
    int idx = index( k );

    if ( idx < int( _data.size() ) && _data[ idx ].first == k )
        return false;

    _data.emplace( _data.begin() + idx, std::move( k ), v );
    return true;
}

int flat_map::index_or_throw( const std::string &k ) const
{
    if ( int idx = index( k ); _data[ idx ].first == k )
        return idx;
    else
        throw std::out_of_range( "indexing flat_map" );
}

token &flat_map::at( const std::string &k )
{
    return _data[ index_or_throw( k ) ].second;
}

const token &flat_map::at( const std::string &k ) const
{
    return _data[ index_or_throw( k ) ].second;
}

token &flat_map::operator[]( const std::string &k )
{
    if ( int idx = index( k ); _data[ idx ].first == k )
        return _data[ idx ].second;

    emplace( k, 0 );
    return at( k );
}