Topic: C++0x Container "Requirements


Author: Stephen Howe <sjhoweATdialDOTpipexDOTcom@giganews.com>
Date: Mon, 1 Jun 2009 14:09:12 CST
Raw View
>Why does forward_list fail to provide a size() function? Is there
>anything from preventing forward_list from defining a function that
>counts the number of elements in O(n) time when it is called?
>Presumably if I want to keep track of the size of the list I'm either
>going to do that myself of I am going to keep a running count of my
>own.

I concur with this.

My position on this is that std::forward_list should do whatever
std::list does with size() in the standard. size() for std::list is
intractable where some cases of splice() versus size() cant both be
O(1). I see no reason for std::forward_list not to provide size()
member.

Stephen Howe

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]





Author: Scott Meyers <usenet@aristeia.com>
Date: Sat, 23 May 2009 10:54:53 CST
Raw View
Table 80 lists container requirements. Table 83 lists sequence container
requirements.  Section 23.2 is "Sequence Containers," and subsection 23.2.3
describes forward_list.  Paragraph 2 of this subsection points out that
forward_list fails to fulfill the requirements of Table 80, and
inspection shows
that it fails to fulfill the requirements of Table 83.  array fails to
satisfy
the sequence container requirements, too.

I understand that the container requirements framework has proven to be too
rigid for what the committee has chosen to standardize, and the
forward_list
proposal (N2231) points out that the unordered associative containers
also fail
to fulfill all the container requirements.

It seems to me that the word "Requirements" is just being abused here
and can't
help but confuse readers of the standard who might foolishly assume that a
container requirement would be fulfilled by all standard containers.  I
suggest
that the standard would be clearer if the "requirements" were limited to
those
things that are truly required.

Perhaps the simplest fix would be to create a new container subsection
called
something like "Nonconforming containers" with sequence and associative
subsections into which forward_list, array, and the unordered containers
were
placed.

Scott

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]





Author: "Bo Persson" <bop@gmb.dk>
Date: Sun, 24 May 2009 14:47:01 CST
Raw View
Scott Meyers wrote:
> Table 80 lists container requirements. Table 83 lists sequence
> container requirements.  Section 23.2 is "Sequence Containers," and
> subsection 23.2.3 describes forward_list.  Paragraph 2 of this
> subsection points out that forward_list fails to fulfill the
> requirements of Table 80, and inspection shows
> that it fails to fulfill the requirements of Table 83.  array fails
> to satisfy
> the sequence container requirements, too.
>
> I understand that the container requirements framework has proven
> to be too rigid for what the committee has chosen to standardize,
> and the forward_list
> proposal (N2231) points out that the unordered associative
> containers also fail
> to fulfill all the container requirements.
>
> It seems to me that the word "Requirements" is just being abused
> here and can't
> help but confuse readers of the standard who might foolishly assume
> that a container requirement would be fulfilled by all standard
> containers.  I suggest
> that the standard would be clearer if the "requirements" were
> limited to those
> things that are truly required.
>
> Perhaps the simplest fix would be to create a new container
> subsection called
> something like "Nonconforming containers" with sequence and
> associative subsections into which forward_list, array, and the
> unordered containers were
> placed.
>

A major problem here is that in the duck-typing land of templates, the
container requirements is exactly what defines a container. If about
half the Containers library clause describes limping ducks, what
exactly have we achived?

Also, have you noticed that basic_string makes a blanket claim (21.4)
of fullfilling the Sequence Container requirements? It isn't fully
aware that the linked-to clause has been re-edited!


Bo Persson



--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]





Author: "george.ryan@gmail.com" <george.ryan@gmail.com>
Date: Mon, 25 May 2009 16:25:04 CST
Raw View
On May 23, 1:54 pm, Scott Meyers <use...@aristeia.com> wrote:
> Paragraph 2 of this subsection points out that
> forward_list fails to fulfill the requirements of Table 80,

Why does forward_list fail to provide a size() function? Is there
anything from preventing forward_list from defining a function that
counts the number of elements in O(n) time when it is called?
Presumably if I want to keep track of the size of the list I'm either
going to do that myself of I am going to keep a running count of my
own.

> that it fails to fulfill the requirements of Table 83.  array fails to
> satisfy the sequence container requirements, too.

At least the array isn't listed under section 23 as being a container
by "requirement", only to have the fine print say otherwise.

> proposal (N2231) points out that the unordered associative containers
> also fail to fulfill all the container requirements.
> [SNIP]
> .confuse readers of the standard who might foolishly assume that a
> container requirement would be fulfilled by all standard containers.

I don't think it is foolish to look under the "Containers
requirements" section and assume all of the containers therein meet
the requirements, because isn't that the point? Why put container
requirements forth and then say 'except this one, this one, and that
one. Oh, and that one'?

As an embedded programmer, I can tell you that one of the things I'm
likely to put forward to my team is to use forward_list<> instead of
list<> when it's applicable to do so. I'm not looking forward to the
discussion of it being 'almost a container' when someone figures it
out.

> I suggest
> that the standard would be clearer if the "requirements" were limited to
> those things that are truly required.

Seconded. Either that, or have different sets of requirements for
different types of containers.

> something like "Nonconforming containers" with sequence and associative

Isn't this just akin to pointing out that either the requirements are
wrong or the containers aren't "containers?"


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]





Author: brangdon@cix.co.uk (Dave Harris)
Date: Sat, 30 May 2009 12:07:02 CST
Raw View
george.ryan@gmail.com () wrote (abridged):
> Why does forward_list fail to provide a size() function?

Presumably to discourage implementors from providing an O(1) version with
the associated memory overhead, and to discourage clients from using an
O(N) version inappropriately:
     for (size_t i = 0; i < list.size(); ++i)

and so inadvertently getting an O(N*N) algorithm.

We already have this issue, only worse, with normal lists, where size()
might be O(1) or O(N) (depending on how fast splice() is).

-- Dave Harris, Nottingham, UK.

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]