[boost] [GSoC] Generic Linked List library

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.