Comment by jandrewrogers | Hacker News Reader

Comment by jandrewrogers | Hacker News Reader

This is a pretty good list of data structures that are out there, that are also useful, and to which most programmers never seem to have been introduced. I regularly use variants of some of the data structures listed (plus several that did not make the list) and frequently get questions about the design and structure from programmers that have never seen them.

In practice, you can get away with knowing just a handful of data structures and most programmers do. However, when it comes time to profile it is valuable to have alternatives to what the standard libraries and implementations offer. For any given set of constraints on the intended use case and workload for a classic container, there is usually a data structure that is nearly ideal for that use case. Also, there are often neat ideas buried in some of these data structures that are worth learning for their own sake.

For the work that I do (high-performance C++) the first pass will often use the C++ STL. When we start profiling, the STL is usually among the first things that need to be replaced. Having a large number of workload optimized data structures in the toolkit for the same abstract container makes this relatively easy.

That's interesting, I always thought of STL as a well-designed piece of library. Or is it just not specialised enough to fit your case?

I cannot speak to jandrewrogers specific reason, but the two major sticking points I've seen developers hit is the STL's bad allocator design and the lack of intrusive data structures. Check out EASTL for more information [1][2].

[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227... [2] https://github.com/paulhodge/EASTL

STL is good for what it is. The limitation is that there is little ability to specify behaviors, use cases, data distributions, workload profiles, etc because that would effectively break the abstraction and expose the internals.

However, STL still requires an implementation and so the implementors select algorithms that will give adequate performance across a wide range of scenarios but which are usually significantly suboptimal for any specific scenario. Consequently, a custom implementation tuned for a specific scenario will often handily out-perform the STL implementation. For the kinds of applications I work on, poor-fitting STL implementations are frequently major bottlenecks in the profiler.

It is plausible to add an enormous number of implementations and data structures to STL that would allow someone to select/construct the perfect data structure for a particular use case. However, that would also add a level of complexity to the STL that probably is not worth the benefit for many users.

> The limitation is that there is little ability to specify behaviors, use cases, data distributions, workload profiles, etc because that would effectively break the abstraction and expose the internals.

STL's limitation is its design. That's the real reason why STL acceptance is low (for a Standard library), not the often cited compatibility issues.

> STL's limitation is its design.

Care to elaborate more on this?

Can you give a concrete example of a refactoring you had to do?

STL uses 'value semantics'. Just use push_back in a loop and observe how often the whole data in std::vector is copied. Not to mention std::sort.

vector::emplace_back ameliorates by allowing new elements to be constructed in-place [1]

[1] http://en.cppreference.com/w/cpp/container/vector/emplace_ba...

Value semantics are the only sensible default in a language like C++. If you need reference semantics, store (smart) pointers explicitly.

Reply on news.ycombinator.com