Boost logo

Boost :

Subject: [boost] [GSoC] Generic Linked List library
From: Thomas Mullaly (thomas.mullaly_at_[hidden])
Date: 2010-03-29 17:18:09

Hi, my name is Thomas Mullaly. I am currently an undergraduate in the
Computer Science department at Kent State University and I am interested
in contributing a generic linked-list library to Boost as a GSoC project
and I just wanted to see if there is any interest from the Boost
community about having these contributed as a library.

I am implementing the linked lists project from 'Elements of
Programming' (ch. 12, I think), and am trying to provide lists for both
constant-time size and constant-time splice. My library currently
implements a number of variations of both singly- and doubly-linked
lists, and I have implemented a wrapper that adds a node count and acts
as a counted list.

While the basic list types are already implemented, there is still a lot
of work to done on them. For my GSoC project I would like to integrate
allocator support into them, clean up the existing interface, and create
a generic interface to the different types of lists with the help of a
mentor. By the end of my GSoC project I would like to have a functional
list library to contribute to Boost.

I feel that this would be a valuable library to Boost because the
standards implementation limits you (depending on your library vendor)
to either a constant time size() function with a linear time splice
operations or constant time splice operations with a linear time size()
function. With my implementations a developer will be able to pick and
choose whether they want a singly or a doubly linked list, or if they
want to use a counted listed instead of a non-counted list. Also their
is variations in memory/runtime efficiency between the different
variations of the list types which a developer will be able to choose for.

Currently my list implementations make heavy use of the new features
available in C++0x such as rvalue references and move semantics, but, I
will be more than happy to create a backport of these for the current
C++ standard so they can be included in Boost.

If anyone is interested in the source code for my current list
implementations I will be able to provide tarballs of them.

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