C++ expected type-specifier

Question

Background

I am in the middle of a project writing stl-like containers for the Arduino. So far I have successfully written deque, vector, and string.

Problem

I have run into a problem with the map container. For some reason, in the map::insert() method, the compiler is telling me that it is expecting a type specifier. I have included all the code related to the problem. Any help would be appreciated.

///////////////////////////////////////////////////////////////////////////////
// pair
///////////////////////////////////////////////////////////////////////////////
template<typename K, typename V>
class pair {
public:
    pair( const K& key, const V& val )
    : _key_( key )
    , _val_( val )
    {}

    pair( const pair& p )
    : _key_( p.key() )
    , _val_( p.val() )
    {}

    virtual ~pair(){}

    K& key(){
        return _key_;
    }

    V& val(){
        return _val_;
    }

private:
    K _key_;
    V _val_;
};

///////////////////////////////////////////////////////////////////////////////
// map
///////////////////////////////////////////////////////////////////////////////
template<typename K, typename V>
class map {
public:
    map()
    : _size_( 0 )
    , _items_( 0 )
    {}

    virtual ~map(){
        for( int i = 0; i < _size_; ++i )
            delete _items_[i];

        free( _items_ );

    }

    void insert( const pair<K,V>& p ){
        _items_ = reinterpret_cast<kick::pair<K,V>**>( realloc( _items_, (sizeof( void* ) * (++_size_)) ) );
        _items_[_size_ - 1] = new pair( p ); //error: expected type-specifier
    }

    V& operator[]( const K& key ){
        for( int i = 0; i < _size_; ++i ){
            if( _items_[i].key() == key )
                return _items_[i].val();

        }

    }

private:
    int _size_;
    pair<K,V>** _items_;

};

Answer 1

pair is just a template, not a type. The compiler is expecting the template parameters, which in this case are types. This is, it is expecting your line to be:

_items_[_size_ - 1] = new pair<K,V>( p );

No, it cannot deduce the template parameters; this only works for template functions, not types.

Answer 2

new pair<K,V>( p ) is what it wants there.

For myself, I'd implement a flat-map on top of vector so I didn't have to do memory management in it. An advantage of this is that you can remove a level of indirection. (Indirection is the performance killer).

Another thought is to have a high-water sorting mark, where things before the sorting mark are sorted, and things after it are jumbled. This can give you fewer comparisons when the container gets large. But first get your flat-map working.