www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Miscellaneous question regarding std.container?

reply "Too Embarrassed To Say" <kheaser eapl.org> writes:
The std.container starts off with container primitives. Does this 
mean that all containers should support all these primitives?  
Because I could never get c.length to work for a simple SList.

Are there formal definitions for  U and Stuff like  in (U)(U[] 
values...) and (string op, Stuff)(Stuff stuff);


struct SList(T);   //  Implements a simple and fast singly-linked 
list.

Since SList is a structure and in the excellent book by 
Andrei[A..u], he says for structure constructors (7.1.3.1) 
“…the compiler always defines the no-arguments constructor”.

This being the case shouldn’t one of the following compile?

SList(int) s1;
SList() s2;
SList s3;
auto s4 = SList;
auto s5 = SList();
auto s6 = SList(int);


And how does the std.array differ from the Array in 
std.container?  Is the std.array array a class while the 
std.container array a structure?
Nov 03 2012
next sibling parent "Tobias Pankrath" <tobias pankrath.net> writes:
On Saturday, 3 November 2012 at 18:38:14 UTC, Too Embarrassed To 
Say wrote:

 The std.container starts off with container primitives. Does 
 this mean that all containers should support all these 
 primitives?  Because I could never get c.length to work for a 
 simple SList.


That is a complete list of all possible primitives that can occur 
in the interface of  a std.container. However not every container 
defines every primitive. SList for example does not define 
length, because length is required (by convention) to be O(1), 
which is impossible with the current SList implementation.


 Are there formal definitions for  U and Stuff like  in (U)(U[] 
 values...) and (string op, Stuff)(Stuff stuff);


No really, these are template parameters. U needs to be implicit 
convertible to T for an SList!T and Stuff needs to be an 
InputRange of U. Which you can only know if you read the source 
:-)



 struct SList(T);   //  Implements a simple and fast 
 singly-linked list.

 Since SList is a structure and in the excellent book by 
 Andrei[A..u], he says for structure constructors (7.1.3.1) 
 “…the compiler always defines the no-arguments 
 constructor”.

 This being the case shouldn’t one of the following compile?

 SList(int) s1;
 SList() s2;
 SList s3;
 auto s4 = SList;
 auto s5 = SList();
 auto s6 = SList(int);


You need an ! before the template parameter.

SList!int s1;
SList!(TypeTuple!(int, long)) s2;

Note that the container are reference types.
Nov 03 2012
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, November 03, 2012 19:38:13 Too Embarrassed To Say wrote:

 The std.container starts off with container primitives. Does this
 mean that all containers should support all these primitives?
 Because I could never get c.length to work for a simple SList.


They're a list of common operations, each of which has a maximal algori=
thmic=20
complexity, and some of which require that they not invalidate ranges (=
i.e.=20
they have stable in their name). Cointainers should implement as many o=
f them=20
as they can, but if they can't implement a function with at most the gi=
ven=20
algorithmic complexity, or they can't implement a stable function witho=
ut=20
invalidating a range, or if the function just plain doesn't make sense =
for=20
that container (e.g. reserve and capacity make no sense for linked list=
s),=20
then they don't implement them. SList doesn't have length, because leng=
th can=20
at worst be O(log n) (I thought that it was O(1), but the docs say O(lo=
g n)),=20
and SList can't implement it in better than O(n).


 Are there formal definitions for  U and Stuff like  in (U)(U[]
 values...) and (string op, Stuff)(Stuff stuff);


Those are template parameters. Why would you need a formal definition? =
They're=20
just generic names for the types, just like T in struct SList(T).


 struct SList(T);   //  Implements a simple and fast singly-linked
 list.
=20
 Since SList is a structure and in the excellent book by
 Andrei[A..u], he says for structure constructors (7.1.3.1)
 =E2=80=9C=E2=80=A6the compiler always defines the no-arguments constr=


uctor=E2=80=9D.

=20
 This being the case shouldn=E2=80=99t one of the following compile?
=20
 SList(int) s1;
 SList() s2;
 SList s3;
 auto s4 =3D SList;
 auto s5 =3D SList();
 auto s6 =3D SList(int);


None of those will compile, because they all use templates incorrectly.=
 SList=20
by itself is not a type. It's a template for a type, so you can never u=
se=20
SList by itself. It must always be an instantiation of SList - e.g. SLi=
st!
(int) or SList!int (the parens are optional when there's only one templ=
ate=20
argument). You're giving the type for T in struct SList(T) when you do=20=

SList!int. Without that, you haven't instantiated SList, and you're dea=
ling=20
with an actual type. So, your lines without parens there won't work, an=
d your=20
lines with parens but no ! won't work. You can generally avoid explicit=
ly=20
instantiating templated functions, because the types of the template ar=
guments=20
are inferred, but that doesn't happen with templated types. The compile=
r has=20
no way of knowing what you want to instantiate SList with unless you te=
ll it.

I'd advise that you read the section on templates in TDPL if you haven'=
t=20
already, since you clearly don't understand them.


 And how does the std.array differ from the Array in
 std.container?  Is the std.array array a class while the
 std.container array a structure?


There's no relation whatsoever. std.array is a module. std.container.Ar=
ray is=20
a type. std.array contains functions that operate on built-in arrays.=20=

std.container.Array is a container similar to C++'s vector or Java's=20=

ArrayList, which encapsulates an array but adds extra functionality on =
top of=20
it.

- Jonathan M Davis
Nov 03 2012