Boost logo

Boost :

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
> 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

> 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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at