Most collection classes easily support iterators; Wil uses an api imitating STL style iterators to avoid new unique api documentation. It's much better to use an api familiar to others. Api novelty is a headache, and thus only pursued given cause. (Because Wil aims for better memory allocation style, it's often impetus for api novelty. But it rarely applies to iterators.)
Wil typically limits his use of iterators to refactoring; given code written first in STL under investigation for improvement, Wil writes replacements with identical interfaces so one or another can be chosen by compiler switch, permitting QA comparisons in testing. The old version of code must often be maintained a while because any odd behavior is blamed on the last interesting change. In response Wil can revert his code with a switch to show odd behavior is present in the old code as well.
(The winner in any context is chosen by actual empirical performance measured with profiling and instrumentation. In day jobs, Wil never rewrites code in pursuit of style or philosophy. Only results matter, and the fittest code wins.)
Although STL classes and iterators have extensive interfaces — especially when they interact with generic algorithms — the actual api used in the wild is often a tiny subset of entire iterator apis. Most often Wil sees code like this:
To replace code like this, Wil only codes methods and operators actually used: a trivially small set of methods.
In addition, occasionally an erase removes elements being iterated, and this adds a bit more complexity. At least one example of erase will be shown in classes on this page. But otherwise it won't be added as distracting complexity.
Warning: this demo isn't very interesting. It's essentially just about syntax — appearing late in a list of things that matter. You can summarize all this demo as: how to make iterators look uniform using STL style names and C++ operators.
However, once you know how one iterator is written, you're most of the way to grasping them all. If you're bored at the end of this demo, you received the message perfectly.
Most iterators on this page are for queue classes in the list demo; so a lot of the code is really an extension of the list api shown there. (Iterators for hashmaps in a future map demo are similar in nature to queue iterators, so when map iterators are added later, far less code will be shown for them.)
Here's the forward iterator for yq which is created by yq::qbegin() which passes the first yqe element to the constructor (cf «).
This iterator simply points to the current elem in the queue's list. When p_e becomes the queue's sentinel element, the iteration is done and operator!=() is false.
In normal use, the yqe passed for comparison is the q_e sentinel elem in yq (cf «).
Since elem pointer yqe* must normally be cast to a subclass type, the pointer returned by the last operator above is more useful than operator*() just below:
Decrement operators are supported to reverse direction of iteration. But this just showing off since the same sort of thing doesn't apply to all collections.
Sample code showing yqp in use appears further below.
The yqp forward iterator shown above doesn't support erasing (that is, removing) the current elem in the iteration.
So the yqpp alternative forward iterator below shows how yqp can be upgraded to remove elements. Wil hopes seeing both versions of the iterator shows you how easy it is to adjust an iterator for additional features.
New member p_n is the next element in the iteration, and it's simply a copy of the current elem's next pointer (p_e->e_n) so current elem p_e can be removed using perase() without disturbing forward progress.
Because no begin() creates yqpp, the first constructor below can be used to make an iterator for a specific yq:
Other than the constructor which populates p_n with the next elem, most of yqpp looks just like yqp, except for the increment operator, which uses and updates next elem p_n:
Last method perase() above is the reason yqpp exists: to support elem removal during iteration. It merely asks the element to remove itself, and this works because the rest of yqpp took care not to depend on the current value of p_e.
(Note because yq queues do no memory management, neither do yqpp iterators. So if a removed elem needs deallocation, this is something the user of yqpp must do. Removing an elem from a queue does nothing but unlink it from the list.)
Once again, yqpp sample code appears further below, along with samples for yqp and reverse iterator yrqp shown next.
The yrqp reverse iterator for yq starts with the last element and iterates backward until it stops at the front.
Note yrqp looks just like yqp but with next pointers swapped with previous pointers, front swapped with back, etc. etc. In short, it's shown only to reveal how much it really looks like yqp. So almost no commentary will appear, since it would be the same as that for yqp, but with directions reversed.
Erasing elements is also not supported in yrqp, but — as an exercise for the reader — it should be trivial to rewrite alternate yqpp shown in the last section so it iterates in reverse and can erase the current elem.
An instance of yrqp is returned by yq::qrbegin(), and you compare it to the value returned by yq::qrend() to see when the iteration is done (cf «).
The yqe32 test element below is an extremely simple yqe subclass in terms of state: it's just a e_val integer with associated magic signature in member e_tag. The integer value makes an element easy to print; the tag makes it easy to assert dynamic casting from yqe* to yqe32* is a success.
The following boilerplate print methods and operator<<() inlines are described in the out and quote demos.
The point of yqe32 is to make stack or heap elements added to a yq queue whose contents are easily printed since elements are printable. (This is the same point of test element yti32x in template queues shown column right: cf »).
The dump and cite formats are gratuitously different: pseudo XML when dumping and brevity when citing.
You can push instances of yqe32 in list ye32l shown next.
Class ye32l ends with l for list and contains a yq of yqe32 elements, which are printed using the same boilerplate print methods used by yqe32.
Note the use of separation of concerns: yq only knows the elements are type yqe, but list ye32l knows the elements are yqe32 and can be printed as such. (This is construction by composition instead of by inheritance.)
Note list ye32l has no idea how elements are allocated; so it defers memory management to the user of ye32l: freedom of choice with responsibility to manage well.
We have the same boilerplate print methods and operator<<() inlines as elems yqe32 (cf out and quote demos):
We have the same boilerplate print methods and operator<<() inlines as elems yqe32 (cf out and quote demos):
And the following operator<<() is just shorthand for qpush_back(). Note this pushes — not a copy — but the actual argument elem into the queue by pointer. (So if the element is on the stack, then the queue points at exactly that instance on the stack; this is not like STL which copies by value.)
The list's print methods below use a yqp forward iterator returned by yq::qbegin() pointing at the first queue element (cf «). No option to iterate backward is offered here — a reverse iterator sample looks like this one further below (cf »).
Try links in the code if you want to see exactly what's invoked by various operators used above.
Class ye32rl ends with rl for reverse list and contains a yq of yqe32 elements, which are printed in reverse order compared to ye32l by means of using reverse iterator yrqp.
Because most of this code looks just like ye32l in the last section, almost no commentary is added. Only the use of yrqp reverse iterators makes printing code different: elements print starting with the last element working backwards.
Once again, these print methods only differ from ye32l methods by using reverse iterator yrqp (instead of yqp) returned by method yq::qrbegin() describing the last queue element (cf «).
Sample code below mixes both forward list ye32l and reverse list ye32rl. So in this particular example, each sort of list only iterates in one direction when printing. (Compare this to template sample code shown column right which can iterate forwards or backwards by setting a member variable.)
Class ye32l ends with l for list and contains a yq of yqe32 elements, which are printed using the same boilerplate print methods used by yqe32.
forward «
Let's see some examples: note output on stdout appears in a separate color. Here we print an empty list, then append one element and print again:
Because we used ye32l::quote() both places above, dump format shows the first element in pseudo XML format:
Now we append two more elements and print them using cite format. This bears repeating: all the elements are added by reference — they're not copied by value.
Cited elements appear as integers followed by a space:
Instead of appending again, we push the last element on the front for variety:
Which of course looks like this when the list is cited:
backward «
Here's the same sample code with reverse list ye32rl substituted so elements are iterated in reverse order:
With fewer than two elements, no order is apparent:
But with two or more elements, you can see reverse order:
Pushing a new element first causes it to display last:
Did you notice we created all new elements to add to the reverse list? That's because the original elements cannot be added to a new list because they are still inside the first list. Any yqe element is member of at most one queue at once.
updating «
We can update the elements while iterating with yqp. Let's go back to the forward list and add 100 to the value of every element with an odd value. First let's append two more elements, so the list contains more odd values:
So the list is now longer:
This update operation demonstrates e is actually in the list, and not just a copy of the list element. After we change each element with an odd value, the new value is in the list:
erasure «
Now let's demonstrate element erasure while iterating with alternative forward iterator yqpp shown earlier (cf «). Using the same forward ye32l list, which still has the elements we pushed earlier, with 100 added to each odd element, let's start by appending two more elements:
Now using the same sort of loop shown while updating, we find each odd element once again, only this time we remove odd values while iterating, via yqpp::perase():
Afterward only even elements remain:
thorn: todo, names, fd, iovec, assert, log, run, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob, tree, slice, rand, time, stat, hash, heap, node, primes, page, book, pile, stack, atomic, lock, mutex, thread, map, meter, list, iter « Þ, ctype
(mu: toy, peg, imm, tag, box, symbol, token, number, bigint, class, method, reader, writer, eval, env, vm, gc, world, pcode, compiler, asm, lathe, lisp, smalltalk, design, weight, jar, card, harp, debug, profile)
Some demos are stubs: todo is a demo guide. See toy for mu updates on language pages; names introduces naming schemes.
Names of iterators in þ usually end with p for pointer because iterators point at a collection element, one element at a time. Where STL would use iterator in a class name, Wil just uses p.
Similarly, where STL uses const in a class name, Wil just uses k, and where STL uses reverse, Wil uses r.
For example, yrqp means thorn reverse queue pointer: the reverse iterator for primitive queue class yq in the list demo (cf «). Sometimes Wil adds typedefs to create long STL type synonyms:
Then you can write yq::reverse_iterator instead of yrqp if you prefer verbosity. Wil only prefers this when replacing existing verbose code with new code using an identical api.
The api for iterators has a common structure and syntax. Each collection has begin() and end() methods returning an iterator and some value which can be compared to an iterator to see if iteration is done. Wil usually writes end() so it returns a unique token, like (y0x*)0, understood as meaning "end of iteration."
(Wil's queue iterators have unusual end() methods because they return a pointer to the queue's sentinel element, so end actually has a value instead being a nominal constant.)
Most iterators generally need the following methods:
- constructor - for use by a collection's begin()
- empty constructor - to declare an iterator instance var
- assignment - so you can assign the value of begin()
- operator!=() - for comparison to collection end
- operator==() - testing equality to collection end
- operator elem*() const - convert to an elem pointer
- elem& operator*() const - convert to elem reference
- iter& operator++() - pre-increment to next element
In addition to the minimum set of methods above, Wil sometimes adds a few more — typically to be slightly more complete.
- iter& operator--() - pre-decrement to previous elem
The decrement operator lets you visit elems backward in the middle instead of advancing forward. (This probably isn't a good idea. But it was trivial in the case of iterating double-ended queues, so Wil thought it might be informative.)
- iter& operator++(int) - post-increment advance
Post-increment is not a good idea because it's inefficient if you really want the original value before increment returned as a side effect. So Wil usually has post-increment do exactly the same thing as pre-increment, with a comment warning you about that.
When Wil writes post-increment and post-decrement operators so they correctly (but inefficiently) return the last iterator state, the only reason to provide them is to show it can be done. But you are strongly encouraged not to use postfix operators to increment or decrement iterators. (In day jobs, Wil makes postfix operators do the same thing as prefix operators to avoid punishing innocent usage.)
The run demo shows an iterator for subsequences in yv runs separated by a given octet value. The iterator is named yv::Vp (cf «) and the sample code for that class is the following:
Here's the resulting output of this code:
Relevant parts of the run demo give more explanation.
Below Wil shows iterators for template queue class yqt<T>, and these include const iterators (with a k for const in their names) unlike the non-template iterators shown in the left column.
Const templates are trivial in the sense you can always make a const iterator by taking a non-const iterator, then remove any method that would modify the collection. Wil only bothers for template queue iterators because folks familiar with STL might expect const iterators, even though they are trivial in nature. (They chew up a lot of vertical text space unnecessarily, though. Perhaps only a forward const iterator will be shown, since a reverse const iterator is so easy to do.)
Note: the this keyword is used a lot in these template inlines in a manner you would think is unnecessary. However, when templates subclass one another, ambiguity creeps in very quickly, and sometimes only explicit this->foo works when you think foo is enough. If it helps, just pretend each this-> qualification is not there.
The first yqtp0 class shown is the base class of all iterators for yqt<T> — forward, reverse, const, or whatever. It defines the methods in common to all the subclasses, to reduce the total number of lines that would appear to define identical comparison operators several times. The name yqtp0 means thorn queue template pointer origin where the 0 suffix means origin because zero is the origin on the number line.
This last operator!=() is used most often:
Getters pe() and const kpe() are the preferred shorthand ways to convert an iterator to an element pointer:
Note the typedef for e_t which defines it as synonymous with template queue element yqte<T> from the list demo (cf «). All the iterators have a similar typedef, so everywhere you see e_t, just remember it means element type and is identical to yqte<T>:
Note member variable e_t inside yqte has the same name as typedef e_t in the iterators. This might be confusing, but context will make it clear which is meant: e_t the value or e_t the type of the queue elem containing that value.
The first iterator class yqtp is the forward iterator returned by yqt::qbegin() (cf «). This class looks extremely similar to yqp (cf «), and to make it support erase during iteration would require making the same changes shown in yqpp (cf «).
The next iterator class ykqtp is the const forward iterator returned yqt::qbegin() const (cf «). The same comments about the non-const ykqtp iterator apply to this one, and to the following reverse iterator yrqtp: they all look like yqp and yrqp (cf « and «) and adding an erase method would resemble the way it's done in yqpp (cf «). The only reason why Wil doesn't present non-const iterators with erase is because they would look even more complex.
Finally, here's the reverse iterator which starts with the last element and works backward from there to the front:
We ought to skip the const reverse iterator for brevity. But it was used in the sample code shown below, so let's include it here:
Sample code for iterators in the last section is situated in printing code for a list class with template queue yqt embedded inside as a member variable. This allows us to implement a less complex api on the container class, instead of directly on the yqt template, shudder.
(This sample resembles the same code shown column left to print an embedded yq using yqp and yrqp to iterate elems being printed.)
Struct yti32x is a tagged int32 example, and provides a type T for use in specializing yqt<T>. It's really just a single 32-bit int with an extra 32-bits of tag which must equal magic number 0x74693332. This gives us something to assert to check whether values in a yqt<T> instance look valid. Most of the yti32x api is for printing.
Integer x_val is the example value for this elem, and x_tag is asserted to have the expected magic signature whenever x_val is read or written — it's just aggressive dynamic type checking.
The rest of the api is for printing, so the demo's sample code can display changes in lists of this element value.
The printing style and boilerplate operator<<() inlines are described in the out and quote demos.
Printing methods for yti32x elems merely show the value in one format or another. The cite format includes a comma afterward for output contrasting with non-template demos on this page.
List class yti32xl below is just a list of yti32x elements — the l suffix here means list; it's a wrapper for a yqt<yti32x> named l_q which adds printing methods and a boolean l_reverse indication of which way to iterate when printing. (So it's the printing methods where the template iterators will be demonstrated.)
The following operator<<() appends a copy of a new yti32x element to list l_q — just shorthand for qpush_back().
Operators above are the usual boilerplate to invoke printing with operator<<() using out stream yo (cf «).
The implementations below use the iterators. Note the use of links to connect each operator and method to the implementation invoked by this code. (Note the one char const T& operator*() is a link too.)
The cite method below invokes exactly the same iterator methods as dump — the only thing different is invoking cite on the elements instead of dump. (Note the heavy use of links.)
The next section tests iterators in printing methods above.
This section builds a yqt template queue from the list demo (cf «) using list yti32xl from last section's sample code above (cf «). Because yqt allocates elements using yH from the heap demo, a special subclass of yH named yxHH is used from the heap demo sample code to show the cumulative heap state over time (cf «). The yxHH heap subclass was actually written specifically for this demo, to show the effects of heap allocation using a template-based list queue.
Since this is apt to be a wee bit confusing, the example below shows output on stdout using a different color: mainly green as opposed to red. (If you're red/green color blind, please accept my apology.)
The code above writes the following on stdout when the yxHH singleton heap g_1xHH starts out empty.
The next bit of code appends two more elements, then reverses iteration print order before printing the list and the heap again:
Next the head and tail of the list are first read, then popped. Then the list and heap are printed again after first making iteration print order forward again:
Finally, the list is cleared to empty, which deletes all list elements, as can be seen when the heap prints final statistics.
Among other things, the following output on stdout shows correct iteration when the template queue is empty.
"Why do you think of iterators as pointers?" asked Dex with a mildly peeved expression. Wil supposed Dex was being overly literal again.
"Wasn't my idea," Wil quipped. "You can find comparisons of iterators to pointers elsewhere."
"Then why do you encourage it?" whined Dex. "You make pointers more confusing when you apply the term to iterators."
"I'm not sure I agree," Wil considered. "I think most folks hope iterators are somehow magical when they're not."
"They are magical," Dex joked with a gleam in his eye. "It's sacrilege to write iterators of your own. Only priests can do that."
Wil rolled his eyes. "You know telling me I can't do something gets me worked up," Wil warned. "Don't play with me."
"I doubt you even understand what pointers really are," Dex elaborated. "Most people suck at pointers."
"I don't think I really understood them until around 1983 or so," Wil admitted. "It was the copy of K&R C I bought in December 1982 that opened my eyes."
"Read a book once, did you?" Dex teased.
"I read the chapter on pointers and arrays six times," Wil marveled, "and each time I pieced together a little more."
"Six times?" Dex asked in surprise. "I thought you had a photographic memory. Now I see you're a loser."
"If you don't quite get something," Wil explained, "you can't memorize it. Or at least I can't. My memory now isn't much better than yours — except I needn't believe a thing is true for recall."
"How does your learning disability relate to iterators?" Dex asked.
"I thought getting pointers completely after a week or two was pretty good," Wil apologized with his eyes for self congratulation. "I only knew Basic, Fortran, and Pascal before I learned C, which I liked enormously more than Pascal."
Dex clapped his hands. "Focus, Wil," Dex urged. "Forget memory lane and tell me about iterators."
"Iterators obfuscate implementation details," Wil responded. "That's the purpose of uniform api: make different things look the same."
"What's the problem with that?" Dex defended.
"Depends on whether you need to know what's happening," Wil began. "Not knowing can make you accidentally waste cycles doing something inefficient. Not that you ever would, right Dex?"
Dex crafted an expression suggesting he had no idea, but actually conveying the opposite — Dex's idea of funny.
"I think it hides detail from other folks," Wil explained, "when sometimes they need to know. If iteration without an iterator is just as clear, then I think direct api use is better."
"Any exceptions off the top of your head?" Dex prompted.
"Most hashmaps are more easily visited using an iterator," Wil replied instantly. "Hashmap structure confuses most folks, so using an iterator makes it clear what you're doing."
"Why haven't you posted map iterators yet then?" Dex accused.
"Busy," Wil glowered. "But I'll put some up within a few months. Probing closed-hash maps are somewhat easy to iterate. But chaining open-hash maps are slightly gnarly to visit without an iterator, especially when supporting removal during iteration."
"I want to see the template-based hashmap," Dex urged.
"I'm not surprised," Wil nodded. "But I'd like to work out a version less like typical monolithic hashmaps using large swaths of contiguous memory. I think hashmaps layered on books are better."
"Books? What?" Dex grimaced. "I hate when you coin terms."
"A book is a super-page," Wil defined. "Say around 64K or 128K in size, and aligned to an address at a multiple of the size."
"Part of anti memory fragmentation regimen?" Dex guessed.
"Yes, a big hashmap can be composed of some N books," Wil agreed. "It needn't be all in one contiguous chunk."
"Except contiguous is simpler," Dex asserted. "Do you love compexity?"
"No, I just hate fragmentation," Wil replied. "And besides, I want to garbage collect hashmaps in book oriented address spaces. Might as well do the same thing in C++ classes."
All this code is available only under the BriarPig mu-babel license described fully on the rights page. You do not have permission to reprint this page in any way. Neither feeds nor repackaging is allowed. You can link this page if you want folks to read it.
demos « Þ
+ todo
+ names
+ fd
+ iovec
+ assert
+ log
+ run
+ hex
+ crc
+ buf
+ in
+ out
+ quote
+ escape
+ compare
+ file
+ deck
+ cow
+ arc
+ blob
+ tree
+ slice
+ rand
+ time
+ stat
+ hash
+ heap
+ node
+ primes
+ page
+ book
+ pile
+ stack
+ atomic
+ lock
+ mutex
+ thread
+ map
+ meter
+ list
+ iter « Þ
+ ctype