Our arrays aren't (2005)(ridiculousfish.com)
ridiculousfish.com
Our arrays aren't (2005)
http://ridiculousfish.com/blog/posts/array.html
5 comments
The author seems to criticize that the Java classes are named for how they're implemented, whereas the CoreFoundation ones are named for what they are instead. In Java, though, the convention (at least in the Collection library), is that the Interface name tells you what the thing is (List, Map, Set), and the class name tells you how it's implemented (ArrayList/LinkedList, HashMap/ConcurrentMap, HashSet/TreeSet).
The author is criticizing Apple's versions, not the Java/C++ ones.
Nitpick: the STL is not standard C++. The containers in the standard library are listed at http://en.cppreference.com/w/cpp/container.
Yes, it is. Its basis was developed independently, but when people speak of the STL today, they are referring to the standard algorithms and containers.
The containers for the standard library are indeed at the link you provided. Those are traditionally referred to as STL containers. No?
The STL is a product developed and maintained by SGI. If you look at the containers listed in the article and on the SGI page, you will see a different set than is present in the C++ standard library, especially if you discount the containers that weren't in the C++ standard library when the article was written.
Now, people often refer to the C++ standard library as the STL, but the author of the article was clearly confusing the STL itself with the standard library, not just the name.
Now, people often refer to the C++ standard library as the STL, but the author of the article was clearly confusing the STL itself with the standard library, not just the name.
What's the actual data structure behind this? Is it something like the blist[1] (i.e., counted b+ tree)?
[1] https://pypi.python.org/pypi/blist/
EDIT: Nvm, the article actually links to the implementation and it seems to be an order statistics 2-3 tree: http://www.opensource.apple.com/source/CF/CF-368.18/Collecti...
[1] https://pypi.python.org/pypi/blist/
EDIT: Nvm, the article actually links to the implementation and it seems to be an order statistics 2-3 tree: http://www.opensource.apple.com/source/CF/CF-368.18/Collecti...
I'm a bit surprised that the graphs for the "standard" arrays are so flat. I would have guessed that there were be some cache and TLB effects. I'd be interested to see what it looks like on a modern processor, but the link to the source is dead. Please post a link if you find it.