www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Containers I'd like to see in std.containers

reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
There are some simple containers I'd like to see in std.containers:

- a priority queue
- a heap
- a stack, a queue
- a set

Do people here also consider them as containers and useful ones in a standard
library?

  Philippe
May 30 2010
next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Philippe Sigaud <philippe.sigaud gmail.com> wrote:

 There are some simple containers I'd like to see in std.containers:

 - a priority queue
 - a heap
 - a stack, a queue
 - a set

 Do people here also consider them as containers and useful ones in a  
 standard
 library?
Absolutely. -- Simen
May 30 2010
prev sibling next sibling parent reply Rainer Deyke <rainerd eldwood.com> writes:
On 5/30/2010 15:53, Philippe Sigaud wrote:
 There are some simple containers I'd like to see in std.containers:
 
 - a priority queue
 - a heap
 - a stack, a queue
 - a set
Any container that supports pushing and popping on one end can be used as a stack. Any container that supports pushing on one end and popping on the other can be used as a queue. I don't think either of these need their own container type. The others, sure. -- Rainer Deyke - rainerd eldwood.com
May 30 2010
next sibling parent Marianne Gagnon <auria.mg gmail.com> writes:
Rainer Deyke Wrote:

 On 5/30/2010 15:53, Philippe Sigaud wrote:
 There are some simple containers I'd like to see in std.containers:
 
 - a priority queue
 - a heap
 - a stack, a queue
 - a set
Any container that supports pushing and popping on one end can be used as a stack. Any container that supports pushing on one end and popping on the other can be used as a queue. I don't think either of these need their own container type.
in the C++ STL, queues and stacks are only adapters to another container I believe; but I still think it's useful to have them. Stack!int m_ints; seems clearer to me than : /** this is a stack */ Vector!int m_ints;
May 30 2010
prev sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Rainer Deyke <rainerd eldwood.com> wrote:

 Any container that supports pushing and popping on one end can be used
 as a stack.  Any container that supports pushing on one end and popping
 on the other can be used as a queue.  I don't think either of these need
 their own container type.
There are other concerns than simply what works. First of all is readability - having containers called queue and stack makes code easier to understand, even if this is done with a simple alias. There might also be a concern about efficiency, as there is a difference in how fast different containers can push and pop. -- Simen
May 30 2010
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 05/30/2010 05:32 PM, Simen kjaeraas wrote:
 Rainer Deyke <rainerd eldwood.com> wrote:

 Any container that supports pushing and popping on one end can be used
 as a stack. Any container that supports pushing on one end and popping
 on the other can be used as a queue. I don't think either of these need
 their own container type.
There are other concerns than simply what works. First of all is readability - having containers called queue and stack makes code easier to understand, even if this is done with a simple alias. There might also be a concern about efficiency, as there is a difference in how fast different containers can push and pop.
std.container is designed to provide operations only within strict complexity limits. So if something offers insertFront and removeFront or insertBack and removeBack, it should be usable as a stack. Andrei
May 30 2010
prev sibling next sibling parent Justin Spahr-Summers <Justin.SpahrSummers gmail.com> writes:
On Mon, 31 May 2010 00:32:44 +0200, Simen kjaeraas 
<simen.kjaras gmail.com> wrote:
 
 Rainer Deyke <rainerd eldwood.com> wrote:
 
 Any container that supports pushing and popping on one end can be used
 as a stack.  Any container that supports pushing on one end and popping
 on the other can be used as a queue.  I don't think either of these need
 their own container type.
There are other concerns than simply what works. First of all is readability - having containers called queue and stack makes code easier to understand, even if this is done with a simple alias. There might also be a concern about efficiency, as there is a difference in how fast different containers can push and pop.
This strikes me as a reason to actually not provide such aliases. Even for stacks and queues, there are tradeoffs involved in the selection of containers. For instance, vectors and linked lists can both service for a stack implementation, but they have rather different performance and memory characteristics. Similarly for deques implemented with arrays or doubly-linked lists.
May 30 2010
prev sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
Simen & Marianne too:

 There are other concerns than simply what works. First of all is
 readability - having containers called queue and stack makes code easier
 to understand, even if this is done with a simple alias.
 There might also be a concern about efficiency, as there is a difference
 in how fast different containers can push and pop.

 --
 Simen
