Dear Julia colleagues, As mentioned in earlier posts, I'm working on a 2-3 tree implementation of sorted associative arrays (analogous to map and multimap in C++). This is like Dict in Julia, except that the key/value pairs can be retrieved in sort-order on the keys.
For my preliminary implementation, the timing for a sequence of 10^7 insert and find operations is encouraging: my Julia 2-3 trees: 10 sec; my Julia 2-3 trees with @inbounds everywhere: 8 sec; my C++ 2-3 trees: 20 sec; my C++ 2-3 trees with /O2 compilation: 6 sec; native C++ map (red/black trees) with /O2 compilation: 5 sec. I have a few additional questions. (1) Iteration: The Julia manual describes a start/next/done formulation for iteration in which the iterator returns (key,value) pairs. However, this is not adequate for some uses of maps. In C++ an iterator is like a pointer to the (key,value) pair or like a subscript of an array. The usefulness of this approach is that the iterator itself can be stored in another data structure and then dereferenced much later. I'm wondering whether there is a convention in Julia for naming and operating with this kind of iterator. (It could be related to the 'state' data item described in 2.1.7 of the manual.) (2) Related to the above question: if m is the map and i is the iterator, then a second getindex can be implemented so that m[i] returns the key-value pair. However, it is a bit confusing to overload [] in this way because of the resemblance to m[k] where k is a key that returns just the value. Does Julia offer the possibility of overloading some other subscript notation besides []? For example, maybe Julia could implement a syntax like m[. i .] or something that would call getindex2 and setindex2? it seems to me that there will be other cases when a user has a data structure that can be indexed in more than one way. I suppose this must already come up with sparse matrices? (3) @inbounds: Is there a way for a user-written data structure to check whether @inbounds is active, and if so, to use a different faster version of (user-written) getindex and setindex? Thanks, Steve Vavasis
