Summary
The growable array I posted about two days ago has evolved into a full-featured stack template class with more features, more tests, better performance and contract verification.
Advertisement
The performance of the OOTL stack class has improved significantly with the use of std::allocator, and the addition of contract verification. The latest version is at OOTL.org.
Here are some benchmark results for containers of 12.8 million elements:
To summarize the results, vectors are slow at individual element growth using the push_back() member function, sometimes more than 3x than the stack. The variation depends on how expensive copy operations are. An extremely expensive copy operation will cause the vector to suffer greatly. The other thing I want you to notice is that deques are very very bad at indexing, 6x as slow as the stack! The difference between fixed_stack and grown_stack is due to the fact that if initialized with a specific size the data structure allocates a single large initial buffer, rather than needing to create a long doubling list.
As I mentioned previously the data structure used, is a "reverse doubling list" (does anyone know if this exist under a prior name?) which is a linked list of arrays each one twice the size as the next. Lookups take an average constant time in this data structure, with a worst case of O(Log N).
The recent versions uses the latest techniques I've developed for programming with contracts, which are more effective previous incarnations. Here is what the contract verification class looks like:
The reason it is so great to have the contract separated like this is for two main reasons:
the contract is separated into a logical and cohesive unit which is easier to read and understand, and can serve as a standalone description of the implementation class.
the logic of the implementation remains unaffected by the verification of preconditions and postconditions
To understand the significance of number 2 consider the pop() function. Traditional programming techniques would have preconditions and postconditions checked directly within the function implementation. For instance, the pop() function would have to be written as:
void pop() {
int old = inh::count();
assert(!inh::is_empty());
...
assert(count() == old - 1);
}
But the problem with this approach is that during release builds there remains a superflous variable declaration and a superflous call to count(). In this trivial example the compiler might be able to optimize the calls away, but in other less trivial cases it won't be able to do so. By separating the entire contract verification into a separate class, all of the logic is applied (or not) depending on the _NDEBUG macro.
I hope some of this code I am developing is useful, the download is public domain, so you can use it to your heart's content. If you need help with it, let me know.
Previous Topic
