Summary: Let's rewrite these stuff in C++!
The great strength of the STL is the ease with which one can experiment with different data structures. Modify the C++ version of Markov to use various structures to represent the prefix, suffix list, and state table. How does performance change for the different structures?
Answer: Changes applied in this commit.
The diff is very small, since we only reference these types once or twice. TODO: measure performance between the two versions.
Write a C++ version that uses only classes and the string data type, but no other advanced library facilities.
Compare it in style and speed to the STL versions.
Answer: I approached this incrementally, doing it type by type. The changes are part of the following commits:
Suffixes-std::vector<std::string>toclass Suffixesthat uses a Linked list under the hood -#bd84f3eState-std::map<Prefix, Suffixes>toclass StateMapthat uses a hash map under the hood -#e84ba3dPrefix-std::deque<std::string>toclass Prefixthat uses a simple array under the hood -#57f3f73
The first one was easy, the other two took more time, because there were more work that needed to be done for them. The solution is really close to the C one, with the only difference that the details are encapsulated, behind the hoods of the classes. But they are still there and the developers need to care for them. In terms of the actual implementation that uses these structs and classes - not much changed, because I kept the contracts more or less the same.
Although it was fun implementing this stuff and hitting all the obstacles, in an actual world situation I would rarely choose the custom implementations over the library ones.