justinmeiners / efficient-programming-with-components

Course notes for Alexander Stepanov's teachings on design and usage of C++ STL.
https://www.jmeiners.com/efficient-programming-with-components/
74 stars 6 forks source link

Include simple example of binary counter #48

Closed justinmeiners closed 2 years ago

justinmeiners commented 2 years ago

I also think it would be very valuable to have a slightly extended example of how the counter works, where multiple elements are inserted. You could do an example where the elements are characters and the binary operator is min, for instance. 'zero' could be a space character. You could push in 8 letters in an order that causes multiple slots to be occupied at the end. You can use that to show that the counter only needs log2(8) = 3 slots. You can also show that after all the elements have been inserted, the job isn't yet finished. This justifies the need for the reduce_counter operation, which performs all the remaining comparisons to get to a single 'winner'. I think that's important, because with the text as it is currently, the reduction step is never really justified. It's just presented as something that is necessary.