Ok. Adesso è chiaro.
http://www.cplusplus.com/reference/a...et_difference/
Come vedi dal link, la set_difference è in overload. La seconda versione prende una funzione o function object per il confronto (stessa cosa per la set_union
Riprendendo il tuo codice, diventa.
codice:
///////////////////////////////////////////////////////////
// Function object
struct mycmp {
	bool operator () (const pair<int,object*>& a, const pair<int,object*>& b) { 
		return a.first < b.first; 
	}
};

////////////////////////////////////////////////////////////

typedef map<int, object*> intV;  
intV mappa1, mappa2, mappaFinale;

mappa1[0] = new object A(0, 0,0, "testo stringa0")
mappa1[2] = new object A(2, 2,2, "testo stringa2")
mappa1[4] = new object A(4, 4,4, "testo stringa4")

mappa2[0] = new object A(2, 4,5, "testo stringa0seconda")
mappa2[2] = new object A(2, 4,5, "testo stringa1seconda")
mappa2[4] = new object A(2, 4,5, "testo stringa4seconda")

//cosi:
intV::iterator it = mappafinale.begin();
	set_difference(mappa1.begin(),mappa1.end(),mappa2.begin(),mappa2.end(),                  
inserter(mappafinale,it), mycmp() );

//o direttamente nel vector (dev'essere di std::pair).

vector< pair<int, object*>  > vectorfinale;
set_difference(mappa1.begin(),mappa1.end(),mappa2.begin(),mappa2.end(),                  
back_inserter(mappafinale), mycmp() );