[GSoC] Generic Linked List library
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.
Thomas Mullaly wrote:
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.
There are already in Boost.Intrusive single linked list and double linked lists, and both are wrapped into containers with full move, emplace and next-gen allocator support in Boost.Container (in the review queue). The containers do not have policies in order to keep the standard interface, but the intrusive versions do. It might be interesting to ask the author of those two libraries, Ion Gaztañaga, whether he thinks you can provide improvements to them. In any case I'm not sure there is enough material for a project there.
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.
There are already in Boost.Intrusive single linked list and double linked lists, and both are wrapped into containers with full move, emplace and next-gen allocator support in Boost.Container (in the review queue).
The containers do not have policies in order to keep the standard interface, but the intrusive versions do. It might be interesting to ask the author of those two libraries, Ion Gaztañaga, whether he thinks you can provide improvements to them. In any case I'm not sure there is enough material for a project there
Ah... I wasn't aware that Container was in the review queue (sorry Tom). I think that this library might provide some good extensions for the Container library. I think it would be nice to have O(1) spliceable lists, if the programmer wants them. I wonder if it would be worthwhile to consider folding the heaps/queues idea into a container's extension also. If done well, it could be of good value. Hopefully Ion is listening and will be able to provide some feedback :) Andrew Sutton andrew.n.sutton@gmail.com
Andrew Sutton-2 wrote:
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.
There are already in Boost.Intrusive single linked list and double linked lists, and both are wrapped into containers with full move, emplace and next-gen allocator support in Boost.Container (in the review queue).
The containers do not have policies in order to keep the standard interface, but the intrusive versions do. It might be interesting to ask the author of those two libraries, Ion Gaztañaga, whether he thinks you can provide improvements to them. In any case I'm not sure there is enough material for a project there
Ah... I wasn't aware that Container was in the review queue (sorry Tom). I think that this library might provide some good extensions for the Container library. I think it would be nice to have O(1) spliceable lists, if the programmer wants them.
I think that this is is already provided by the intrusive and container libraries. Best, Vicente -- View this message in context: http://old.nabble.com/-GSoC--Generic-Linked-List-library-tp28075331p28078557... Sent from the Boost - Dev mailing list archive at Nabble.com.
participants (4)
-
Andrew Sutton -
Mathias Gaunard -
Thomas Mullaly -
Vicente Botet Escriba