Alex Shafir wrote:
The other idea is the “sparse array” container. Working for securities trading industry I used it innumerable number of times. It is useful in situations where there is a set of entities identified by integer(unsigned) numbers. Most often the numbers are identity keys in a database, a protocol field ids, etc. The potential range of the numbers makes it impractical to use a C++ array or the STL <vector>. On the other hand the average percentage of the keys that are really used in an application relative to the potential range is often less then 5% and there are huge holes of unused keys between zero and max(used key). The data elements or pointers to objects are kept in a structure similar to a balanced B-tree. Elements are directly accessed by an index operator. Access involves only a few arithmetic and redirection operations. When storing a new element that is outside of the range provided by exiting data structure the structure bilds itself up extending the indes range enough to accommodate a new index value. Existing data are never physically moved like in the STL vector. So, all references/pointers/iterators referencing existing elements are never invalidated.
Very interesting, but how is it substantially different from std::map? -- Dave Abrahams BoostPro Computing http://www.boostpro.com