Iterators and Other Design Considerations

[smbanasik]

@leviathaninc after going over how to best implement iterators, it seems like the method used in the STL is the best option. I wanted to utilize inheritance to define an interface, which would allow us to force that interface to be used, but that adds a layer of indirection and it's quite costly. It's best to avoid abstract classes (and by extension interfaces) as much as possible. Instead, we'll have to rely on an externally defined contract and assume that the user must be using an iterator that's compliant with what we expect.

To generalize this concept, we need to use templates for containers, and each container will need an iterator which will act as the bridge between the containers and other things we define (such as algorithms). Iterators will need to be defined for each container, and they'll need to at minimum have the functionality that we expect for a given type. We can still specialize iterators as needed, but they'll need that minimum functionality.

I'll experiment with this, I want invalid usage of an iterator to break at compile time and I'm not sure how we would take care of that. Here is something that talks about the iterator pattern, and we may consider using a different pattern all together.

[smbanasik]

Another issue that I'm having with the STL iterator method is that it's not fully container independent. If you change containers, you must change all of the iterator declarations associated with the container unless you use the auto keyword.

So what are our options so far?

• Inheritance based system
  • We define a common interface for each type of iterator, then classes may extend from these.
  • Pros: easy to implement, we achieve container independence
  • Cons: not very efficient, virtual tables and indirection stink
• Template based system
  • Iterators receive the container type via template, we could use methods that each container has for operating the iterators that are private, then friend the iterator class to use those functions
  • Pros: no indirection
  • Cons: not container independent, pushes the iterator requirements to containers which still have no common interface, just a standard for containers (this makes it less obvious if a container has an iterator or not, and what about different types of iterators?)
• Subclass system
  • This is what the STL does, each iterator is a subclass of the container.
  • Pros: no indirection
  • Cons: not container independent, no real common interface, just a standard

We should prioritize performance since this is meant to be a lower level library, so in my opinion the first option is out. Since the second option would lead to more structural issues, I'm leaning towards repeating the method of what the STL does since it would lead to issues being caught the earliest. However, I'm still not fully satisfied with this method.