std::map insert o std::map find?

La respuesta es que no lo haces. En su lugar, desea hacer algo sugerido por el artículo 24 de STL efectivo de Scott Meyers:

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
    // key already exists
    // update lb->second if you care to
}
else
{
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup
}

La respuesta a esta pregunta también depende de lo caro que sea crear el tipo de valor que está almacenando en el mapa:

typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;

void foo (MapOfInts & m, int k, int v) {
  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.first->second = v;
  }
}

Para un tipo de valor como un int, lo anterior será más eficiente que una búsqueda seguida de una inserción (en ausencia de optimizaciones del compilador). Como se indicó anteriormente, esto se debe a que la búsqueda a través del mapa solo se realiza una vez.

Sin embargo, la llamada a insertar requiere que ya tenga construido el nuevo "valor":

class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;

void foo (MapOfLargeDataType & m, int k) {

  // This call is more expensive than a find through the map:
  LargeDataType const & v = VeryExpensiveCall ( /* ... */ );

  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.first->second = v;
  }
}

Para llamar a 'insertar', estamos pagando la costosa llamada para construir nuestro tipo de valor, y por lo que dijo en la pregunta, no usará este nuevo valor el 20% del tiempo. En el caso anterior, si cambiar el tipo de valor del mapa no es una opción, entonces es más eficiente realizar primero la 'búsqueda' para verificar si necesitamos construir el elemento.

Alternativamente, el tipo de valor del mapa se puede cambiar para almacenar identificadores de los datos utilizando su tipo de puntero inteligente favorito. La llamada a insertar utiliza un puntero nulo (muy barato de construir) y solo si es necesario se construye el nuevo tipo de datos.

Apenas habrá diferencia en la velocidad entre los 2, find devolverá un iterador, insert hace lo mismo y buscará en el mapa de todos modos para determinar si la entrada ya existe.

Así que... depende de las preferencias personales. Siempre trato de insertar y luego actualizar si es necesario, pero a algunas personas no les gusta manejar el par que se devuelve.