"Bill Buklis"
From an aesthetics standpoint, it would be nice to have the two types of iterators depending on what you need. The code would be more readable. It would also shut those up who complain about the iterators not acting like std::map. "Look, use map_iterator if you want that!" Also in those cases where you do need both the key and the value, you wouldn't have to cast the void* back to the correct object type.
From an aesthetics standpoint, you should re-use transform_iterator with the appropriate function object to project a tuple of references into either the first or second element, rather than fattening the interface of this particular container. That transform_iterator idiom could then be re-used with std::map.
-- Dave Abrahams Boost Consulting www.boost-consulting.com