Lance Page <page@k2.mv.com> wrote:

>Fortunately, it's perfectly feasible to SPECIALIZE an algorithm based on
>ITERATOR CATEGORY.
>So we're not necessarily stuck with the same algorithm implementation for all
>containers/iterators if we don't want to be.
>
>For example, we could implement count() to take just only two arguments
>(Iter start, Iter end),
>and that runs in O(1) for containers with random access iterators and O(N)
>for other containers.

There is already an algorithm that does this. Its called distance() and
it's in the (draft) standard library. You even mentioned it in your
post.

distance() can not replace size().  size() is O(1) for all containers.
distance() is only O(1) for vector<T>::iterator, deque<T>::iterator and
other random-access iterators. There is no way to write distance() so
that it would be O(1) for non-random-access iterators. Thus size() is a
still needed.

Besides, even if there were another way to calculate it, size is an
intrinsic attribute of a container and it makes sense to have a
convenient way to get it. The library is not so minimalistic that
conventient methods are left out just because there is another way to
get the same result.

-------------------------------------------------------------
Pablo Halpern                   phalpern@truffle.ultranet.com

I am self-employed. Therefore, my opinions *do* represent
those of my employer.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Bradd W. Szonye <bradds@concentric.net> wrote:
: Joe Buck wrote:
: >
: > Bradd W. Szonye <bradds@concentric.net> wrote:
: > >I suspect that size() is a member function so that it has an O(1) and
: > >not O(n) implementation. For all iterators except random-access
: > >iterators, calculating size() from begin() to end() is O(n). And no
: > >standard containers provide random-access iterators.
: >
: > Minor quibble: vector<T>::iterator and deque<T>::iterator are
: > random-access. Because of this, SGI's implementation of vector<T>
: > implements size() as end()-begin().  But for set, list, map, etc. you
: > are right...

: Aargh, you are correct. Mea culpa, chapter and verse:

[...]

: It seems that lately I've been spreading more mis-information than
: useful information.

Mee too. The good news is that it's two orders of magnitude
more profitable to say something wrong and get corrected
then to say something right. Yeh, I am selfish, you can tell.

: However, I could *swear* that recently several
: highly-respected C++ guru types asserted here that vectors and deques
: had only bidirectional iterators. I found those claims suspicious, but
: never had time to follow up on them.

I think it was a hallucination, triggered by the guru's saying
that the storage doesn't have to be contiguous. Iterators must
still be of the random-access category. Meaning that +/-
operation must exist and be of a constant time complexity.

: Or perhaps they were talking about something else? But I'm pretty sure
: that the assertion was that you couldn't treat a vector like a "random
: access container." Could it have been strings, not vectors? Since they
: follow the less strict "sequence requirements." I hope.

