Software Development

As you may or may not know, I've been implementing my own containers that work as closely as possible to existing STL containers and am learning a lot in the process. Difference with my containers is that they have different performance and often have a combination of functionality from various existing STL containers. For example, an AutoSkipList acts like a set and a vector all at the same time. It's a sorted list and when you insert an item, you get an iterator that also has its index within that list. From then on, you can perform actions from both a set and vector container. For example, you can use arbitrary access and you can use find().

Ok, so I'm going through the documentation at SGI. The docs are actually pretty good. But I cannot figure out which came first, the documentation or the code. First off, they have performance requirements mixed in with functionality. So if you have a container that can only erase an element in logarithmic time, then it's not an Associative Container (containers that work with keys). A lot of algorithms that work with keys work in logarithmic time, not constant. So unless you can earase an element in constant time, none of the other derived concepts are applicable. You can't say you have a Pair Associative Container (like a map). You can't say you have a Unique Associative Container (where the key must be unique). On and on. All because of one little difference in performance requirement.

OTOH, if performance requirements were separate from the functionality, that would be something else all together. You could select the functionality you want and add your own concepts if you want. And THEN you could match up the performance requirements for your container for each of the concepts you implemented.

I'm finding that writing docs is taking WAY longer than writing the code. What I find strange is that despite my complaints about the way the STL documentation is organized, it's kind of fun to describe what each part of your code does. In fact, it helps make your code more consistent.

So what did I do? I added some of my own concepts. A few of them are overrides. Basically, you can use the standard STL concepts, but if you use an override, it alters the performance requirements even if the original concept specifies a different performance requirement. This effectively separates the performance requirements from the functionality. The performance requirements are no longer requirements, but defaults. You can alter them by stating override concepts.

One example of this is "Associative Container LOGN", a new concept I created. This overrides the performance requirement for erasing an element in the original "Associative Container" concept so that it can be performed in logarithmic time. I can now have a container that is both an Associative Container LOGN and a Pair Associative Container. A Pair Associative Container must have erase element be in constant time, but Associative Container LOGN overrides that and allows the container to perform erase element in logarithmic time. In short, I can now have a map-like container that erases an element in logarithmic time.

Since all my containers are SkipLists, almost everything is done in logarithmic time. Now that I had a way to deal with container performance requirements, iterators became a problem. There are about five different kinds of iterators and the first two aren't very powerful. Of the more powerful ones, they all require constant time movement. Some of my containers are Bidirectional Iterators, but many aren't because these last ones can only move backward in logarithmic time. You can use the container that best suits your needs. If someone seldomly needs to go backwards, this could be the right container because you save memory in exchange for loss in performance, an age old truism of computing.

Then we get to arbitrary access. Random Access Iterator is the only one that has it defined and it MUST be constant time. All my SkipLists that support indexing can do it in logarithmic time. It may not be as fast as a vector, but it's just as fast as a map or set (except that we search via index and not by a key) and those containers are used all the time. In this case, I didn't use overrides, but defined new iterator concepts with different performance requirements. It's weird though because they still need to be defined as random access iterators (or bidirectional iterators) to get the right functionality at the code level even if the performance is different.

I do understand that the STL documentation is there to document what they have. I get that. I just find it really strange that there is ZERO room for expansion. No thought whatsoever has gone into adding more components later on with different performance requirements. I've seen plenty of docs where they reserve this and that for future use. Or they leave a few loose ends that will be used at a later time, etc. None of this stuff changes what you have. But it does let someone know that the future is not an antithesis to your work.

Should documentation follow some of the same rules as programming? Or is this more a reflection of how the code was designed? It's hard to tell. Perhaps it's the fact that they had such an easy way to make it all extensible, docs and code alike, that I'm perplexed at the whole situation.

Anyways, documention is really fun for me once I get set up with the layout, formatting and design that I want to follow. I wish I could say it's similar to blog writing in that I try to explain things in a more understandable fashion, but it's not like that at all. Maybe once or twice for the general explanation how to use the container. But after that, you have to make sure the same comments appear in all the container documentation that have the same methods.

Documentation really is the finishing touch on your code. It makes everything look better and creates a complete package. It takes time, but totally worth it.