Yeah, particularly if having both stack and queue just costs one alias. I mean, it's a standard library. I know I can use built-in arrays (for example) as stacks and queues, but sometimes I just want to have a stack. Initially in my mind, that was just to make some graph algorithms clearer. Philippe
May 31 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Philippe Sigaud:
 Yeah, particularly if having both stack and queue just costs one alias. I
mean, it's a standard library. I know I can use built-in arrays (for example) as stacks and queues, but sometimes I just want to have a stack.
And in some situations it's better to have stacks and queues implemented with a deque (for example a dynamic array of pointers to short fixed-size arrays, where all arrays but the first and last one are full) instead of just a dynamic array. Later some kind of cache-conscious B+-something tree can be useful ^_^ The implementation is not much harder than the Red-black trees, etc, but they can be better for small keys, because they use CPU cache lines better. Bye, bearophile
May 31 2010
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 05/31/2010 02:36 PM, Philippe Sigaud wrote:
 Simen & Marianne too:


     There are other concerns than simply what works. First of all is
     readability - having containers called queue and stack makes code easier
     to understand, even if this is done with a simple alias.
     There might also be a concern about efficiency, as there is a difference
     in how fast different containers can push and pop.

     --
     Simen


 Yeah, particularly if having both stack and queue just costs one alias.
 I mean, it's a standard library. I know I can use built-in arrays (for
 example) as stacks and queues, but sometimes I just want to have a stack.
My opinion in the matter is that it's good to have stacks and queues just because in general sometimes it's better to have a more restricted interface. Andrei
May 31 2010
prev sibling next sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 05/30/2010 04:53 PM, Philippe Sigaud wrote:
 There are some simple containers I'd like to see in std.containers:

 - a priority queue
(incf vote) It seems like I'm always writing priority queue implementations whose elements get mutated at weird times and need to be resorted.
 - a heap
 - a stack, a queue
alias + doubly linked list
 - a set
want
 Do people here also consider them as containers and useful ones in a standard
 library?

    Philippe
May 30 2010
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, May 31, 2010 at 00:47, Ellery Newcomer
<ellery-newcomer utulsa.edu>wrote:

 On 05/30/2010 04:53 PM, Philippe Sigaud wrote:

 There are some simple containers I'd like to see in std.containers:

 - a priority queue
(incf vote) It seems like I'm always writing priority queue implementations whose elements get mutated at weird times and need to be resorted.
Me too. Once again, it's a standard libray, it should offer the things anyone will code in its first three months in D. I know I did :-) If Andrei wants std.containers to be containers and this list contains _things_ that are not containers, then by all mean Phobos should have a std.usefulThingiesToPutThingsIn
  - a heap
 - a stack, a queue
alias + doubly linked list - a set

 want
I always end up using a bool[T] as a set, every feeling like I'm cheating or such. Philippe
May 31 2010
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmail.com> writes:
Philippe Sigaud wrote:

 There are some simple containers I'd like to see in std.containers:
 
 - a priority queue
 - a heap
 - a stack, a queue
 - a set
 
 Do people here also consider them as containers and useful ones in a
 standard library?
 
   Philippe
A sorted map in addition to a hash map would be good, and for a set, both a sorted and a hash variety woud be good. And of course, multisets and multimaps would be useful too. We also lack a doubly-linked list. I do agree with others that a normal stack and queue are either unnecessary or that they should be achieved via aliasing or some other thin wrapper. Creating a whole new container just for a name seems a bit silly and creates more code to maintain. - Jonathan M Davis
May 30 2010
parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 05/30/2010 06:25 PM, Jonathan M Davis wrote:
 Philippe Sigaud wrote:

 There are some simple containers I'd like to see in std.containers:

 - a priority queue
 - a heap
 - a stack, a queue
 - a set

 Do people here also consider them as containers and useful ones in a
 standard library?

    Philippe
