Andrey Semashev <andysem <at> mail.ru> writes:
Hello JOAQUIN,
Monday, June 11, 2007, 1:46:53 AM, you wrote:
[...]
It is not exactly like that, if I'm understanding your description correctly. Indices do not hold iterators to some base container, which would be the simplest implementation technique, but they're rather much more tightly coupled to each other internally. For instance, a multi_index_container consisting of N indices holds only one node per element --this node is constructed by metaprogrammatically aggregating in one single struct the N headers for each index. The savings achieved by this technique are calculated at
The inner workings of the indices are also constrained by some internal APIs that must be complied with so that multi_index_containers can assemble and use the indices.
Ok, this makes things more complicated but still possible. I see that the node structure becomes dependant on the index nature and there is no longer "ultimate" begin or end of the container which makes it difficult to clear or destruct it.
However, the implementation does not restrict indices from having their internal data that helps them to implement their logic. In fact, I suspect that random_access and hashed indices use this ability.
Correct, these indices allocate their own supplemental structures.
Therefore, if there is:
- a way to tell the index the complete node type and means to extract the container value and index's header form it - a way to tell multi_index_container the type of index's header and iterators - a way to notify the index about modification events (such as insert and erase) performed through other indices (at least on per-node basis)
then there is a quite usable basic interface to implement user's indices.
The interface is not a passive one like you seem to be describing, but an active one in which some operations are performed in an orchestrated manner by all the indices. Allow me to give a very incomplete description of how indices work internally. Rouhgly speaking, an index has the following structure: template<typename Super> class index_implementation { public: // public interface typedef typename Super::value_type value_type; typedef ... iterator; ... iterator begin(); ... iterator find(...)const; ... protected: // backbone typedef ... node_type; ... index_implementation(...); void copy_(...); node_type* insert_(...); void erase_(..); void swap_(...); bool replace_(...); ... }; where Super contains a linear hierarchy of the preceding indices and index_implementation is supposed to derive from this to add itself to the chain. The important part is the backbone protected interface by which all the important "primitive" operations of the multi_index_container are implemented: for instance, index_implementation::insert_(...) must do its part of the insertion operation and then call Super::insert_(...) so that the remaining indices do the same, etc. The public member function insert() then resolves to a mere call to this primitive operation. As you see, the degree of coupling is very high --this has been done so in order to provide maximal efficienfy time- and memory-wise. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo