What's the actual reasoning behind iterator categorization in STL?

onehundredquestions guy 0
Viewed 48

For reasons of efficiency it's not possible to have every container work with every generic algorithm -- STL Tutorial and Reference Guide.

So i'm learning about STL and i was reading the mentioned book and trying simultaneously to see the justification behind this categorization of iterators, the book doesn't actually go beyond the quotes in explaining the why behind this categorization.

I understand that some generic algorithms requires certain abilities from their containers (for example random access for sort algorithms) so clearly not all containers can be all plugged in all generic algorithms for efficiency reasoning.

but this answer isn't much sufficient and it seems to me like it's only one aspect of this decision design, before reading the section i thought about the categorization as more of a safety belt (because of the naming...) but this aspect is not even mentioned in the book, all in all the book doesn't go much in details about this design decision ,if you can, could you please go in much detail about the why behind this ?

stl iterator containers c++
1 Answers

The justification for the categorization of iterators is that they are useful. The categories are not restrictions or "safety", not limitations on what can be. They are descriptions and an organization of what exists. Algorithms first, iterator categories second.

If someone creates a new container, the iterator of that container can be analyzed to see in which categories it fits. That is enough to know which algorithms will work with the new container. There is no need to analyze each algorithm individually.

For example, a "for_each" algorithm requires an "input iterator". If the iterator of the hypothetical new container is an input iterator, then "for_each" can be used with that container. There is no need for the documentation of the new container to acknowledge the existence of "for_each", much less analyze the algorithm to see if it works. The container documentation merely has to state that the iterator is an input iterator, and users may deduce that "for_each" can be used with the container.

Why does "for_each" require an input iterator? Because the algorithm needs to make a single pass of the container and extract values from the container. That functionality is guaranteed by an input iterator, and not guaranteed by more basic iterator categories. It is unlikely that someone started implementing "for_each" by saying "assume an input iterator". Rather, the starting point should have been the needed functionality. After the initial implementation, there should have been an optimization pass. After the implementation was finalized, it could be analyzed and then the iterator requirement established – at the end, not the beginning.

Similarly, does the new container work with searching? There is no need to analyze the search algorithm, only to look up that searching requires a forward iterator. If the new iterators are forward iterators, then the search algorithm can be used with the new container. Otherwise, it cannot.

The result is a simpler experience for documentation writing because the number of iterator types is much smaller than the number of algorithms that exist or will be created in the future. Documenting which iterator types are supported is simpler and more modular than creating a list of supported algorithms.

JaMiT0
Related