A sorted map in addition to a hash map would be good, and for a set, both a sorted and a hash variety woud be good. And of course, multisets and multimaps would be useful too. We also lack a doubly-linked list.
Maybe an ordered map, i.e. keeps track of order of insertion? I think I saw this in python once. Looked handy.
 I do agree with others that a normal stack and queue are either unnecessary
 or that they should be achieved via aliasing or some other thin wrapper.
 Creating a whole new container just for a name seems a bit silly and creates
 more code to maintain.

 - Jonathan M Davis
May 30 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 05/30/2010 07:10 PM, Ellery Newcomer wrote:
 On 05/30/2010 06:25 PM, Jonathan M Davis wrote:
 Philippe Sigaud wrote:

 There are some simple containers I'd like to see in std.containers:

 - a priority queue
 - a heap
 - a stack, a queue
 - a set

 Do people here also consider them as containers and useful ones in a
 standard library?

 Philippe
A sorted map in addition to a hash map would be good, and for a set, both a sorted and a hash variety woud be good. And of course, multisets and multimaps would be useful too. We also lack a doubly-linked list.
Maybe an ordered map, i.e. keeps track of order of insertion? I think I saw this in python once. Looked handy.
I'm thinking of a slightly different course for std.container. Instead of defining an OrderedMap structure that doesn't specify its implementation, std.container will define _explicit_ consecrated data structures, such as BinaryTree and RedBlackTree (Steve Schveighoffer graciously contributed his R-B tree implementation). Later on, we might define a set of generic aliases for typical container choices, but I want std.container to actually reflect the interesting personalities and tradeoffs that data structures have. Andrei
May 30 2010
parent Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 05/30/2010 07:41 PM, Andrei Alexandrescu wrote:
 On 05/30/2010 07:10 PM, Ellery Newcomer wrote:
 On 05/30/2010 06:25 PM, Jonathan M Davis wrote:
 Philippe Sigaud wrote:

 There are some simple containers I'd like to see in std.containers:

 - a priority queue
 - a heap
 - a stack, a queue
 - a set

 Do people here also consider them as containers and useful ones in a
 standard library?

 Philippe
A sorted map in addition to a hash map would be good, and for a set, both a sorted and a hash variety woud be good. And of course, multisets and multimaps would be useful too. We also lack a doubly-linked list.
Maybe an ordered map, i.e. keeps track of order of insertion? I think I saw this in python once. Looked handy.
I'm thinking of a slightly different course for std.container. Instead of defining an OrderedMap structure that doesn't specify its implementation, std.container will define _explicit_ consecrated data structures, such as BinaryTree and RedBlackTree (Steve Schveighoffer graciously contributed his R-B tree implementation). Later on, we might define a set of generic aliases for typical container choices, but I want std.container to actually reflect the interesting personalities and tradeoffs that data structures have. Andrei
My bad. alias RedBlackTreeWithDoublyLinkedListFieldsInRBNodeAndMaraschinoCherryOnTop OrderedMap; Disregarding implementation, do you think this one would be useful enough to merit inclusion?
May 30 2010
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 05/30/2010 04:53 PM, Philippe Sigaud wrote:
 There are some simple containers I'd like to see in std.containers:

 - a priority queue
 - a heap
What's the difference between the two?
 - a stack, a queue
These are adaptors over other containers, I agree they should be in.
 - a set
Yah, though I want std.container to focus on implementation, not policy. Andrei
May 30 2010
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, May 31, 2010 at 01:56, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

 On 05/30/2010 04:53 PM, Philippe Sigaud wrote:

 There are some simple containers I'd like to see in std.containers:

 - a priority queue
 - a heap
What's the difference between the two?
Looking at some old code of mine, not much. Once you have a BinaryHeap, a PriorityQueue!(Payload,Priority) is just a BinaryHeap!(Tuple!(Payload, Priority)) with a sorter acting on the tuple's second field and front() (or whatever it's called for containers) returning the first field. And, of course, nice creating functions. So, heap is the basis, priority queue is just a nice wrapper. But I want nice wrappers! They are easy to code, and gives joe phobos what he wants.
  - a stack, a queue

 These are adaptors over other containers, I agree they should be in.
