OOP only solves this problem if you can arrange that every possible type of container that the implementation might be using can be persuaded to support the same iterator mechanism, so that you can put a fixed for statement at the loop site and just vary the iterator implementation per container.
But I think that even if I'd been able to guarantee the availability of C++, it's not clear to me in this context that the various implementations would have been set up that way – they're all in code bases maintained by different groups of people who have no incentive to cooperate on issues like this. So it's quite likely that I'd still have needed some sort of macro-based parametrisation at the call site, even if it was less overwhelming than what I've got here.
Yeah - this is much easier in C#, where all of the built in collection types support IEnumerable, and if you were creating a new collection type then not supporting IEnumerable would be a bit silly.
(And yes, I know that C# isn't suitable for all sorts of things.)
Does even the ordinary array type support IEnumerable too? (I presume that C# still has ordinary array types, and doesn't actually require you to instantiate a dynamically allocated collection object every time you want to store n things in a row.)
Yup. Array implements IEnumerable and IEnumerable<>. I think it does some jiggery-pokery under the covers to do so, but I've never dug into how they actually work. I would have suspected they were significantly slower than pure C++, but it seems that I am incorrect: http://www.mightyware.com/cpp_vs_csharp_arrays.bhs
Nonono! C++ beats C for this sort of thing, but not because of objects and interfaces. You don't want to sully a simple linked-list traversal with run-time polymorphism, abstract interfaces and virtual function calls!
As I said below, the C++ feature that's actually useful here is generic programming and concept conformance. (Function overloading is indispensable to implementation of the forthcoming C++0x idiom.) Nothing about the idiom there (pedantry: except using ++i to increment the iterator and i==j to compare, rather than inc(i) and equal(i,j)) uses object-orientation at all.
By convention (in the Standard Template Library, originally designed by SGI but then standardised), if you have a container type C then you expect C::iterator to be an iterator over it that lets you modify the contained values, C::const_iterator to be one that only lets you read the contained values. Maybe C::iterator is the actual declared type; maybe it's a suitable typedef.
Also, by convention, if you have a container c, you expect c.begin() and c.end() to give you, respectively, an iterator pointing at the first item in the container and an iterator pointing immediately beyond the last item.
This latter convention is being firmly embedded in the C++0x standard that's due out any day now: when someone says for (int &x: myContainer) that is shorthand expressing a for loop between myContainer.begin() and myContainer.end(). (It doesn't actually care what the type returned by those functions is, provided thy both return the same type and it can be incremented, compared and dereferenced.)
This is achieved by container authors implementing iterators for the container types they create. Indeed, in most cases, creating the iterators is the very meat of container implementation and much else gets expressed in terms of them, at least implicitly.
As mentioned, iterators don't exhibit an interface in the Java sense: there's no run-time polymorphism. An iterator is, broadly, any type for which you can compare values for equality, increment values and dereference values (i.e. apply prefix * to them). Given those features, you can write generic code that works on any kind of iterator. (In reality that's approximately the input iterator concept — there are other concepts both more and less stringent, as well as regrettable gotchas, but the power of the system more than compensates in practice.)
I assume that there's a reason for having a convention rather than an actual contract. It seems odd to me that you wouldn't specify that "I am a container, and do the things that containers do" rather than just implementing the necessary methods and _not_ declaring that you're doing so.
The "input iterator" concept is just a useful set of features, coupled with the observation that if some classes implement all those features and some algorithms confine themselves to requiring just those features then they'll get along usefully together.
Unfortunately, one of the wrinkles is the key distinction between an input iterator and a forward iterator: you can copy a forward iterator and use the copy later to make a second pass through the data, whereas an input iterator is once-only (compare traversing a linked list with reading lines from a TCP socket). This distinction between contexts can't be directly enforced by the compiler. There is an iterator_category mechanism to get around the problem, but it's clunky.
There is also a proposal to extend the language with explicit concepts, but it's typical Stroustrup filth and was rightly rejected from C++0x. In due course, someone will come up with something nice to replace it, I hope.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
And then realised that you were working in C, not C++, and thus objects and interfaces were not an option for you!
And that made me remember why I like OOP so much.
forstatement at the loop site and just vary the iterator implementation per container.But I think that even if I'd been able to guarantee the availability of C++, it's not clear to me in this context that the various implementations would have been set up that way – they're all in code bases maintained by different groups of people who have no incentive to cooperate on issues like this. So it's quite likely that I'd still have needed some sort of macro-based parametrisation at the call site, even if it was less overwhelming than what I've got here.
(And yes, I know that C# isn't suitable for all sorts of things.)
http://www.mightyware.com/cpp_vs_csharp_arrays.bhs
Which is why I like functional programming so much.
;-)
Or heck, I’ll throw Forth into the ring too. =)
As I said below, the C++ feature that's actually useful here is generic programming and concept conformance. (Function overloading is indispensable to implementation of the forthcoming C++0x idiom.) Nothing about the idiom there (pedantry: except using ++i to increment the iterator and i==j to compare, rather than inc(i) and equal(i,j)) uses object-orientation at all.
Also, by convention, if you have a container c, you expect c.begin() and c.end() to give you, respectively, an iterator pointing at the first item in the container and an iterator pointing immediately beyond the last item.
This latter convention is being firmly embedded in the C++0x standard that's due out any day now: when someone says for (int &x: myContainer) that is shorthand expressing a for loop between myContainer.begin() and myContainer.end(). (It doesn't actually care what the type returned by those functions is, provided thy both return the same type and it can be incremented, compared and dereferenced.)
This is achieved by container authors implementing iterators for the container types they create. Indeed, in most cases, creating the iterators is the very meat of container implementation and much else gets expressed in terms of them, at least implicitly.
As mentioned, iterators don't exhibit an interface in the Java sense: there's no run-time polymorphism. An iterator is, broadly, any type for which you can compare values for equality, increment values and dereference values (i.e. apply prefix * to them). Given those features, you can write generic code that works on any kind of iterator. (In reality that's approximately the input iterator concept — there are other concepts both more and less stringent, as well as regrettable gotchas, but the power of the system more than compensates in practice.)
Unfortunately, one of the wrinkles is the key distinction between an input iterator and a forward iterator: you can copy a forward iterator and use the copy later to make a second pass through the data, whereas an input iterator is once-only (compare traversing a linked list with reading lines from a TCP socket). This distinction between contexts can't be directly enforced by the compiler. There is an iterator_category mechanism to get around the problem, but it's clunky.
There is also a proposal to extend the language with explicit concepts, but it's typical Stroustrup filth and was rightly rejected from C++0x. In due course, someone will come up with something nice to replace it, I hope.