Aptitude

The main difference is that Aptitude keeps track of which packages have been explicitly installed, and which were automatically pulled in via dependencies. It can then remove automatically installed packages that are not longer required. This typically happens for two reasons:

- You installed something (pulling in a bunch of dependencies), then changed your mind and removed it. - A library made an ABI breaking change, and bumped its major version number. Typically you'll end up with both the old and new versions installed. Once all applications have migrated, the old version can be removed. This is relatively rare.

 > So, if I use Aptitude I'll sometimes get some extra cleanup done. 
 > But if I also use other installers, Aptitude may think nothing is 
 > still using a lib when in fact it is. :( 

That shouldn't happen. If aptitude doesn't know how a package got installed (because something else installed it) it will assume it is required and leave it there. Remember that apt-get, aptitude, SmartPM, etc. are all just frontends to the real package management system (dpkg). As such they all share a common dependency tracking and installed package state. If you install software that's not debian packages you're pretty much on your own either way.