• Philippe Sigaud (8/8) May 30 2010 There are some simple containers I'd like to see in std.containers:
• Simen kjaeraas (4/12) May 30 2010 Absolutely.
• Rainer Deyke (8/14) May 30 2010 Any container that supports pushing and popping on one end can be used
• Marianne Gagnon (6/19) May 30 2010 in the C++ STL, queues and stacks are only adapters to another container...
• Simen kjaeraas (8/12) May 30 2010 There are other concerns than simply what works. First of all is
• Andrei Alexandrescu (5/15) May 30 2010 std.container is designed to provide operations only within strict
• Justin Spahr-Summers (8/21) May 30 2010 This strikes me as a reason to actually not provide such aliases. Even
• Philippe Sigaud (6/13) May 31 2010 Yeah, particularly if having both stack and queue just costs one alias. ...
• bearophile (5/8) May 31 2010 And in some situations it's better to have stacks and queues implemented...
• Andrei Alexandrescu (5/16) May 31 2010 My opinion in the matter is that it's good to have stacks and queues
• Ellery Newcomer (6/14) May 30 2010 (incf vote)
• Philippe Sigaud (11/26) May 31 2010 Me too. Once again, it's a standard libray, it should offer the things
• Jonathan M Davis (9/20) May 30 2010 A sorted map in addition to a hash map would be good, and for a set, bot...
• Ellery Newcomer (3/23) May 30 2010 Maybe an ordered map, i.e. keeps track of order of insertion? I think I
• Andrei Alexandrescu (10/31) May 30 2010 I'm thinking of a slightly different course for std.container. Instead
• Ellery Newcomer (7/39) May 30 2010 My bad.
• Andrei Alexandrescu (5/10) May 30 2010 These are adaptors over other containers, I agree they should be in.
• Philippe Sigaud (15/28) May 31 2010 Looking at some old code of mine, not much. Once you have a BinaryHeap, ...
• Johan Granberg (5/56) Jun 06 2010 I also think a set would be highly usefull, and when defining it pleas d...
• Steven Schveighoffer (8/15) Jun 07 2010 I don't understand this. What better place to put set operations such a...
• Jonathan M Davis (5/19) Jun 07 2010 I think that the complaint is that they _weren't_ included in the
• Mihail Strashun (5/13) May 31 2010 May be my question will be a bit naive, but what is about
• Philippe Sigaud (17/21) Jun 01 2010 My even more naive answer is that I neved had occasion to use it, as I t...
• Mihail Strashun (8/31) Jun 01 2010 Yep, used it about a half an year ago last time. For example, for
• dennis luehring (3/11) Jun 01 2010 and a range based tree (something like http://tree.phi-sci.com/)
• Philippe Sigaud (11/27) Jun 02 2010 I gave it a try some times ago. Here are the current modules:

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

"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

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

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;

"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

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

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.

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

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

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

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

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

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

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

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

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?

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

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

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.

"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

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

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

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.

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.

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?

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