Kill some more virtual calls and make code nicer to work with.

Also see if we can expose exact sized iterators while we're at it.