Use Parent/Interface types rather than implementation types
If you've got a method that returns, say, a TreeMap pointer, you can generally declare it to return a Map; you're unlikely to use a method ofTreeMap that isn't a method of Map (if there even are such things), so the calling code won't be affected.
This allows you, though, to change the implementation class to, say, HashMap without any other code being affected.
The same goes for parameters passed into a method. In general, only explicitly use the implementation type when creating the instance [i.e.new()].
[NOTE: There's an issue peculiar to C++ where one must make sure that the implementation class' destructor is virtual, or it won't be executed when one deletes a pointer of the parent-class type.]