Suggestions for chapters 8 and 9

[aharrison24]

Chapters 8 and 9 introduce list_pool and list_pool_iterator. A few things confused me while I read those chapters. I've listed them here in case they are useful:

Examples of using the list_pool class

list_pool has an unusual API compared to what we're used to from the STL. It was not immediately obvious to me how I was supposed to use it. I eventually discovered test_merge_sort.cpp which generates a list via the push methods on the iterator. But there are no examples of how to use the most important member functions of list_pool. And I wasn't expecting to need to read test_merge_sort.cpp when I was only on Chapter 8.

Perhaps it would help to give some brief examples in the chapters themselves? It's difficult to come up with concise examples, as the API seems to be designed to be used mostly via algorithms like generate_list. Here's my best stab at code using the list_pool API directly.

Chapter 8

This uses the queue operations. Without them I guess you have to keep calling allocate, which is probably a bit too low level.

list_pool<char> pool;
list_pool<char>::pair_type q = pool.empty_queue();

// push_xxx does mutate the pool, but not the queue. So you must
// remember to update the queue object yourself.
q = pool.push_back(q, 'c');
q = pool.push_back(q, 'd');
q = pool.push_back(q, 'e');
q = pool.push_front(q, 'b');
q = pool.push_front(q, 'a');
q = pool.push_back(q, 'f');

// If you want to print the list without using the list_iterator then I think this is
// the only way? But at least it demonstrates how to use `value` and `next`.
list_pool<char>::list_type node = q.first;
while (node != pool.end()) {
    std::cout << pool.value(node) << " ";
    node = pool.next(node);
}

free_list(pool, q.first);

Chapter 9

Using iterators to populate and print a list. Using push_back is more challenging, as you need to increment the insertion point each time, which gets messy. It's much neater to use something like the generate_list function from list_algorithm.h.

    list_pool<char> pool;

    list_pool<char>::iterator nil = list_pool<char>::iterator(pool);
    list_pool<char>::iterator list = nil;

    push_front(list, 'd');
    push_front(list, 'c');
    push_front(list, 'b');
    push_front(list, 'a');

    std::copy(list, nil, std::ostream_iterator<char>(std::cout, " "));

Why there is no pop_back

The list_pool API contains push_front and push_back, but only pop_front and not pop_back. That lack of symmetry seemed odd until I realised that you can't implement pop_back efficiently for a singly-linked list. A note to that effect might be worthwhile somewhere in Chapter 8?

pop_front does not free the removed elements

I'm still not sure whether that's a bug or whether it is by design. I suppose it means you end up with two lists sharing a common tail sequence, assuming you kept hold of your original head node. This isn't really something actionable in the write-up, but it is a thing that still bothers me.

Singly Linked List Iterator concept

I find this concept unsettling. I've not come across iterators that mutate the structure of the underlying data structure before (have I?). These iterators do a lot more than act as 'coordinates'!

The fact that the push_front and push_back friend functions inside list_pool_iterator.h return void even though they allocate new nodes is also odd. As it stands, push_front mutates the iterator, but push_back does not. I'd think it would be more useful for both of them to return an iterator to the newly created node or something. That would make them a little easier to hold correctly, and make the generate_list function easier to write.

But who am I to doubt Alex Stepanov? Would be interested to hear your thoughts on why it's designed this way.

[justinmeiners]

These are helpful comments. Since I am familiar with Lisp, these didn't catch me off guard. Here are some immediate responses. I will have to consider them more carefully when I actually make changes.

Perhaps it would help to give some brief examples in the chapters themselves?

I think a good start would be adding a file test_list_pool.cpp which assembles some basic "a, b, c" or "1, 2, 3" lists as you have shown. This can be added to the code for chapter 8. Then perhaps adding a footnote or something similar to show this usage could be a good thing.

It is traditional in lisp books to start constructing lists with the equivalent of alloc.

This uses the queue operations.

Another nice thing about the pool class, is you only need to free stuff if you plan on reusing nodes. You can of course just wait for the pool to go out of scope.

as you need to increment the insertion point each time, which gets messy

Yes, lisp lists work best by appending to the front. One way to avoid the mess is to append everything to the front and then reverse, although the reverse is probably written in a later chapter.

That lack of symmetry seemed odd until I realised that you can't implement pop_back efficiently for a singly-linked list. A note to that effect might be worthwhile somewhere in Chapter 8?

Will do.

I suppose it means you end up with two lists sharing a common tail sequence.

Absolutely. It's actually an idea similar to "copy on write" optimization. You can have several lists which share parts of each other, as long as they don't start making modifications.

However, since this section is explicitly using list pool to implement queues (queues being a distinct data structure) it may make sense to make pop_back do a free. I might leave it to a footnote though. But who am I to doubt Alex Stepanov? Would be interested to hear your thoughts on why it's designed this way.

I've not come across iterators that mutate the structure of the underlying data structure before (have I?). These iterators do a lot more than act as 'coordinates'!

Hmm, I would not consider it different than modifying the value pointed to by a pointer. Pointers point to a value, you can modify it. Linked iterators point to a value, and a next. You can modify both.

I think you are correct that there aren't others in the standard library (besides pointer like things). They are in "Elements of Programming". Alex makes a big deal about how we should invent lots of new iterator types are people are afraid to. See:

https://justinmeiners.github.io/efficient-programming-with-components/12_merge_sort.html#Kinds-of-iterators

But who am I to doubt Alex Stepanov? Would be interested to hear your thoughts on why it's designed this way.

You might be on to something with returning something other than void. In the course his students sometimes find ways to improve things and he agrees, so don't assume something like that is carved in stone. Perhaps one reason is other push_back functions in the STL return void.

[justinmeiners]

I think PR #40 is how I want to address these. Anything I missed?

[aharrison24]

I've come across cons before in Haskell, so that wasn't a completely new idea to me. I think a large part of my confusion here was that there are actually three separate APIs for interacting with list nodes in list_pool. I wasn't sure whether they really were completely separate, or whether it would be necessary to mix-and-match between them. I think some short code samples will help a lot with that.

Thanks for trying to address my vaguely specified set of discomforts with the text. I'll go and have a look at the PR.

[justinmeiners]

I actually realized I couldn't find push_back, etc for iterators anywhere in the text. I'm going to do some more careful grepping, but it's very possible that is added much later, or outside the class. Either way, I think I need to modify test_list_pool_iterator.cpp.

[aharrison24]

Good point. I had meant to say something about the exercise at the bottom of chapter 9. It's a pretty loose description of what the reader needs to do. I think at the very least it ought to name the member functions that need to be implemented, to narrow the scope of possibilities a bit.

But yeah, a section about the Linked Iterator concept would probably be helpful. Perhaps it's better not done as an exercise, as it's a slightly non-obvious use for an iterator (as we've discussed elsewhere)?