Yes, an adaptor with a default implementation. Do you consider built-in arrays (not slices) to be containers?
  - a set

 Yah, though I want std.container to focus on implementation, not policy.
Please, a set, please, a set! I mean, where would you put it otherwise? Philippe
May 31 2010
parent reply Johan Granberg <lijat.meREM OVEgmail.com> writes:
Philippe Sigaud wrote:

 On Mon, May 31, 2010 at 01:56, Andrei Alexandrescu <
 SeeWebsiteForEmail erdani.org> wrote:
 
 On 05/30/2010 04:53 PM, Philippe Sigaud wrote:

 There are some simple containers I'd like to see in std.containers:

 - a priority queue
 - a heap
What's the difference between the two?
Looking at some old code of mine, not much. Once you have a BinaryHeap, a PriorityQueue!(Payload,Priority) is just a BinaryHeap!(Tuple!(Payload, Priority)) with a sorter acting on the tuple's second field and front() (or whatever it's called for containers) returning the first field. And, of course, nice creating functions. So, heap is the basis, priority queue is just a nice wrapper. But I want nice wrappers! They are easy to code, and gives joe phobos what he wants.
  - a stack, a queue

 These are adaptors over other containers, I agree they should be in.
Yes, an adaptor with a default implementation. Do you consider built-in arrays (not slices) to be containers?
  - a set

 Yah, though I want std.container to focus on implementation, not policy.
Please, a set, please, a set! I mean, where would you put it otherwise? Philippe
I also think a set would be highly usefull, and when defining it pleas don't let the set operations (union,intersection,maybe complement) be defined. I recently was writing some c++ code and got a nasty preformance hit from not finding a fast set union operation.
Jun 06 2010
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 06 Jun 2010 14:48:27 -0400, Johan Granberg  
<lijat.meREM ovegmail.com> wrote:


 I also think a set would be highly usefull, and when defining it pleas  
 don't
 let the set operations (union,intersection,maybe complement) be defined.  
 I
 recently was writing some c++ code and got a nasty preformance hit from  
 not
 finding a fast set union operation.
I don't understand this. What better place to put set operations such as intersection and union besides the implementation of the set itself? For example, dcollections includes these operations (union (add) and complement (remove) are essential anyways, intersection is the odd duck) as the quickest possible implementation O(n * lg(n)). -Steve
Jun 07 2010
parent Jonathan M Davis <jmdavisProg gmail.com> writes:
Steven Schveighoffer wrote:

 On Sun, 06 Jun 2010 14:48:27 -0400, Johan Granberg
 <lijat.meREM ovegmail.com> wrote:
 
 
 I also think a set would be highly usefull, and when defining it pleas
 don't
 let the set operations (union,intersection,maybe complement) be defined.
 I
 recently was writing some c++ code and got a nasty preformance hit from
 not
 finding a fast set union operation.
I don't understand this. What better place to put set operations such as intersection and union besides the implementation of the set itself?
I think that the complaint is that they _weren't_ included in the implementation itself, and he hopes that D's implementation _does_ include them. - Jonathan M Davis
Jun 07 2010
prev sibling next sibling parent reply Mihail Strashun <m.strashun gmail.com> writes:
May be my question will be a bit naive, but what is about 
boost::multi_index approach? I find it brilliant for dividing container 
implementation from various container interfaces - things you guys are 
arguing here about a bit.

On 05/31/2010 12:53 AM, Philippe Sigaud wrote:
 There are some simple containers I'd like to see in std.containers:

 - a priority queue
 - a heap
 - a stack, a queue
 - a set

 Do people here also consider them as containers and useful ones in a standard
 library?

    Philippe
May 31 2010
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, May 31, 2010 at 22:27, Mihail Strashun <m.strashun gmail.com> wrote:

 May be my question will be a bit naive, but what is about
 boost::multi_index approach? I find it brilliant for dividing container
 implementation from various container interfaces - things you guys are
 arguing here about a bit.