: [I feel like I'm going through one of those phases when I don't feel
: like I really know what I'm talking about regarding C++ any more. That
: seems to happen once every 6-12 months.

Mee too. No more do I know anything about templates, points
of instantiation, name binding, ``export'', overload resolution,
template parameter deduction, non-type template parameters,
``more specialized'' template functions, iostreams.

: Fortunately, such lapses usually
: occur before a major breakthrough "discovery" about the language, so I'm
: still optimistic.

Let's hope for the best.

: My reply address is correct as-is. The courtesy of providing a correct
: reply address is more important to me than time spent deleting spam.

Right.

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <354F2DF8.2781@wizard.net>#1/1,
  James Kuyper <kuyper@wizard.net> wrote:
>
> Maybe you're thinking about the discussion about whether vector<> could
> contain disconnected blocks of memory. Such an implementation would
> require non-trivial iterators, with an overloaded operator-() that takes
> such discontinuities into effect. However, end()-begin() could still be
> an O(1) operation, so long as the starting index for each section is
> stored with the section. I don't see how operator[] could fail to be
> O(N) with such an implementation, but I may be missing something. Maybe
> they just ignore the fact that the number of sections required is
> proportional to N for large N, when calculating the order of the
> operation.

Or maybe they introduce an added level of indirection (as my older
dynamic array class did), so that insertions, etc. DON'T invalidate
references and pointers to objects in the array.  (Growing a vector
can also be much faster with this implementation, since you only
move pointers, not complex objects.  This was, in fact, my initial
motivation for the implementation.)

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
        +49 (0)69 66 45 33 10    mailto: jkanze@otelo.ibmmail.com
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

JHB NIJHOF wrote:

> Loic.Tregan <Loic.Tregan@cert.fr> wrote:
>
> : > All STL (and ANSI/ISO C++) containers have size() methods.
>
> : ok : same question replacing vector by STL::* ;-)
>
> :  why the count algorithm which does not need to belongs to a container
> : is a standlone procedure, and the size algortihm wich does not need
> : (since it is public - not implementation dependant - that end()-begin()
> : returns the # of element) ? what are the arguments for size wich are not
> : valid for count ???
>
> The basic idea between STL is orthogonality:
> if you have L type of containers, and M types of iterators, and
> N algorithms, instead of defining LxMxN algorithms n that works on
> container type l using iterator type m, you define
> L containers with their methods, with the same public interface,
> and M iterators with their methods, with the same public interface,
> and N algoritms, that work with each of the iterators
> and each of the containers (if sensible, of course; e.g.
> you cannot use a front_insert_iterator on a vector, or a
> bidirectional_iterator on a list).
> But that will only work if all containers have the same public
> members with te same public names.
> Now for instance stable_sort(), defined in <algorithm>, needs
> to know how many elements there are in the containers. Therefore
> it needs a size(), _which has to do the same thing for every type
> of container_.
>
> Now size() belongs in the definition of the container, because
> it has to be calculated differently for every type
> As you say, for a vector it can be calculated easily from begin() and
> end(), but that doesn't work for other containers.
> E.G. for a deque, it is calculated from protected elements:
> finish - start, and for a rope, it returns a member of a protected
> member, and for a list, it is calculated by a call to distance(,
> which is actually defined in <iterator>!
>
> If vectors were the only thing that ever needed sorting,
> stable_sort() could simply use end()-begin(), but they are not,
> so there has to be a container member function size().
>
> On the other hand, count() is an algoritm that belongs in <algorithm>,
> because it is an algorithm that does something with the elements of the
> container. (it counts the number of elements equal to something,
> or satisfying some predicate).
>
> Jeroen Nijhof

Fortunately, it's perfectly feasible to SPECIALIZE an algorithm based on
ITERATOR CATEGORY.
So we're not necessarily stuck with the same algorithm implementation for all
containers/iterators if we don't want to be.

For example, we could implement count() to take just only two arguments
(Iter start, Iter end),
and that runs in O(1) for containers with random access iterators and O(N)
for other containers.

The technique is to break down different algorithms for count-- one using
iterator subtraction, and one using a loop -- into different helper functions
that are distinguished by a third argument, which is of some ITERATOR
CATEGORY.
The main algorithm, count, just returns
count_helper(start, end, iterator_traits<Iter>::iterator_category())
which maps to the correct algorithm based on the actual type of the third
argument.

I wish I could be more explicit here, but this is exactly what Stroustrup's
distance template does in C++ Prog Lang, 3rd Edition, Sect 19.2.3, and to be
any more explicit might stomp on copyrights.


Lance Page


PS:  Stroustrup (in Sect. 17.1.1) agrees with Chuck McCorvey, who wrote:

     All STL (and ANSI/ISO C++) containers have size() methods.




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6ipgpe$4j0$1@mulga.cs.mu.OZ.AU>#1/1,
  fjh@cs.mu.OZ.AU (Fergus Henderson) wrote:
>
> James Kuyper <kuyper@wizard.net> writes:
>
> >Maybe you're thinking about the discussion about whether vector<> could
> >contain disconnected blocks of memory.  Such an implementation would
> >require non-trivial iterators, with an overloaded operator-() that takes
> >such discontinuities into effect. However, end()-begin() could still be
> >an O(1) operation, so long as the starting index for each section is
> >stored with the section. I don't see how operator[] could fail to be
> >O(N) with such an implementation, but I may be missing something. Maybe
> >they just ignore the fact that the number of sections required is
> >proportional to N for large N, when calculating the order of the
> >operation.
>
> I think you're missing something.  Consider an implementation
> in which all the disconnected blocks are the same size, e.g. one page,
> and where the vector itself contains an array of pointers to pages.
>
>  template <class T, ...>
>  class vector {
>   char **page_table;
>   ...
>  };
>
> Then operator[] need just do something like
>
>  T& operator[] (int index) {
>   size_t offset = index * sizeof(T);
>   char *page = this->page_table[offset / PAGE_SIZE];
>   return (T&) page[offset % PAGE_SIZE];
>  }

Although I agree with the principle, I think it's a little more
complicated than that.  I think you'll have problems whenever
sizeof(T) is not a divisor of PAGE_SIZE, and I rather imagine
that the results would not be satisfactory if sizeof(T) were
greater than PAGE_SIZE, either.

Still, my own implementation did something like this.  Growing an
array can be significantly faster, since you only have to copy pointers,
not objects, and of course, growing the array doesn't invalidate
pointers and references into it.  (When I did my own implementation
of dynamic array, before STL, it never even occured to me that you
could violate this principle.  It seems like an invitation to errors.)

I think what may really be needed is something like Herb Sutter's
static_vector, that he discussed once in GotW, in comp.lang.c++.moderated.
A vector with two template arguments, T and the length, which guarantees
that the memory for the elements will be allocated within the vector
itself, and not dynamically.  This guarantee practically removes all
possible motivation for non-contiguous allocation, but it would probably
be a good idea if it were explicitly forbidden.  I'd also like to see
a guarantee that sizeof( vector< T , n > ) == n * sizeof( T ), but
I'm not sure that that is a reasonable thing to put in a standard.
(Maybe a note that this is the intent?)

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
        +49 (0)69 66 45 33 10    mailto: jkanze@otelo.ibmmail.com
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

jkanze@otelo.ibmmail.com wrote:

: I think what may really be needed is something like Herb Sutter's
: static_vector, that he discussed once in GotW, in comp.lang.c++.moderated.
: A vector with two template arguments, T and the length, which guarantees
: that the memory for the elements will be allocated within the vector
: itself, and not dynamically.

Right. It is definitely needed. I once posted a ~12 point list
why it is needed.

: This guarantee practically removes all
: possible motivation for non-contiguous allocation, but it would probably
: be a good idea if it were explicitly forbidden.  I'd also like to see
: a guarantee that sizeof( vector< T , n > ) == n * sizeof( T ), but
: I'm not sure that that is a reasonable thing to put in a standard.
: (Maybe a note that this is the intent?)

Is there any reason not to mandate that the only data member is
a build-in array and nothing else?

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6itiqm$3lc@marianna.psu.edu>,
  zabluda@math.psu.edu (Oleg Zabluda) wrote:
>
> jkanze@otelo.ibmmail.com wrote:
>
> : I think what may really be needed is something like Herb Sutter's
> : static_vector, that he discussed once in GotW, in
comp.lang.c++.moderated.
> : A vector with two template arguments, T and the length, which guarantees
> : that the memory for the elements will be allocated within the vector
> : itself, and not dynamically.
>
> Right. It is definitely needed. I once posted a ~12 point list
> why it is needed.
>
> : This guarantee practically removes all
> : possible motivation for non-contiguous allocation, but it would probably
> : be a good idea if it were explicitly forbidden.  I'd also like to see
> : a guarantee that sizeof( vector< T , n > ) == n * sizeof( T ), but
> : I'm not sure that that is a reasonable thing to put in a standard.
> : (Maybe a note that this is the intent?)
>
> Is there any reason not to mandate that the only data member is
> a build-in array and nothing else?

Just the general principle that you want to mandate as little as
possible, in order to give the implementors as much freedom as possible.

The wording must be such as to allow the internal data member to be
declared as raw memory, and initialized in the constructor using the
copy constructor of the type in question.  This is less trivial than
it seems, since there is no fully standard conforming way of doing this,
and the only reasonably portable way I know of may in some rare cases
cause the objects to be larger than they would be otherwise.

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
        +49 (0)69 66 45 33 10    mailto: jkanze@otelo.ibmmail.com
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung


-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Bradd W. Szonye wrote:
>
> Joe Buck wrote:
> >
> > Bradd W. Szonye <bradds@concentric.net> wrote:
> > >I suspect that size() is a member function so that it has an O(1) and
> > >not O(n) implementation. For all iterators except random-access
> > >iterators, calculating size() from begin() to end() is O(n). And no
> > >standard containers provide random-access iterators.
> >
> > Minor quibble: vector<T>::iterator and deque<T>::iterator are
> > random-access. Because of this, SGI's implementation of vector<T>
> > implements size() as end()-begin().  But for set, list, map, etc. you
> > are right...
>
> Aargh, you are correct. Mea culpa, chapter and verse:
>
>   23.2.1  Template class deque                               [lib.deque]
> 1 A deque is a kind of sequence that, like a vector (_lib.vector_), sup-
>   ports random access iterators.  In addition, it supports constant time
>   insert  and  erase  operations at the beginning or the end; insert and
>   erase in the middle take linear time.  That is, a deque is  especially
>   optimized  for  pushing and popping elements at the beginning and end.
>   As with vectors, storage management is handled automatically.
>
> Similar stuff appears at lib.vector. And it's the same in both CD2 and
> FDIS, so it's not a "wrong version" problem either.
>
> It seems that lately I've been spreading more mis-information than
> useful information. However, I could *swear* that recently several
> highly-respected C++ guru types asserted here that vectors and deques
> had only bidirectional iterators. I found those claims suspicious, but
> never had time to follow up on them.
>
> Or perhaps they were talking about something else? But I'm pretty sure
> that the assertion was that you couldn't treat a vector like a "random
> access container." Could it have been strings, not vectors? Since they
> follow the less strict "sequence requirements." I hope.

Maybe you're thinking about the discussion about whether vector<> could
contain disconnected blocks of memory. Such an implementation would
require non-trivial iterators, with an overloaded operator-() that takes
such discontinuities into effect. However, end()-begin() could still be
an O(1) operation, so long as the starting index for each section is
stored with the section. I don't see how operator[] could fail to be
O(N) with such an implementation, but I may be missing something. Maybe
they just ignore the fact that the number of sections required is
proportional to N for large N, when calculating the order of the
operation.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> writes:

>Maybe you're thinking about the discussion about whether vector<> could
>contain disconnected blocks of memory.  Such an implementation would
>require non-trivial iterators, with an overloaded operator-() that takes
>such discontinuities into effect. However, end()-begin() could still be
>an O(1) operation, so long as the starting index for each section is
>stored with the section. I don't see how operator[] could fail to be
>O(N) with such an implementation, but I may be missing something. Maybe
>they just ignore the fact that the number of sections required is
>proportional to N for large N, when calculating the order of the
>operation.

I think you're missing something.  Consider an implementation
in which all the disconnected blocks are the same size, e.g. one page,
and where the vector itself contains an array of pointers to pages.

 template <class T, ...>
 class vector {
  char **page_table;
  ...
 };

Then operator[] need just do something like

 T& operator[] (int index) {
  size_t offset = index * sizeof(T);
  char *page = this->page_table[offset / PAGE_SIZE];
  return (T&) page[offset % PAGE_SIZE];
 }

--
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Loic.Tregan wrote:
>
>  why the count algorithm which does not need to belongs to a container
> is a standlone procedure, and the size algortihm wich does not need
> (since it is public - not implementation dependant - that
> end()-begin() returns the # of element) ? what are the arguments for
> size wich are not valid for count ???

I suspect that size() is a member function so that it has an O(1) and
not O(n) implementation. For all iterators except random-access
iterators, calculating size() from begin() to end() is O(n). And no
standard containers provide random-access iterators. On the other hand,
if the container tracks the size itself (or can calculate it more
simply), it can provide size() in O(1) time.

Thus, size() exists so that users can find the size of a container in
constant rather than linear time.
--
Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds

My reply address is correct as-is. The courtesy of providing a correct
reply address is more important to me than time spent deleting spam.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Loic.Tregan <Loic.Tregan@cert.fr> wrote:

: > All STL (and ANSI/ISO C++) containers have size() methods.

: ok : same question replacing vector by STL::* ;-)

:  why the count algorithm which does not need to belongs to a container
: is a standlone procedure, and the size algortihm wich does not need
: (since it is public - not implementation dependant - that end()-begin()
: returns the # of element) ? what are the arguments for size wich are not
: valid for count ???

The basic idea between STL is orthogonality:
if you have L type of containers, and M types of iterators, and
N algorithms, instead of defining LxMxN algorithms n that works on
container type l using iterator type m, you define
L containers with their methods, with the same public interface,
and M iterators with their methods, with the same public interface,
and N algoritms, that work with each of the iterators
and each of the containers (if sensible, of course; e.g.
you cannot use a front_insert_iterator on a vector, or a
bidirectional_iterator on a list).
But that will only work if all containers have the same public
members with te same public names.
Now for instance stable_sort(), defined in <algorithm>, needs
to know how many elements there are in the containers. Therefore
it needs a size(), _which has to do the same thing for every type
of container_.

Now size() belongs in the definition of the container, because
it has to be calculated differently for every type
As you say, for a vector it can be calculated easily from begin() and
end(), but that doesn't work for other containers.
E.G. for a deque, it is calculated from protected elements:
finish - start, and for a rope, it returns a member of a protected
member, and for a list, it is calculated by a call to distance(,
which is actually defined in <iterator>!

If vectors were the only thing that ever needed sorting,
stable_sort() could simply use end()-begin(), but they are not,
so there has to be a container member function size().

On the other hand, count() is an algoritm that belongs in <algorithm>,
because it is an algorithm that does something with the elements of the
container. (it counts the number of elements equal to something,
or satisfying some predicate).

Jeroen Nijhof
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Bradd W. Szonye <bradds@concentric.net> wrote:
>I suspect that size() is a member function so that it has an O(1) and
>not O(n) implementation. For all iterators except random-access
>iterators, calculating size() from begin() to end() is O(n). And no
>standard containers provide random-access iterators.

Minor quibble: vector<T>::iterator and deque<T>::iterator are random-access.
Because of this, SGI's implementation of vector<T> implements size() as
end()-begin().  But for set, list, map, etc. you are right that

>Thus, size() exists so that users can find the size of a container in
>constant rather than linear time.

--
-- Joe Buck
   work: jbuck@synopsys.com, otherwise jbuck@welsh-buck.org or jbuck@best.net
http://www.welsh-buck.org/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Joe Buck wrote:
>
> Bradd W. Szonye <bradds@concentric.net> wrote:
> >I suspect that size() is a member function so that it has an O(1) and
> >not O(n) implementation. For all iterators except random-access
> >iterators, calculating size() from begin() to end() is O(n). And no
> >standard containers provide random-access iterators.
>
> Minor quibble: vector<T>::iterator and deque<T>::iterator are
> random-access. Because of this, SGI's implementation of vector<T>
> implements size() as end()-begin().  But for set, list, map, etc. you
> are right...

Aargh, you are correct. Mea culpa, chapter and verse:

  23.2.1  Template class deque                               [lib.deque]
1 A deque is a kind of sequence that, like a vector (_lib.vector_), sup-
  ports random access iterators.  In addition, it supports constant time
  insert  and  erase  operations at the beginning or the end; insert and
  erase in the middle take linear time.  That is, a deque is  especially
  optimized  for  pushing and popping elements at the beginning and end.
  As with vectors, storage management is handled automatically.

Similar stuff appears at lib.vector. And it's the same in both CD2 and
FDIS, so it's not a "wrong version" problem either.

It seems that lately I've been spreading more mis-information than
useful information. However, I could *swear* that recently several
highly-respected C++ guru types asserted here that vectors and deques
had only bidirectional iterators. I found those claims suspicious, but
never had time to follow up on them.

Or perhaps they were talking about something else? But I'm pretty sure
that the assertion was that you couldn't treat a vector like a "random
access container." Could it have been strings, not vectors? Since they
follow the less strict "sequence requirements." I hope.

[I feel like I'm going through one of those phases when I don't feel
like I really know what I'm talking about regarding C++ any more. That
seems to happen once every 6-12 months. Fortunately, such lapses usually
occur before a major breakthrough "discovery" about the language, so I'm
still optimistic. It could also just mean that I've spent too much time
lately programming and not enough being a language lawyer, alas. :)]

Anyway, I'll still stand by my original claim that size() makes sense in
library containers, by the way. Even if some of the containers do
provide for size calculation with end()-begin(), not all of them do. I'd
hate to write a nice generic algorithm for bidirectional containers that
has to count elements at some point, and then suddenly realize that it
adds O(n) to an inner loop when used on lists or sets. Whether it's
really THAT important to do size bookkeeping on the linked containers is
debatable, but I'd wager that there's enough demand for it that it's a
good container requirement to provide size().
--
Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds

My reply address is correct as-is. The courtesy of providing a correct
reply address is more important to me than time spent deleting spam.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Lo   c Tr   gan wrote in message <6hptfn$ldv$1@news3.isdnet.net>...
>I've seen in RogueWave::STL a vector::size() function.
>First, I think it is not logical, since only public functionnalities of
>vector is needed to compute the size, so a stand-alone function
>count(vector<T>) should be more appropriate than a method.
>Second, it looks not coherent with the choice of the count (or find,...)
>algorithm, wich is not a method.

All STL (and ANSI/ISO C++) containers have size() methods.
--
Chuck McCorvey
Creative SolutionWare, Inc.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Chuck McCorvey wrote:
>=20
> Lo=EFc Tr=E9gan wrote in message <6hptfn$ldv$1@news3.isdnet.net>...
> >I've seen in RogueWave::STL a vector::size() function.
> >First, I think it is not logical, since only public functionnalities o=
f
> >vector is needed to compute the size, so a stand-alone function
> >count(vector<T>) should be more appropriate than a method.
> >Second, it looks not coherent with the choice of the count (or find,..=
.)
> >algorithm, wich is not a method.
>=20
> All STL (and ANSI/ISO C++) containers have size() methods.

ok : same question replacing vector by STL::* ;-)

 why the count algorithm which does not need to belongs to a container
is a standlone procedure, and the size algortihm wich does not need
(since it is public - not implementation dependant - that end()-begin()
returns the # of element) ? what are the arguments for size wich are not
valid for count ???
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <3545C0E5.4047@cert.fr>, Loic.Tregan <Loic.Tregan@cert.fr> wrote:

>  why the count algorithm which does not need to belongs to a container
> is a standlone procedure, and the size algortihm wich does not need
> (since it is public - not implementation dependant - that end()-begin()
> returns the # of element) ? what are the arguments for size wich are not
> valid for count ???

You cannot compute end()-begin() for a list, because list iterators
are not random-access iterators.  The only way to determine the number
of elements in a list are either to count them (order n) or for the list
data structure itself to include a count (order 1).
--
    --Andrew Koenig
      ark@research.att.com
      http://www.research.att.com/info/ark



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I've seen in RogueWave::STL a vector::size() function.
First, I think it is not logical, since only public functionnalities of
vector is needed to compute the size, so a stand-alone function
count(vector<T>) should be more appropriate than a method.
Second, it looks not coherent with the choice of the count (or find,...)
algorithm, wich is not a method.




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]