Subject: [boost] Google Summer of Code Proposal Feedback
From: Niall Douglas (ndouglas_at_[hidden])
Date: 2013-04-25 12:34:48
> aware of GSOC until recently. I had strongly considered writing a proposal
> for Boos.ASIO, but I fear my lack of experience with Linux, POSIX, and
> concurrency in general might prove to be too great of an obstacle. If the
> subject matter can be learned relatively quickly, I would love to discuss
> what such a project would require with the mentor, Niall Douglas, or a
> community member who has is familiar with the project.
I'm hardly "the" mentor in Boost.ASIO. I'm probably just the only one to
have registered as a potential mentor so far. It's still early days. A lot
more potential mentors will register in time, then depending on project
scoring and people's availability and of course Google's preferences, we'll
see what turns out.
> My original proposal probably isn't unique, and much to my chagrin as I
> read the hints for successful proposals it seems a popular topic. I am of
> course suggesting a project dealing with Trees. Rather than suggest
> building a generic tree, I am suggesting the start of a tree library, or
> the addition of several types of trees to existing libraries, as I am not
> sure which is more appropriate.
An awful lot of students expose their ignorance of what Boost, or indeed the
C++ standard library, provides during GSoC. It really doesn't help them to
be scored well which is why Boost strongly recommends that students discuss
their ideas here first before submission. 95% of the time their idea is
already implemented.
For example, there are multiple tree implementations in the C++ STL and
Boost. Look into Boost.Intrusive for example.
> Because trees are such a fundamental data type in computer science, I
have
> found it difficult to understand why there are no explicit tree classes in
> the c++ standard.
They generally don't have "tree" in their name ;)
> tested in an afternoon, while implementing a Red Black Tree would take
> considerably longer, yet the C++ standard has linked lists and not Red
> Black Trees.
Red-black trees are called std::map<>, std::set<> et al. in C++ since 1998.
Of course std::map<> et al. doesn't *have* to be implemented as red-black,
but most implementations do since the SGI STL defined std::map<> using
stl_tree<>.
> The library I am proposing should eventually be able to satisfy almost
> anyone requiring the use of a tree. It should have many different types of
> trees, Binary trees, AVL Trees, Red Black Trees, Treeps, B-Trees,
> Skip-Lists, etc. It should support common methods of traversal, inorder,
> preorder, postorder, and user defined traversal methods. Eventually, the
> library should support an n-ary trees and their operations. Trees in the
> library should also be performant, fail gracefully, be well documented,
> unit and integration tested, as exception safe as possible, and, someday,
Look into Boost.Intrusive. They're the most appropriate category for what
you propose.
Niall