My even more naive answer is that I neved had occasion to use it, as I think I quit C++ before this existed in Boost (but I may be wrong). I read the docs for multi-index once or twice, though. Did you use it recently? Hey, I was re-reading Boost::MPL, Fusion and Graph recently and was thinking that it's be quite easier to do that in D. Interestingly, on Boost 1.43 (may 6th): Major Updates - Range <http://www.boost.org/libs/range/index.html>: Boost.Range has undergone extensive updates that it include all of the features from the recently reviewed Boost.RangeEx, from Neil Groves. - Range-based version of the full STL iterator based algorithms. - Range adaptors which can be combined with range-based algorithms for unprecedented expressiveness and efficiency. - New functions: irange, istream_range, join, combine. http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/index.html Man, I didn't know they had it.
Jun 01 2010
parent Mihail Strashun <m.strashun gmail.com> writes:
On 06/01/2010 10:48 PM, Philippe Sigaud wrote:
 On Mon, May 31, 2010 at 22:27, Mihail Strashun <m.strashun gmail.com
 <mailto:m.strashun gmail.com>> wrote:

     May be my question will be a bit naive, but what is about
     boost::multi_index approach? I find it brilliant for dividing
     container implementation from various container interfaces - things
     you guys are arguing here about a bit.


 My even more naive answer is that I neved had occasion to use it, as I
 think I quit C++ before this existed in Boost (but I may be wrong). I
 read the docs for multi-index once or twice, though. Did you use it
 recently?
Yep, used it about a half an year ago last time. For example, for defining nice OrderedMap with only a pair lines of code :) Liked idea a lot and thought that similar stuff in D2 could be even better, getting rid of C++ template syntax.
 Hey, I was re-reading Boost::MPL, Fusion and Graph recently and was
 thinking that it's be quite easier to do that in D.
I think same, don't no D so good yet, though.
 Interestingly, on Boost 1.43 (may 6th):


       Major Updates

     * Range <http://www.boost.org/libs/range/index.html>: Boost.Range
       has undergone extensive updates that it include all of the
       features from the recently reviewed Boost.RangeEx, from Neil Groves.
           o Range-based version of the full STL iterator based algorithms.
           o Range adaptors which can be combined with range-based
             algorithms for unprecedented expressiveness and efficiency.
           o New functions: irange, istream_range, join, combine.


 http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/index.html

 Man, I didn't know they had it.
Boost::Range is hanging there for quite a long time - more than 5 years, AFAIK.
Jun 01 2010
prev sibling parent reply dennis luehring <dl.soluz gmx.net> writes:
Am 30.05.2010 23:53, schrieb Philippe Sigaud:
 There are some simple containers I'd like to see in std.containers:

 - a priority queue
 - a heap
 - a stack, a queue
 - a set

 Do people here also consider them as containers and useful ones in a standard
 library?

    Philippe
and a range based tree (something like http://tree.phi-sci.com/) and what about graphs?
Jun 01 2010
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Wed, Jun 2, 2010 at 08:27, dennis luehring <dl.soluz gmx.net> wrote:

 Am 30.05.2010 23:53, schrieb Philippe Sigaud:

  There are some simple containers I'd like to see in std.containers:
 - a priority queue
 - a heap
 - a stack, a queue
 - a set

 Do people here also consider them as containers and useful ones in a
 standard
 library?

   Philippe
and a range based tree (something like http://tree.phi-sci.com/) and what about graphs?
I gave it a try some times ago. Here are the current modules: http://www.dsource.org/projects/dranges/wiki (look into the tree and graph section and tell me what you think.) There is a basic tree and basic graph, some consideration on recursive ranges and a bunch of graph algorithms (dijkstra, spanning tree, meta-graph, strongly connected components, etc). Also, ways to project a tree or graph into a linear range, by depth-first or breadth-first iteration. It's taken from an older project of mine,I will clean it up in the following weeks. Philippe
Jun 02 2010