Graph library - graph interface I am trying to write simple graph lib in C++, BFS, DFS etc.. 
I want to create class GraphI which will represent any graph and will include necessary methods so my library could work.
Could I add/remove/improve something from my code?  

#pragma once
#include &lt;algorithm&gt;
#include "colors.h"
struct Vertex;
template &lt; typename T &gt;
class GraphI {

public:
    struct Vertex {
        Vertex( const T&amp; k, color col = color::w, int c = -1 )
            : key( k )
            , color(col)
            , cost( c ) {}

        int getCost() const { return cost; }
        const T&amp; getKey() const { return key; }
        T&amp; getKey() { return key; }
        void setColor( color c ) { color = c; }
        color getColor() { return color; }

        int cost;
        color color;
        T key;
        bool operator&lt;( const Vertex&amp; v1 ) const {
            return key &lt; v1.key;
        }
    };
    using Graph = std::map&lt;Vertex, std::list&lt;Vertex&gt; &gt;;
    GraphI() = default;
    virtual ~GraphI() = default;

    virtual void add_vertex( const T&amp; vertex ) {
        // if exists then add else do nothing
        _graph[ vertex ] = {};
        ++_size;
    } 
    virtual void add_edge( const T&amp; from,
                   const T&amp; to,
                  int cost = -1 ) {
        // if vertices do NOT exist return
        auto it = _graph.find( from );
        if ( it == _graph.end() ) return;

        auto it2 = _graph.find( to );
        if ( it2 == _graph.end() ) return;



        auto&amp; neighbours = it-&gt;second;
        auto it_exists = std::find_if( neighbours.begin(),
                        neighbours.end(),
                        [&amp;to]( const Vertex&amp; vertex ) { return vertex.getKey() == to; } );
        // if edge already exists
        if ( it_exists != neighbours.end() ) return;
        neighbours.emplace_back( Vertex(to, color::w, cost) );
    }
    virtual void remove_vertex( const T&amp; vertex ) {
        _graph.erase( vertex );
        --_size;
        // remove all edges going TO vertex
        for ( auto&amp; v : _graph ) { 
            auto it = std::find_if( v.second.begin(),
                        v.second.end(),
                        [&amp;vertex]( const auto&amp; v )
                        { return vertex == v.getKey(); } );
            // if vertex does NOT exist
            if ( it == v.second.end() ) return;
            v.second.erase( it );
        }

    }
    virtual void remove_edge( const T&amp; from, const T&amp; to ) {
        auto it = _graph.find( from );
        if ( it == _graph.end() ) return;

        auto &amp;edges = it-&gt;second;
        auto it2 = std::find_if( edges.begin(), edges.end(),
                    [&amp;]( const auto&amp; vertex ) { return vertex.key == to; } );

        if ( it2 == edges.end() ) return;
        edges.erase( it2 );
    }

    const Graph&amp; graph() const { return _graph; }
    unsigned size() const { return _size; }
private:
    Graph _graph;
    unsigned _size;
};
The comment in add_vertex is confusing and at contradicts what the code does.  If vertex already exists in _graph, the existing vertex will be replaced with an empty one, then the size increased (causing the internal _size to be incorrect).  Depending on what behavior you want when adding a vertex that already exists, you can use _graph.try_emplace, _graph.insert_or_assign, or just _graph[vertex] (to add a new entry if it does not exist, and do nothing if it does).

There is no benefit to maintaining a distinct _size variable.  As shown above, it can get out of sync with the actual size.  It is better to just call _graph.size() whenever the user calls Graph::size.

In remove_vertex, you should check the return value from _graph.erase to see if something was actually removed.  If nothing was removed there's no benefit to running any of the other code in the function.  Also, the if (it == v.second.end()) check should not return, as you avoid scanning the rest of the vertexes in _graph to remove edges that connect to the vertex that was just removed.  Alternatively, you can just replace that whole loop body with a call to either v.second.remove or v.second.remove_if.  (The same change can be made in remove_edge.)