On 10/31/06, Martin Knoblauch Revuelta <mkrevuelta@gmail.com> wrote:
The width is based on the same concept as count, but they are not related at all. Note that W might be float, for example.
I might deduce m_total_width from m_node_width by recursing through the whole subtree every time. Obviously, this would spoil the whole thing.
I don't entirely understand the benifit of your 'non-proportional sequence view'. What use cases can you think of where this would be beneficial to client code? Right now it seems like it adds unjustified bloat to the library.
* I get the impression that there's is way more code than needed to implement this data structure.
I'm trying to refactorize some things, but it's a large interface... ;-)
Large interface == monolithic design. As much as possible, I would try to stick to just implementing member functions that are already member functions of other container types. Everything else should be a free function, perhaps in an optional utility header of some kind.
* Not sure why you would want the various unsigned/int/long vs size_type variations of methods. Having those extra methods just confuses the interface for users and introduces extra use cases to account for in the implementation.
It helps avoiding ambiguities when T is an unsigned/int/long. This is how other container implementations solve it.
What ambiguities? Implicit conversions exist between built in types, so if there is no algorithmic difference I don't understand this justification.
and keeping exceptions in mind you do a swap in between :-)
Exceptions? Swap?
He is referring to a pattern where you would create a temporary <sequence name here> object, build up that object, and then swap the two sequences (just swap their root pointer values). This would ensure that if you can't finish building the tree then the nodes you added will be released automatically. Essentially, commit/rollback without a try/catch.
* You have a variety of C style casts, and you happen to be casting "this". That's frowned upon, and truthfully I can't see why you do it.
I'll change them to C++ casts.
With this trick, neither iterators nor tree nodes need to contain a pointer to the avl_array object where they "belong", while the interface allows working with iterators without requiring references to the corresponding avl_array objects.
I would say that slightly more space overhead would be preferable to tricky and less straight forward code. Although I'm not sure why either the nodes or the iterators should be aware of the container they are a part of to begin with.
* Algorithms rarely have a place in STL containers. You might want to move the various binary_search, sort, etc. methods to functions. Preferably having them use the same interface as the STD versions.
I'll study this too.
One of the most important features of the stl is that it separates algorithms from the container types they operate on. Most of these algorithms already exist in the stl. What is your justification that they need to be overridden for your container in the first place?
* I would make the value sorted aspect a separate container, possibly as an adaptor to the rank container but possibly also some other form of tree. Sorted ordering is orthogonal to rank statistics.
Why? I wouldn't like to restrict the hybrid use of a container object. I mean, using it as a sorted container for a while, then using it as unsorted for a while, then sorting it again, maybe with a different criterion, and so on... Note that iterators would remain valid through the whole process...
Because it desimplifies the interface, causing bloat and making client code potentially pay for features it doesn't want/need. I would prefer a separate container type (perhaps priority_<sequence_name_here>) which would behave more like a stack or queue. It could allow pushing and popping values into sorted order and forbid arbitrary location inserts by the user. Supporting both random location inserts by the user and sorted inserts doesn't make sense. The container no longer has control over its invariants. -Jason