Christopher Eltschka wrote:
>
> James Kuyper wrote:
> >
> > Paul D. DeRocco wrote:
> > >
> > > James Kuyper wrote:
> > > >
> > > > If a vector<T>::iterator is anything other than a T* (which it
must
> > > > be, to implement non-contiguous storage), I don't see what any
> > > > implementation can do to allow a non-C++ function to access the
> > > > contents
> > > > of that container. The non-C++ code has no way of executing the
member
> > > > funcions needed to access those contents
> > >
> > > The implementation could provide a regular extern "C" function
that gets
> > > a regular pointer. Or, it could be left up to the C++ caller to
get the
> > > pointer and pass it to the C code. But this would only be possible
if
> > > the underlying implementation was contiguous.
> >
> > The message I was responding to claimed that this was feasible,
whether
> > or not vector<> is contiguous. The solution is, of course, quite
trivial
> > with contiguous storage. However, I was pointing out that it is far
from
> > trivial, and perhaps impossible, in the case of non-contiguous
storage.
>
> The problem to access the members of a vector from other languages is
> easy:
>
> vector<X> v;
>
> extern "C" X* getX(int index)
> {
>   if (index<0 || index>v.size())
>     return NULL;
>   return &v[index];
> }

Under the specified assumption of non-contiguous storage, getX() will
return a pointer which can only be guaranteed useful for the one item at
the specified index. How does this solve the problem of getting a
pointer that can be passed to a third party C function, which needs a
pointer to the entire array? As third party software, it cannot be
re-written to call getX(). Even if it could, the result would be
replacing a simple memory access with a function call; this is not
something you want to do with time-critical software, such as many
systems functions. Finally, re-writing the code to call getX()
hard-wires that function to your object, unless you're talking about
implementing a callback interface.

> There could also be a GetFirstX/GetNextX interface with opaque
> pointers (which indeed just point to iterators) to allow faster
> iteration from other languages. Indeed, this would even reduce
> the dependency on actual implementation (there need not be a
> "real" iterator behind; the opaque pointers could point to the
> objects themselves for contiguous memory, or they could point
> to the nodes for lists. They could even contain no pointers at
> all, but other data that fits, since you never dereference them
> in your program).

That option is useless when calling third party functions that expect a
pointer to a specified non-C++ type, which is not an opaque pointer.

> Indeed, the problem only arises the other way round: You *have*
already
> a function taking a pointer and an element count, and want to store
> your data in a vector and pass that data to that function.

I'm confused by your statement; your "other way around" was the problem
I'm referring to. When you're free to re-write both the C and the C++
code, the problem is trivial; why did you assume I was talking about the
trivial case? That's not what this thread has been about.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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> wrote:
>Christopher Eltschka wrote [mod whitespace-edits]:
>> vector<X> v;
>> extern "C" X* getX(int index) {
>>   if (index<0 || index>v.size())
>>     return NULL;
>>   return &v[index];
>> }
>
>Under the specified assumption of non-contiguous storage, getX() will
>return a pointer which can only be guaranteed useful for the one item at
>the specified index.

Right, but there's another problem: The above code won't always work.

In short, vector<T,...>::operator[] doesn't necessarily return a T&. If
you use a custom allocator, vector<T,MyAlloc>::operator[] returns a
MyAlloc::reference. One of two bad things can happen: The expression
"&v[index]" may not be legal; or, worse, it may be legal but not mean
what
you think.

* When "&v[index]" is not legal:

If it's not possible to take the address of whatever a
MyAlloc::reference
is, then "&v[index]" is not legal.

* When "&v[index]" is legal, but doesn't mean what you think:

A popular idiom is to make MyAlloc::reference (and therefore
operator[]'s
return value) a "reference-like" proxy object, one that has suitable
operators defined for doing work on the elements contained in the
vector.
If the allocator uses this kind of idiom, it can mean that "&v[index]"
can
end up inadvertently taking the address of a temporary object. (I say
"can" because the proxy might have operator& defined, and in a way
that's
sensible for this usage. Then again, it might not (either define it, or
in
an appropriate way).)

David Abrahams wrote:
>
> That requirement doesn't imply contiguity at all. The trick of storing
> pointers to elements still works; you're just required to do something
> which calls T's assignment operator the right number of times. One
> (perverse) way to fulfill that requirement would be to assign the last
> element to itself over and over.

Yeah, but it's a perverse way. The requirement suggests to me that the
standard writers _intended_ the implementation to be contiguous. If they
didn't, they'd have simply _allowed_ erase() to call the copy
constructor that number of times.

> One side-effect of requiring contiguity for vector<> would be that in
> a "large model" x86 program, a vector<T> would be limited to roughly
> 65536/sizeof(T) elements, while all other containers would only be
> limited by available memory. That quirky assymmetry makes it quite
> difficult to write portable programs.

True. Fortunately, 16-bit x86 code is dying out, and nothing else out
there seems to have those particular quirks.

> Perhaps if contiguity were required, we could encourage vendor
> extensions which produce possibly non-contiguous but more capacious
> vectors.

I agree. In fact, one might wish string objects to be guaranteed
contiguous, to make c_str efficient, leaving it to alternative
containers (like SGI's rope) for fancier stuff.

--

Ciao,
Paul

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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 wrote:
>
> Christopher Eltschka wrote:
> >
> > James Kuyper wrote:
> > >
> > > Paul D. DeRocco wrote:
> > > >
> > > > James Kuyper wrote:
> > > > >
> > > > > If a vector<T>::iterator is anything other than a T* (which it
> must
> > > > > be, to implement non-contiguous storage), I don't see what any
> > > > > implementation can do to allow a non-C++ function to access the
> > > > > contents
> > > > > of that container. The non-C++ code has no way of executing the
> member
> > > > > funcions needed to access those contents
> > > >
> > > > The implementation could provide a regular extern "C" function
> that gets
> > > > a regular pointer. Or, it could be left up to the C++ caller to
> get the
> > > > pointer and pass it to the C code. But this would only be possible
> if
> > > > the underlying implementation was contiguous.
> > >
> > > The message I was responding to claimed that this was feasible,
> whether
> > > or not vector<> is contiguous. The solution is, of course, quite
> trivial
> > > with contiguous storage. However, I was pointing out that it is far
> from
> > > trivial, and perhaps impossible, in the case of non-contiguous
> storage.
> >
> > The problem to access the members of a vector from other languages is
> > easy:
> >
> > vector<X> v;
> >
> > extern "C" X* getX(int index)
> > {
> >   if (index<0 || index>v.size())
> >     return NULL;
> >   return &v[index];
> > }
>
> Under the specified assumption of non-contiguous storage, getX() will
> return a pointer which can only be guaranteed useful for the one item at
> the specified index. How does this solve the problem of getting a
> pointer that can be passed to a third party C function, which needs a
> pointer to the entire array? As third party software, it cannot be
> re-written to call getX(). Even if it could, the result would be
> replacing a simple memory access with a function call; this is not
> something you want to do with time-critical software, such as many
> systems functions. Finally, re-writing the code to call getX()
> hard-wires that function to your object, unless you're talking about
> implementing a callback interface.
>
> > There could also be a GetFirstX/GetNextX interface with opaque
> > pointers (which indeed just point to iterators) to allow faster
> > iteration from other languages. Indeed, this would even reduce
> > the dependency on actual implementation (there need not be a
> > "real" iterator behind; the opaque pointers could point to the
> > objects themselves for contiguous memory, or they could point
> > to the nodes for lists. They could even contain no pointers at
> > all, but other data that fits, since you never dereference them
> > in your program).
>
> That option is useless when calling third party functions that expect a
> pointer to a specified non-C++ type, which is not an opaque pointer.
>
> > Indeed, the problem only arises the other way round: You *have*
> already
> > a function taking a pointer and an element count, and want to store
> > your data in a vector and pass that data to that function.
>
> I'm confused by your statement; your "other way around" was the problem
> I'm referring to. When you're free to re-write both the C and the C++
> code, the problem is trivial; why did you assume I was talking about the
> trivial case? That's not what this thread has been about.

Well, you're right, I've got confused. I was under the misconception
that this partial thread was based on the following (in
<6k3jth$jl3@netlab.cs.rpi.edu> from Peter Garner:

--8<--
This would of course mean rewriting almost every
OS in existance and totally do away with the C language, since it
would not be useful on an OS whose system calls relied on the STL!
;-)
--8<--

Since all functions using the OS (including those written in C)
are written later than the OS, in this case my statement apply.

This shows the danger of posting late in the evening ;-)

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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              ]

Herb Sutter<herbs@cntc.com> wrote:
>James Kuyper <kuyper@wizard.net> wrote:
>>Christopher Eltschka wrote [mod whitespace-edits]:
>>> vector<X> v;
>>> extern "C" X* getX(int index) {
>>>   if (index<0 || index>v.size())
>>>     return NULL;
>>>   return &v[index];
>>> }
>
>... there's another problem: The above code won't always work.
>
>In short, vector<X,...>::operator[] doesn't necessarily return a X&.
>If you use a custom allocator, vector<X,MyAlloc>::operator[] returns a
>MyAlloc::reference. One of two bad things can happen: The expression
>"&v[index]" may not be legal; or, worse, it may be legal but not mean
>what you think.

Sorry, this is not right.  MyAlloc::reference is required to be X&.
However, operator& might be overloaded for type X, yielding something
that might not be a X*; or it might be private.  But if you define the
type X involved, you can determine that.

Not that any of this helps people trying to extract useful pointers
from std::vector<X>...

Listen: std::vector<> in the standard is just an example.  Why not
grab the free SGI code, rename it, and use that?  Then you will be
certain of its semantics, regardless of what your compiler provides
for std::vector<>.  (The only license restriction is that you must
leave in the copyright notices.)

This is the case for any standard container, or algorithm: what is
essential is the Iterator interface; everything else is just examples.
If they don't do precisely what you want, you are absolutely free to
use something else that does.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 wrote:
>On the other hand, if you use the default allocator<T>, you're safe
>because allocator<T>::reference is a typedef for a plain old T&. Then
>all you have to remember is to account for the lifetimes of references
>if the vector is changed.

Of course, a specialization of allocator<T> might not typedef it as T&,
but then I don't think it's allowed for a user to specialize allocator<T>
under the "can't extend namespace std" rule.

---
Herb Sutter (mailto:herbs@cntc.com)

Current Network Technologies Corp  2695 North Sheridan Way, Suite 150
www.cntc.com www.peerdirect.com    Mississauga Ontario Canada L5K 2N6

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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              ]

Herb Sutter writes:
> vector<T,...>::operator[] doesn't necessarily return a T&.

Yes it does.

> If you use a custom allocator, vector<T,MyAlloc>::operator[]
> returns a MyAlloc::reference.

Yes, and according to the allocator requirements MyAlloc<T>::reference
must be T&.

Greg Colvin




[ 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              ]

herbs@cntc.com (Herb Sutter) writes:

> Right, but there's another problem: The above code won't always work.
>
> In short, vector<T,...>::operator[] doesn't necessarily return a T&. If
> you use a custom allocator, vector<T,MyAlloc>::operator[] returns a
> MyAlloc::reference. One of two bad things can happen: The expression
> "&v[index]" may not be legal; or, worse, it may be legal but not mean
> what
> you think.

MyAlloc::reference must always be MyAlloc::value_type&.  The allocator
requirements do not give users the freedom to define alternate
reference types.  (See lines 3 and 4 of Table 32, in section 20.1.5.)

There's a reason for that: alternate reference types just don't work
very well.  First, they interact poorly with class types, since it's
impossible to redefine "operator.".  Second, they interact poorly with
call by reference.  Functions that are defined to use call by
reference, and that take arguments of type T&, do very strange things
when you pass them proxy reference objects.

You can use proxy references, sometimes, more or less, but they don't
fit naturally into the structure of the STL.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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              ]

Herb Sutter<herbs@cntc.com> wrote:
>I wrote:
>>On the other hand, if you use the default allocator<T>, you're safe
>>because allocator<T>::reference is a typedef for a plain old T&. Then
>>all you have to remember is to account for the lifetimes of references
>>if the vector is changed.
>
>Of course, a specialization of allocator<T> might not typedef it as T&,
>but then I don't think it's allowed for a user to specialize allocator<T>
>under the "can't extend namespace std" rule.

No, you *are* allowed to specialize allocator<T> for your own type T.
However, if it doesn't conform to the Allocator requirements, then
standard container behavior is undefined.  The Allocator requirements
are clear that allocator<T>::reference must be identical to T&.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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 thought that write was in the user namespace, in which case, the
|implementation doesn't have a right to provide it.

The implementation can provide anything it wants to as long as that
doesn't interfere with its operation as a conforming implementation.

In this case, for instance, an implementation can certainly provide
a function called write() and provide a declaration for it in
a header outside the scope of the C++ standard, say <unistd.h>.
If the programmer includes <unistd.h>, she has stepped outside
the C++ standard, so the implementation can provide write().
If she does not include it, there won't be a declaration for it,
and any attempt to use it would result in a diagnostic, as required.
The implementation only has to ensure that if she does not include
<unistd.h> and provides her own write() that she gets the correct
one, and that's really not too tricky.
--
To reply by mail, please remove "mail." from my address -- but please
send e-mail or post, not both

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

Valentin Bonnard wrote:
>
> The idea behind deque is that it can grow in both directions,
> whereas vector only grow in one direction; also deque has an
> extra level of indirection. This gives differents
> complexity requirements.

If the number of levels of indirection is fixed (e.g., one), then the
complexity requirement is the same. A log term is only introduced when
the number of levels of indirection grows with the log of the total size
of the container, as with a b-tree.

--

Ciao,
Paul

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

bs@research.att.com (Bjarne Stroustrup) writes:

|>  I suggested to the person who originally raised the issue of contiguous
|>  allocation of vector elements that he ask for clarification from the C++
|>  standards commitee through his national standards body. This has been done
|>  so that this issue will be officially settled in due course.
|>
|>  Until then, I will personally assume vector elements to be allocated contiguously
|>  despite the lack of a firm promise and despite the arguments brought forward
|>  to the effect that there should be no such guarantee. For me at least, the
|>  problems of not using vector vector elements directly from C-style routines
|>  outweights the worry that the committee might come to a conclusion different
|>  from mine (and it might, I do not claim to have fathomed every detail of this
|>  issue - one reason to have a formal standards group is to look deeper into
|>  issues that an individual is likely to do).

As a result of this discussion, I've changed my opinion, and think that
vector should guarantee contiguous allocation.  Never the less, I cannot
see any way of interpreting the standard to ensure this.  Just how much
liberty does the committee have in "clarifying"?

In the meantime, the fact that you have formally suggested that people
count on this "implementation detail" should provide a powerful
incentive for implementors not to do it otherwise.

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung
---
[ 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              ]

> True, but write() exists on all implementations which support POSIX.1,
> which makes it important, and even on implementations which don't
> support
> POSIX.1 there are other functions similar to write() for which the

Yes, just to further support your point there are indeed a huge amount
of legacy functions that take a pointer (array) and a count.  An array
is one of the simplest and most common data structures in use.  I am
afraid that if the standards committee eventually fails to either
clarify vectors in favour of contigous storage, OR provide an STL
class that DOES allow itself to substitute for an array in all of the
**ix system calls, etc., then we are left with a standard library that
fails to support one of the simplest and most common data structures
in use!  I do not think that someone's statement "well those functions
should be rewritten to take a vector and an iterator" was meant in
anything but jest.  This would of course mean rewriting almost every
OS in existance and totally do away with the C language, since it
would not be useful on an OS whose system calls relied on the STL!
;-)

Peace

Peter


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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              ]

Andrew Koenig wrote:
>
> In article <6jfe5i$5c1@netlab.cs.rpi.edu>,
> Theodore Todorov  <todorov@sbghp10.in2p3.fr> wrote:
>
> >   2) vector<T> is _not_ usable as an interface to non-C++ functions
> >       (like write()), mainly because of the absence of a guarantee
> >      for contiguos storage.
>
> Whether vector<T> is usable as an interface to non-C++ functions
> is up to the implementation.  This state of affairs holds whether
> or not vector<T> is guaranteed to use contiguous storage.  For that
> matter, it is up to the implementation whether or not write() exists.

If a vector<T>::iterator is anything other than a T* (which it must be,
to implement non-contiguous storage), I don't see what any
implementation can do to allow a non-C++ function to access the contents
of that container. The non-C++ code has no way of executing the member
funcions needed to access those contents (except possibly by calling
them through their mangled names - not exactly a feasible option for
third-party software).

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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              ]

On 22 May 98 16:44:04 GMT, "Paul D. DeRocco" <pderocco@ix.netcom.com>
wrote:

>greg wrote:
>>
>> The standard places very stringent requirements on the complexity of
>> vector operations, and a very experienced and skillful implementer
>> once told me that he knew of no other way to meet those requirements.
>> I've certainly never seen any other conforming implementation.  So I
>> don't think implementers need the freedom to use other
>> implementations.
>
>I don't know what the official standard says, but the draft standard
>says something that everyone in this discussion has missed. In 23.2.4.3
>[lib.vector.modifiers], it says:
>
>  iterator erase(iterator position);
>  iterator erase(iterator first, iterator last);
>
>  Effects:
>    Invalidates all the iterators and references after the point of  the
>    erase.
>  Complexity:
>    The  destructor of T is called the number of times equal to the num-
>    ber of the elements erased, but the  assignment  operator  of  T  is
>    called  the  number  of times equal to the number of elements in the
>    vector after the erased elements.
>
>The last clause states a requirement that would further imply
>contiguity. For instance, the trick of storing pointers to elements, so
>that the elements wouldn't have to move, would violate that clause,
>since the assignment operator wouldn't be called at all.

That requirement doesn't imply contiguity at all. The trick of storing
pointers to elements still works; you're just required to do something
which calls T's assignment operator the right number of times. One
(perverse) way to fulfill that requirement would be to assign the last
element to itself over and over.

>I've looked at the complexity requirements of deque and vector, and it
>seems to me that (given reasonable implementations) it should be
>possible to require contiguity of storage for vector, while leaving
>those situations where contiguity is a bad idea, to use deque instead.

>Conversely, if vector is allowed to be noncontiguous, I see no
>capability or benefit that vector provides that isn't also provided by
>deque (or couldn't easily be added). In other words, if vector isn't
>stored contiguously, what do we need it for?

Deque doesn't fulfill some of the requirements of vector (notably
those involving reserve()). But yes, deque could be extended in that
way.

The answers to your questions depend on what you think vector<> is an
abstraction of. If you think it's an abstraction of C-style arrays,
then it makes sense to require contiguity. If you think it's an
abstraction of a linearly-addressable container, then maybe it
doesn't.

One side-effect of requiring contiguity for vector<> would be that in
a "large model" x86 program, a vector<T> would be limited to roughly
65536/sizeof(T) elements, while all other containers would only be
limited by available memory. That quirky assymmetry makes it quite
difficult to write portable programs.

Weighed against the existence of huge quantities of legacy code which
uses C-style arrays, I guess the issue of being able to use large
vectors on architectures which will one day be obsolete seems
relatively minor, but it's something that should be considered.

Perhaps if contiguity were required, we could encourage vendor
extensions which produce possibly non-contiguous but more capacious
vectors.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

john@mail.interlog.com (John R MacMillan) writes:

|>  |I thought that write was in the user namespace, in which case, the
|>  |implementation doesn't have a right to provide it.
|>
|>  The implementation can provide anything it wants to as long as that
|>  doesn't interfere with its operation as a conforming implementation.
|>
|>  In this case, for instance, an implementation can certainly provide
|>  a function called write() and provide a declaration for it in
|>  a header outside the scope of the C++ standard, say <unistd.h>.
|>  If the programmer includes <unistd.h>, she has stepped outside
|>  the C++ standard, so the implementation can provide write().
|>  If she does not include it, there won't be a declaration for it,
|>  and any attempt to use it would result in a diagnostic, as required.
|>  The implementation only has to ensure that if she does not include
|>  <unistd.h> and provides her own write() that she gets the correct
|>  one, and that's really not too tricky.

The implementation also has to ensure that the users write is not called
instead of the system write by filebuf; the problem is a little bit
trickier, but the solutions are known.

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

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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              ]

On 12 May 1998 16:24:36 GMT, "greg" <yo@mama.com> wrote:

>Andrew Koenig <ark@research.att.com> wrote in article
><6j6isj$61s@netlab.cs.rpi.edu>...
>> In article <6isd34$sgo@netlab.cs.rpi.edu>,
>> Jim Barry <jim.barry@bigfoot.com> wrote:
>>
>> > If vectors cannot be assumed to be contiguous, they cannot be used
>> > with functions that take a pointer and an element count, which is a
>> > very common scenario.
>>
>> You're quite correct.  Such functions should be rewritten to take
>> a vector iterator and an element count.
>
>Except that if those functions belong to a third party, such as your OS
>vendor, you can't rewrite them.  So perhaps it would have been better
>for the vector<T> iterator type to be specified as T*.  I expect that
>this will be true of enough implementations, and assumed by enough code,
>to become a problem.
>
>Greg Colvin

Unfortunately, I agree that it will probably become a problem, but
let's not use that likelihood to condone the use of
vector<>::iterators interchangeably with T*. There are useful vector<>
implementations which don't use T* iterators. For example, the STLPort
with full iterator validity debugging enabled substitutes a class for
vector<>::iterator. Programmers shouldn't assume the implementation of
vector<> lest they cut off some powerful options in the future.

-Dave

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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 <Et3t00.CDu@research.att.com>, ark@research.att.com (Andrew Koenig) writes:
> In article <199805120621.IAA06855@lnzx05.co.at>,
> Zeisel Helmut <zeisel@lnzx16.vai.co.at> wrote:
>
> > > You're quite correct.  Such functions should be rewritten to take
> > > a vector iterator and an element count.
>
> > And what is the recommended solution if that function
> > cannot be changed because it is part of a third party C library?
> > valarray??????
>
> The same solution as when a third-party function has any
> other portability bug.  There is nothing special about this
> particular problem.

I would not say that this is a "portability bug",
AFAIK pointer and element count is the quasi-standard interface
in languages such as
C and FORTRAN, and is used in Numerical Recipes,
IMSL, LAPACK, NAGLIB, BLAS, and so on.
I do not know any better solution for the function interface
in C and FORTRAN.

The "special" about this particular problem is that it is not a
"particular" problem, but a very common one.

Since

1) C++ is designed to be cooperative with other languages
 and existing code and libraries, and
2) The aim of the standard C++ library is to provide
 comfortable solutions for "standard" problems,

I would have expected that some "cooperative" vector class
is part of the standard library.

Of course I known Barton & Nackman an can user their vector classes
to write my wrapper classes; nevertheless, I would have expected
to get better support from the C++ standard library.

Helmut Zeisel


[ 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              ]

> Does valarray satisfy your needs?
> (My compiler does not yet support valarray,
> so I am not so familiar to it)

As I understand, valarray is just a vector optimised for numerical
use.  Although for some reason people keep discussing it as the
solution to all of this bugaboo about (IHMO the standards committees
gross oversight) whether vectors are contiguous.  Just out of
curiosity has any one ON the standards committee responded to this?

thanks

Peter



[ 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              ]

ark@research.att.com (Andrew Koenig) writes:

>In article <199805120621.IAA06855@lnzx05.co.at>,
>Zeisel Helmut <zeisel@lnzx16.vai.co.at> wrote:
>
>> > You're quite correct.  Such functions should be rewritten to take
>> > a vector iterator and an element count.
>
>> And what is the recommended solution if that function
>> cannot be changed because it is part of a third party C library?
>> valarray??????
>
>The same solution as when a third-party function has any
>other portability bug.  There is nothing special about this
>particular problem.

Excuse me, I must be missing something.  If third-party code has a
portability problem, then the usual thing to do is to fix the
portability problem (or ask the vendor to do so, etc.).  In this case,
the third-party code does not have a portability problem, so I don't
see how we can apply the same solution here.

--
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              ]

ark@research.att.com (Andrew Koenig) writes:

>In article <6jfe5i$5c1@netlab.cs.rpi.edu>,
>Theodore Todorov  <todorov@sbghp10.in2p3.fr> wrote:
>
>>   2) vector<T> is _not_ usable as an interface to non-C++ functions
>>       (like write()), mainly because of the absence of a guarantee
>>      for contiguos storage.
>
>Whether vector<T> is usable as an interface to non-C++ functions
>is up to the implementation.  This state of affairs holds whether
>or not vector<T> is guaranteed to use contiguous storage.

I don't think that is the case.  If I know that vector<T> guarantees
contiguous storage, then I can write code such as

 vector<int> v;
 ...
 write(fd, &v[0], v.size() * sizeof(int));

and this will work regardless of the implementation, so long as the
implementation conforms to the C++ standard, the requirement about
vectors using contiguous storage, and POSIX.1.  Thus vector<T>
is usable as an interface to non-C++ functions such as write().

>For that
>matter, it is up to the implementation whether or not write() exists.

True, but write() exists on all implementations which support POSIX.1,
which makes it important, and even on implementations which don't
support
POSIX.1 there are other functions similar to write() for which the
same problem can arise.  For example, the same problem arises if you
are trying to interface with other languages such as Fortran.

--
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.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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 <6jkivf$s5n@netlab.cs.rpi.edu>, greg <yo@mama.com> wrote:

> The standard places very stringent requirements on the complexity of
> vector operations, and a very experienced and skillful implementer
> once told me that he knew of no other way to meet those requirements.

I could easily implement a vector so that the elements are contiguous
but in the opposite order from what you would expect.  That would certainly
meet all the performance requirements.
--
    --Andrew Koenig
      ark@research.att.com
      http://www.research.att.com/info/ark


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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 <6jfe5i$5c1@netlab.cs.rpi.edu>, Theodore Todorov <todorov@sbghp10.in2p3.fr> writes:
 >
 > So what we need is a new container, array<T>, which is essentially
 > a vector with contiguous storage and possibly iterators convertible
 > to pointers

In article <MDRLdUlulsRd-pn2-VQU0SMKHoz3i@pn-dialkn1-6.primary.net>, peter.garner@toward.com (Peter Garner) writes:
>
> > Does valarray satisfy your needs?
> > (My compiler does not yet support valarray,
> > so I am not so familiar to it)
>
> As I understand, valarray is just a vector optimised for numerical
> use.  Although for some reason people keep discussing it as the
> solution to all of this bugaboo about (IHMO the standards committees
> gross oversight) whether vectors are contiguous.  Just out of
> curiosity has any one ON the standards committee responded to this?
>

Another guess: is a class like the "Pre-STL Standard" class dynarray
(as in Plauger, "The Draft Standard C++ Library")
suitable?

Helmut Zeisel


[ 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              ]

greg wrote:
>
> Valentin Bonnard [says]
...
> > There is nothing in the standard which directly says or indirectly
> > implies that vector<> shall or should have continuous
representation.
> > Nothing which even recommand that. At least no-one have been able to
> > cite such a thing. I don't understand Bjarne's comment, but IMO it's
> > completly unfounded.
> >
> > My personnal reading is that it's not even expected from
implementers.
>
> The standard places very stringent requirements on the complexity of
> vector operations, and a very experienced and skillful implementer
> once told me that he knew of no other way to meet those requirements.
> I've certainly never seen any other conforming implementation.  So I
> don't think implementers need the freedom to use other
implementations.

An implementation in which a vector<> contains a reallocatable array of
pointers to fixed-size memory blocks can meet all of the complexity
requirements. Some such scheme is needed if you want to have a vector<>
that is larger than the largest connected block of memory that can be
allocated.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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              ]

zeisel@lnzx16.vai.co.at (Zeisel Helmut) writes:

 > AFAIK pointer and element count is the quasi-standard interface
 > in languages such as
 > C and FORTRAN, and is used in Numerical Recipes,
 > IMSL, LAPACK, NAGLIB, BLAS, and so on.
 > I do not know any better solution for the function interface
 > in C and FORTRAN.
 >
 > The "special" about this particular problem is that it is not a
 > "particular" problem, but a very common one.

I agree.


 > Since
 >
 > 1) C++ is designed to be cooperative with other languages
 >  and existing code and libraries, and
 > 2) The aim of the standard C++ library is to provide
 >  comfortable solutions for "standard" problems,
 >
 > I would have expected that some "cooperative" vector class
 > is part of the standard library.

Vector was meant to be the most efficient representation of a random
accessible datastructure on a give architecture under the constraint
that its size could be changed. On all common architectures (of all
times I think) the former requirement implies contiguous allocation
of elements and the latter implies access through a handle (holding
a pointer to the elements).

Contiguous allocation was what Alex Stepanov assumed when he designed
the STL, was what I assumed when I supported its inclusion as part of
the standard library, and is what every implementation has provided.

As far as I can see, there are no words in the FDIS that explicitly
promises contiguous allocation of elements. There are however, many
statements that assumes that an increase of the size of a vector
will cause the reallocation of all elements. For example insert()
is said to "cause reallocation" rather than simply "may cause
reallocation". This is undoubtedly NOT meant as a requirement to
move elements, but it shows how deeply incrained in our thinking
is the notion that the elements of a vector is an array.

The deque explicitly supports uses where a random-accessible non-contiguously
allocated sequence of elements are needed.

Consider:

 vector<int> v; // use default allocator
 int* p = &v[i];

The initialization of p is legal because allocator<int>::reference is int*
and vector<int>::operator[]() returns an allocator<int>::reference.
In particular,
given the default allocator, &v[i] does not return an iterator which coould be
different from an int*.

Now consider (assume that i and i+1 are valid indeces):

 int* p1 = &v[i+1];
 int* p2 = &v[i]+1;
 if (p1 != p2) surprise();

Can surprise be called on a conforming implementation? Unless contiguity is
guaranteed the answer is 'yes.' One might allocate elements with one word of
padding between elements (silly) or allocate large vectors in segments
of 1024 elements so that indexing is required to first compute the address
of a segment holding an elementa and then its offset within that segment
(for a really large vector on a machine with peculiar addressing facilities,
this might make sense, but even then large segments of elements would be
contiguous).

My suggestion is that the answer should be 'no' so that surprise() will
never be called exactly as it will never be called in this example:

 int vv[n];
 int* p1 = &vv[i+1];
 int* p2 = &vv[i]+1;
 if (p1 != p2) surprise();

I suggested to the person who originally raised the issue of contiguous
allocation of vector elements that he ask for clarification from the C++
standards commitee through his national standards body. This has been done
so that this issue will be officially settled in due course.

Until then, I will personally assume vector elements to be allocated contiguously
despite the lack of a firm promise and despite the arguments brought forward
to the effect that there should be no such guarantee. For me at least, the
problems of not using vector vector elements directly from C-style routines
outweights the worry that the committee might come to a conclusion different
from mine (and it might, I do not claim to have fathomed every detail of this
issue - one reason to have a formal standards group is to look deeper into
issues that an individual is likely to do).

 - Bjarne

Bjarne Stroustrup, AT&T Labs, http://www.research.att.com/~bs



[ 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 <6jps98$hdq@netlab.cs.rpi.edu>,
  ark@research.att.com (Andrew Koenig) wrote:
>
> In article <6jfe5i$5c1@netlab.cs.rpi.edu>,
> Theodore Todorov  <todorov@sbghp10.in2p3.fr> wrote:
>
> >   2) vector<T> is _not_ usable as an interface to non-C++ functions
> >       (like write()), mainly because of the absence of a guarantee
> >      for contiguos storage.
>
> Whether vector<T> is usable as an interface to non-C++ functions
> is up to the implementation.  This state of affairs holds whether
> or not vector<T> is guaranteed to use contiguous storage.  For that
> matter, it is up to the implementation whether or not write() exists.

I thought that write was in the user namespace, in which case, the
implementation doesn't have a right to provide it.

--
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

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

greg <yo@mama.com> wrote:
: Valentin Bonnard quotes Jim Barry quoting James Kanze quoting Bjarne
: Stroustrup:
: > >
: > > ===> I'm not sure that the requirements can be met by any non-perverted
: > > implementation that doesn't allocate elements contiguously.  It is at
: > > least possible to read the standard as requiring contiguous allocation.

: > > In real code (as opposed to code used to illustrate formal properties
: > > of the standard), I'd simply use the efficient way.
: > > Maybe the committee ought to clarify this. Maybe
: > > you could send a request for clarification to the UK panel to get
: > > the process started?

: Yes, please do.
:
: > There is nothing in the standard which directly says or indirectly
: > implies that vector<> shall or should have continuous representation.
: > Nothing which even recommand that. At least no-one have been able to
: > cite such a thing. I don't understand Bjarne's comment, but IMO it's
: > completly unfounded.
: >
: > My personnal reading is that it's not even expected from implementers.

: The standard places very stringent requirements on the complexity of
: vector operations, and a very experienced and skillful implementer
: once told me that he knew of no other way to meet those requirements.

I think this implementor needs to pick some more skills
and experience then. In this thread alone, about a dozen of
other ways were proposed by several different people, and
some general mechanism was proposed to generate infinilely
many implementations other then plain contiguous, yet still
conforming to the complexity requirements.

: I've certainly never seen any other conforming implementation.  So I
: don't think implementers need the freedom to use other
implementations.

I think we do. The problems with contiguous storage is well known,
and plenty:

- the need for contiguous storage. May be hard to get if
  the memory is fragmented.

- very expensive relocation, if the copy constructor is expensive.

- the need for more memory then really needed, while relocating.
  If you are truly unlucky, and it causes L1, L2 or DRAM cache
  thrashing, you can get factor of 1000 performance penalty.

- relocating causes memory fragmentation. Can be very severe.

- and so on and so forth

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

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 <Et9Krn.DD8@research.att.com>,
  bs@research.att.com (Bjarne Stroustrup) wrote:
>
[Snipped]
>  >
>  > 1) C++ is designed to be cooperative with other languages
>  >  and existing code and libraries, and
>  > 2) The aim of the standard C++ library is to provide
>  >  comfortable solutions for "standard" problems,
>  >
>  > I would have expected that some "cooperative" vector class
>  > is part of the standard library.
>
> Vector was meant to be the most efficient representation of a random
> accessible datastructure on a give architecture under the constraint
> that its size could be changed. On all common architectures (of all
> times I think) the former requirement implies contiguous allocation
> of elements and the latter implies access through a handle (holding
> a pointer to the elements).
>
> Contiguous allocation was what Alex Stepanov assumed when he designed
> the STL, was what I assumed when I supported its inclusion as part of
> the standard library, and is what every implementation has provided.

[Snipped]

> Until then, I will personally assume vector elements to be allocated
contiguously
> despite the lack of a firm promise and despite the arguments brought forward
> to the effect that there should be no such guarantee. For me at least, the
> problems of not using vector vector elements directly from C-style routines
> outweights the worry that the committee might come to a conclusion different
> from mine.

[Snipped]

Thanks for your posting. It shows your practicality.  I had also decided
that even if the standard does not guarantee the contiguity, I will
ignore the standard.  Apart from the huge code base that C++ allows me
to tap (all using array and count), it also supports my theory that one
needs primitive containers like vector, slist and list to be predictable
(in terms of representation) to be useful in a variety of situations and
one can always build other containers on top of the efficient and primitive
ones (with different tradeoffs).

One analogy that comes to mind is a 'Point' class. If I don't know for sure
that it does not have efficient ways of setting x and y (assume 2d), I will
never use it. If somebody says that it may store polar co-ordinates (r and
theta) and may convert x and y to r and theta; then goodbye to that class
(I may use it when I need polar coordinates).  I may not have put it in
a coherent way, but the basic point is : it is good to keep classes at the
appropriate abstraction level.

- Saroj Mahapatra

-----== 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              ]

greg wrote:
>
> The standard places very stringent requirements on the complexity of
> vector operations, and a very experienced and skillful implementer
> once told me that he knew of no other way to meet those requirements.
> I've certainly never seen any other conforming implementation.  So I
> don't think implementers need the freedom to use other
> implementations.

I don't know what the official standard says, but the draft standard
says something that everyone in this discussion has missed. In 23.2.4.3
[lib.vector.modifiers], it says:

  iterator erase(iterator position);
  iterator erase(iterator first, iterator last);

  Effects:
    Invalidates all the iterators and references after the point of  the
    erase.
  Complexity:
    The  destructor of T is called the number of times equal to the num-
    ber of the elements erased, but the  assignment  operator  of  T  is
    called  the  number  of times equal to the number of elements in the
    vector after the erased elements.

The last clause states a requirement that would further imply
contiguity. For instance, the trick of storing pointers to elements, so
that the elements wouldn't have to move, would violate that clause,
since the assignment operator wouldn't be called at all.

I've looked at the complexity requirements of deque and vector, and it
seems to me that (given reasonable implementations) it should be
possible to require contiguity of storage for vector, while leaving
those situations where contiguity is a bad idea, to use deque instead.
Conversely, if vector is allowed to be noncontiguous, I see no
capability or benefit that vector provides that isn't also provided by
deque (or couldn't easily be added). In other words, if vector isn't
stored contiguously, what do we need it for?

--

Ciao,
Paul

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 <Et9Krn.DD8@research.att.com>, bs@research.att.com (Bjarne Stroustrup) writes:
>
> Consider:
>
>  vector<int> v; // use default allocator
>  int* p = &v[i];
>
> The initialization of p is legal because allocator<int>::reference is int*
> and vector<int>::operator[]() returns an allocator<int>::reference.
> In particular,
> given the default allocator, &v[i] does not return an iterator which coould be
> different from an int*.
>
> Now consider (assume that i and i+1 are valid indeces):
>
>  int* p1 = &v[i+1];
>  int* p2 = &v[i]+1;
>  if (p1 != p2) surprise();
>
> Can surprise be called on a conforming implementation? Unless contiguity is
> guaranteed the answer is 'yes.' One might allocate elements with one word of
> padding between elements (silly) or allocate large vectors in segments
> of 1024 elements so that indexing is required to first compute the address
> of a segment holding an elementa and then its offset within that segment
> (for a really large vector on a machine with peculiar addressing facilities,
> this might make sense, but even then large segments of elements would be
> contiguous).
>
> My suggestion is that the answer should be 'no' so that surprise() will
> never be called exactly as it will never be called in this example:
>
>  int vv[n];
>  int* p1 = &vv[i+1];
>  int* p2 = &vv[i]+1;
>  if (p1 != p2) surprise();
>
> I suggested to the person who originally raised the issue of contiguous
> allocation of vector elements that he ask for clarification from the C++
> standards commitee through his national standards body. This has been done
> so that this issue will be officially settled in due course.
>
> Until then, I will personally assume vector elements to be allocated contiguously
> despite the lack of a firm promise and despite the arguments brought forward
> to the effect that there should be no such guarantee. For me at least, the
> problems of not using vector vector elements directly from C-style routines
> outweights the worry that the committee might come to a conclusion different
> from mine (and it might, I do not claim to have fathomed every detail of this
> issue - one reason to have a formal standards group is to look deeper into
> issues that an individual is likely to do).
>
>  - Bjarne
>

I am not sure whether "contiguous" is the right word to describe
the desired behavior.
In particular, it is not clear to me what "contiguous" should mean
for vector<bool>.

Instead of "contiguous" I would prefer to see
an explicit guarantee that

 &v[i+1] == &v[i]+1 for valid indices

(which is guaranteed for valarray<T> in Draft Standard 2 Dec 96, 26.3.2.3 (3) )
for every vector<T> that is not specialized in the standard
(i.e., for every type T except of "bool")

Helmut Zeisel


[ 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 wrote:
>
> If a vector<T>::iterator is anything other than a T* (which it must
> be, to implement non-contiguous storage), I don't see what any
> implementation can do to allow a non-C++ function to access the
> contents
> of that container. The non-C++ code has no way of executing the member
> funcions needed to access those contents

The implementation could provide a regular extern "C" function that gets
a regular pointer. Or, it could be left up to the C++ caller to get the
pointer and pass it to the C code. But this would only be possible if
the underlying implementation was contiguous.

--

Ciao,
Paul

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

Paul D. DeRocco wrote:
>
> James Kuyper wrote:
> >
> > If a vector<T>::iterator is anything other than a T* (which it must
> > be, to implement non-contiguous storage), I don't see what any
> > implementation can do to allow a non-C++ function to access the
> > contents
> > of that container. The non-C++ code has no way of executing the member
> > funcions needed to access those contents
>
> The implementation could provide a regular extern "C" function that gets
> a regular pointer. Or, it could be left up to the C++ caller to get the
> pointer and pass it to the C code. But this would only be possible if
> the underlying implementation was contiguous.

The message I was responding to claimed that this was feasible, whether
or not vector<> is contiguous. The solution is, of course, quite trivial
with contiguous storage. However, I was pointing out that it is far from
trivial, and perhaps impossible, in the case of non-contiguous storage.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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 wrote:
>
> Paul D. DeRocco wrote:
> >
> > James Kuyper wrote:
> > >
> > > If a vector<T>::iterator is anything other than a T* (which it must
> > > be, to implement non-contiguous storage), I don't see what any
> > > implementation can do to allow a non-C++ function to access the
> > > contents
> > > of that container. The non-C++ code has no way of executing the member
> > > funcions needed to access those contents
> >
> > The implementation could provide a regular extern "C" function that gets
> > a regular pointer. Or, it could be left up to the C++ caller to get the
> > pointer and pass it to the C code. But this would only be possible if
> > the underlying implementation was contiguous.
>
> The message I was responding to claimed that this was feasible, whether
> or not vector<> is contiguous. The solution is, of course, quite trivial
> with contiguous storage. However, I was pointing out that it is far from
> trivial, and perhaps impossible, in the case of non-contiguous storage.

The problem to access the members of a vector from other languages is
easy:

vector<X> v;

extern "C" X* getX(int index)
{
  if (index<0 || index>v.size())
    return NULL;
  return &v[index];
}

There could also be a GetFirstX/GetNextX interface with opaque
pointers (which indeed just point to iterators) to allow faster
iteration from other languages. Indeed, this would even reduce
the dependency on actual implementation (there need not be a
"real" iterator behind; the opaque pointers could point to the
objects themselves for contiguous memory, or they could point
to the nodes for lists. They could even contain no pointers at
all, but other data that fits, since you never dereference them
in your program).

Indeed, the problem only arises the other way round: You *have* already
a function taking a pointer and an element count, and want to store
your data in a vector and pass that data to that function.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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              ]

David Abrahams <abrahams@motu.com> writes:

> I'm fairly sure that deque<T> fulfills all of the requirements of
> vector<T> except those involving reserve(). I think you could add that
> behavior to a deque and get a conforming non-contiguous vector.

No, vector has the additionnal requirement that insert/remove
only invalidates iterators/pointers after the point of insertion/
removal. This isn't garantied for deque (except for insertions
at the end).

Of course, this is assuming that no reallocation occur.

Or perhaps that's exactly what you meant by requirements
'involving reserve()' ?

The idea behind deque is that it can grow in both directions,
whereas vector only grow in one direction; also deque has an
extra level of indirection. This gives differents
complexity requirements. It seems to me that the union of the
requirements of vector and deque is umimplementable, or
at least very difficult to implement.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 <6jfe5i$5c1@netlab.cs.rpi.edu>,
Theodore Todorov  <todorov@sbghp10.in2p3.fr> wrote:

>   2) vector<T> is _not_ usable as an interface to non-C++ functions
>       (like write()), mainly because of the absence of a guarantee
>      for contiguos storage.

Whether vector<T> is usable as an interface to non-C++ functions
is up to the implementation.  This state of affairs holds whether
or not vector<T> is guaranteed to use contiguous storage.  For that
matter, it is up to the implementation whether or not write() exists.
--
    --Andrew Koenig
      ark@research.att.com
      http://www.research.att.com/info/ark


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

On 12 May 1998 16:24:36 GMT, "greg" <yo@mama.com> wrote:
>Andrew Koenig <ark@research.att.com> wrote in article
><6j6isj$61s@netlab.cs.rpi.edu>...
>> In article <6isd34$sgo@netlab.cs.rpi.edu>,
>> Jim Barry <jim.barry@bigfoot.com> wrote:
>>
>> > If vectors cannot be assumed to be contiguous, they cannot be used
>> > with functions that take a pointer and an element count, which is a
>> > very common scenario.
>>
>> You're quite correct.  Such functions should be rewritten to take
>> a vector iterator and an element count.
>
>Except that if those functions belong to a third party, such as your OS
>vendor, you can't rewrite them.  So perhaps it would have been better
>for the vector<T> iterator type to be specified as T*.  I expect that
>this will be true of enough implementations, and assumed by enough code,
>to become a problem.
>
It will be a problem, Most O/S interfaces apply a binary standard
defined  by the vendor. This is probably because there is no other way
to define stuff, but it also results in simplicity and better
performance.

To take the specific example of Win16, it certainly allowed
allocations beyond 64K and in order to do so, the most efficient
implementation required telling the compiler that this was the case.
There were unpleasant issues involved, but these just involved the use
of an occasional  keyword,  no more unpleasant than the
template/vector syntax.

Anyway, i hope that the C++  vtable implementation does not assume
this terrible contiguous thing and that it  uses vector iterators :).

phil.
---
[ 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              ]

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

On 18 May 98 07:20:00 GMT, Valentin Bonnard <bonnardv@pratique.fr>
wrote:

>David Abrahams <abrahams@motu.com> writes:
>
>> I'm fairly sure that deque<T> fulfills all of the requirements of
>> vector<T> except those involving reserve(). I think you could add that
>> behavior to a deque and get a conforming non-contiguous vector.
>
>No, vector has the additionnal requirement that insert/remove
>only invalidates iterators/pointers after the point of insertion/
>removal. This isn't garantied for deque (except for insertions
>at the end).

No, but a particular deque implementation could make this guarantee.
Of course, it wouldn't be a very good implementation, since insertions
near the beginning would be unneccessarily expensive.

>Of course, this is assuming that no reallocation occur.
>
>Or perhaps that's exactly what you meant by requirements
>'involving reserve()' ?

Not exactly, but it is related. Since deque doesn't support reserve(),
you'd need to extend it. Reallocation requirements on vector<> are
intimately tied up with the behavior of reserve().

>The idea behind deque is that it can grow in both directions,
>whereas vector only grow in one direction;

Of course I know that.

>also deque has an extra level of indirection.

That part is just an implementation detail; it isn't required.

>This gives differents
>complexity requirements. It seems to me that the union of the
>requirements of vector and deque is umimplementable, or
>at least very difficult to implement.

You're right; it would be very difficult, at least to do well. But
you're missing my point: I'm just trying to illustrate a possible
structure for vector which could be non-contiguous. You could
implement a conforming vector in a way analogous to deque.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 <6jfe5i$5c1@netlab.cs.rpi.edu>, Theodore Todorov <todorov@sbghp10.in2p3.fr> writes:
 >
 > So what we need is a new container, array<T>, which is essentially
 > a vector with contiguous storage and possibly iterators convertible
 > to pointers ( but I would prefere no implicit conversion,  typing
 >
 >    array<T>::iterator i;
 >    T* tp = &(*i);
 >
 > is not that difficult and makes the conversion explicit).
 >
 > This new container could contain some new features which vector
 > lacks, like the possibility for the user to provide growth policy
 > (the implementation I use used to allocate max(1024,sizeof(T)) bytes
 > at first insertion and then doubled the size, and there is _no_ way
 > to change this; the latest version has a bug in the growth algorithm
 > and does not comply with the requirements of std::vector !).
 >
 > If such a container could be standardised I would probably never
 > need to use vector, which would solve the problem of the ill-chosen
 > std::vector name (now I have vector<Vector>, the Vector being
 > a real mathematical vector).

Does valarray satisfy your needs?
(My compiler does not yet support valarray,
so I am not so familiar to it)

Helmut Zeisel

--
---
[ 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              ]

greg <yo@mama.com> wrote:

: Andrew Koenig <ark@research.att.com> wrote in article
: <6j6isj$61s@netlab.cs.rpi.edu>...
: > In article <6isd34$sgo@netlab.cs.rpi.edu>,
: > Jim Barry <jim.barry@bigfoot.com> wrote:
: >
: > > If vectors cannot be assumed to be contiguous, they cannot be used
: > > with functions that take a pointer and an element count, which is
a
: > > very common scenario.
: >
: > You're quite correct.  Such functions should be rewritten to take
: > a vector iterator and an element count.

: Except that if those functions belong to a third party, such as your
OS
: vendor, you can't rewrite them.  So perhaps it would have been better
: for the vector<T> iterator type to be specified as T*.

No, it absolutely should not. I think that the common current
practice of typedeffing the iterator to T* is very bad.
It does not catch accessing elements of vector<Derived>
through vector<Base>::iterator, at compile time.

Besides, how would a library vendor implement vector, which
stores it's elements non-contiguously?

: I expect that
: this will be true of enough implementations, and assumed by enough
code,
: to become a problem.

That would be a true disaster. I don't think it'll ever get
that bad.

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

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 <6isd34$sgo@netlab.cs.rpi.edu>,
  "Jim Barry" <jim.barry@bigfoot.com> wrote:
>
> jkanze@otelo.ibmmail.com wrote in message
> <6ipu9s$hm8@netlab.cs.rpi.edu>...
> >Unless I've misunderstood something, linear, in this context,
> >means that for i < j, if v[ i ] exists and v[ j ] exists, all
> >intermediate elements also exist.  (A linked list is also linear.)
>
> You could equally well take it to mean a linear arrangement in memory.

As it happens, I'm unable to find the word linear in the standard anyway,
at least refering to vector.  The exact text describing vector, quoted
from the standard:

    A vector is a kind of sequence that supports random access
    iterators.  In addition, it supports (amortized) constant time
    insert and erase operations at the end; insert and erase in the
    middle take linear time.  Storage management is handled
    automatically, though hints can be given to improve efficiency.

    A vector satisfies all of the requirements of a container and of a
    reversible container (given in two tables in
    _lib.container.requirements_) and of a sequence, including most of
    the optional sequence requirements (_lib.sequence.reqmts_).  The
    exceptions are the push_front and pop_front member functions,
    which are not provided.

Contiguity can't be implied by the word "sequence", since a list is
also described as being a kind of sequence.  An the only thing that
is linear is the *time* it takes to insert in the middle.

--
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 oriente 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

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 <6isd34$sgo@netlab.cs.rpi.edu>,
Jim Barry <jim.barry@bigfoot.com> wrote:

> If vectors cannot be assumed to be contiguous, they cannot be used
> with functions that take a pointer and an element count, which is a
> very common scenario.

You're quite correct.  Such functions should be rewritten to take
a vector iterator and an element count.
--
    --Andrew Koenig
      ark@research.att.com
      http://www.research.att.com/info/ark


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 in message
<6itsdf$7n8@netlab.cs.rpi.edu>...
>Really.  If I understood Bjarne's quotation correctly, he said that
>if you thought the question unclear, you should as for a
clarification
>from the standards committee.

That quote in full:

===> I'm not sure that the requirements can be met by any non-perverted
implementation that doesn't allocate elements contiguously.  It is at least
possible to read the standard as requiring contiguous allocation. In real code
(as opposed to code used to illustrate formal properties of the standard), I'd
simply use the efficient way. Maybe the committee ought to clarify this. Maybe
you could send a request for clarification to the UK panel to get the process
started?

>> If vectors cannot be assumed to be contiguous, they cannot be used
>> with functions that take a pointer and an element count, which is a
>> very common scenario.
>
>So common that I've never seen it in C++ code.

It is common in Win32.

Sure, I can write my own contiguously-allocating vector but I had
hoped that would be something the standard library would provide.
Until I come up with a better idea, I'll just take advantage of VC's
contiguous implementation. It makes me queasy but, after all, code
written to Win32 has limited portability anyway.

- Jim

--
Jim Barry, Thermoteknix Systems Ltd., Cambridge, UK.
http://www.thermoteknix.co.uk Queen's Award for Export 1998
Antispam address courtesy of http://www.bigfoot.com
Or e-mail direct: jim at thermoteknix dot co dot uk

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

Jim Barry wrote in message <6isd34$sgo@netlab.cs.rpi.edu>...
>jkanze@otelo.ibmmail.com wrote in message
><6ipu9s$hm8@netlab.cs.rpi.edu>...
>If vectors cannot be assumed to be contiguous, they cannot be used
>with functions that take a pointer and an element count, which is a
>very common scenario. Workarounds are ugly and inefficient, and pretty
>much outweigh the benefits that vector offers. I want C++ to help me
>write good code, not to punish me for trying to make effective use of
>new language developments.

If you want to write good code, use vector<>.  If you want to be punished,
use functions that take a pointer and an element count.  This sounds like an
embedded systems scenario in which you'd need the speed of contiguous
memory.  If it's not, then use something readable like vector<>.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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:
>> Access in constant time means just that, and says nothing concerning
>> the arrangement in memory.

Paul D. DeRocco <pderocco@ix.netcom.com> wrote:
>I'm no mathematician, but it seems to me that the only arrangement that
>could achieve constant time is either contiguous, or fixed sized pages
>with a fixed number of levels of indirection.

The HP and SGI implementations of deque<T> use the latter arrangement
that you describe (the data is stored in a sequence of fixed sized
pages,
and these pages are indexed in a lookup table).

--
-- Joe Buck
   work: jbuck@synopsys.com, otherwise jbuck@welsh-buck.org or
jbuck@best.net
http://www.welsh-buck.org/

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

On 11 May 98 21:19:09 GMT, "Jim Barry" <jim.barry@bigfoot.com> wrote:

>jkanze@otelo.ibmmail.com wrote in message
><6itsdf$7n8@netlab.cs.rpi.edu>...
>>Really.  If I understood Bjarne's quotation correctly, he said that
>>if you thought the question unclear, you should as for a
>clarification
>>from the standards committee.
>
>That quote in full:
>
>===> I'm not sure that the requirements can be met by any non-perverted
>implementation that doesn't allocate elements contiguously.  It is at least
>possible to read the standard as requiring contiguous allocation. In real
code
>(as opposed to code used to illustrate formal properties of the standard),
I'd
>simply use the efficient way. Maybe the committee ought to clarify this.
Maybe
>you could send a request for clarification to the UK panel to get the process
>started?

I'm fairly sure that deque<T> fulfills all of the requirements of
vector<T> except those involving reserve(). I think you could add that
behavior to a deque and get a conforming non-contiguous vector.

>>> If vectors cannot be assumed to be contiguous, they cannot be used
>>> with functions that take a pointer and an element count, which is a
>>> very common scenario.
>>
>>So common that I've never seen it in C++ code.
>
>It is common in Win32.

In some architectures, like Win16, the best implementation of vector
might NOT allocate contiguously. If you want more than 64KB worth of
elements in your vector under this memory model, you're better off
with an implementation resembling that of most deques.

-Dave

P.S. NO, 16-bit Windows programming is NOT dead; there are
(unfortunately) still lots of reasons to use it. Just for one example,
anyone doing real-time multimedia work for Win95 will need to use some
Win16 code if to get good timing response.

P.P.S. std::vector was not designed as a stand-in for C++ arrays; It
just happens to be a convenient stand-in in many cases.
(Please change 'spam' to 'abrahams' in the return address, which has
been altered to foil junk mail senders.)

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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              ]

Andrew Koenig <ark@research.att.com> wrote in article
<6j6isj$61s@netlab.cs.rpi.edu>...
> In article <6isd34$sgo@netlab.cs.rpi.edu>,
> Jim Barry <jim.barry@bigfoot.com> wrote:
>
> > If vectors cannot be assumed to be contiguous, they cannot be used
> > with functions that take a pointer and an element count, which is a
> > very common scenario.
>
> You're quite correct.  Such functions should be rewritten to take
> a vector iterator and an element count.

Except that if those functions belong to a third party, such as your OS
vendor, you can't rewrite them.  So perhaps it would have been better
for the vector<T> iterator type to be specified as T*.  I expect that
this will be true of enough implementations, and assumed by enough code,
to become a problem.

Greg Colvin

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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 <6j6isj$61s@netlab.cs.rpi.edu>, ark@research.att.com (Andrew Koenig) writes:
> In article <6isd34$sgo@netlab.cs.rpi.edu>,
> Jim Barry <jim.barry@bigfoot.com> wrote:
>
> > If vectors cannot be assumed to be contiguous, they cannot be used
> > with functions that take a pointer and an element count, which is a
> > very common scenario.
>
> You're quite correct.  Such functions should be rewritten to take
> a vector iterator and an element count.

And what is the recommended solution if that function
cannot be changed because it is part of a third party C library?
valarray??????

Helmut Zeisel



[ 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 <6j6isj$61s@netlab.cs.rpi.edu>,
  ark@research.att.com (Andrew Koenig) wrote:
>
> In article <6isd34$sgo@netlab.cs.rpi.edu>,
> Jim Barry <jim.barry@bigfoot.com> wrote:
>
> > If vectors cannot be assumed to be contiguous, they cannot be used
> > with functions that take a pointer and an element count, which is a
> > very common scenario.
>
> You're quite correct.  Such functions should be rewritten to take
> a vector iterator and an element count.

I think that two iterators (begin and end) would be more idiomatic.
But it's not that easy; some of the functions in question are defined
by standards (ISO C, Posix, etc.) or are part of a published API.
Making write take two iterators, instead of a pointer and count,
would require some hacking in my system kernel (thus invalidating
my maintenance contract with Sun), and would break most of the other
applications running on my system.

--
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 oriente 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

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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:
>
> In article <6j6isj$61s@netlab.cs.rpi.edu>,
>   ark@research.att.com (Andrew Koenig) wrote:
> >
> > In article <6isd34$sgo@netlab.cs.rpi.edu>,
> > Jim Barry <jim.barry@bigfoot.com> wrote:
> >
> > > If vectors cannot be assumed to be contiguous, they cannot be used
> > > with functions that take a pointer and an element count, which is a
> > > very common scenario.
> >
> > You're quite correct.  Such functions should be rewritten to take
> > a vector iterator and an element count.
>
> I think that two iterators (begin and end) would be more idiomatic.
> But it's not that easy; some of the functions in question are defined
> by standards (ISO C, Posix, etc.) or are part of a published API.
> Making write take two iterators, instead of a pointer and count,
> would require some hacking in my system kernel (thus invalidating
> my maintenance contract with Sun), and would break most of the other
> applications running on my system.
>

It seems that

  1) vector<T> is a well-defined and perfectly useful container as
      it is even if the benefits of not requiring contiguous storage
      are dubious for the time being. Anyway, it's too late to change
it.

  2) vector<T> is _not_ usable as an interface to non-C++ functions
      (like write()), mainly because of the absence of a guarantee
     for contiguos storage.

  3) a vector<T> - like container which is storage-compatible with
     built-in arrays but adjusts its size in a transparent way and has
     constant time insertion at the end is very useful at least for
     some applications, and is not provided in the standard library.

So what we need is a new container, array<T>, which is essentially
a vector with contiguous storage and possibly iterators convertible
to pointers ( but I would prefere no implicit conversion,  typing

   array<T>::iterator i;
   T* tp = &(*i);

is not that difficult and makes the conversion explicit).

This new container could contain some new features which vector
lacks, like the possibility for the user to provide growth policy
(the implementation I use used to allocate max(1024,sizeof(T)) bytes
at first insertion and then doubled the size, and there is _no_ way
to change this; the latest version has a bug in the growth algorithm
and does not comply with the requirements of std::vector !).

If such a container could be standardised I would probably never
need to use vector, which would solve the problem of the ill-chosen
std::vector name (now I have vector<Vector>, the Vector being
a real mathematical vector).

                            Regards,
                                       Teddy Todorov (t.todorov@cern.ch)

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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              ]

Jim Barry wrote:
>
> jkanze@otelo.ibmmail.com wrote in message
> <6itsdf$7n8@netlab.cs.rpi.edu>...
> >Really.  If I understood Bjarne's quotation correctly, he said that
> >if you thought the question unclear, you should as for a
> clarification
> >from the standards committee.
>
> That quote in full:
>
> ===> I'm not sure that the requirements can be met by any non-perverted
> implementation that doesn't allocate elements contiguously.  It is at least
> possible to read the standard as requiring contiguous allocation. In real code
> (as opposed to code used to illustrate formal properties of the standard), I'd
> simply use the efficient way. Maybe the committee ought to clarify this. Maybe
> you could send a request for clarification to the UK panel to get the process
> started?

There is nothing in the standard which directly says or indirectly
implies that vector<> shall or should have continuous representation.
Nothing which even recommand that. At least no-one have been able to
cite such a thing. I don't understand Bjarne's comment, but IMO it's
completly unfounded.

My personnal reading is that it's not even expected from implementors.

> Sure, I can write my own contiguously-allocating vector but I had
> hoped that would be something the standard library would provide.
> Until I come up with a better idea, I'll just take advantage of VC's
> contiguous implementation. It makes me queasy but, after all, code
> written to Win32 has limited portability anyway.

If it's a common scenario, perhaps we should do something about it.

Ideas so far:

o data() variants:
  - add a data() function, which returns a non-modifiable array
  - add a mutable_data() function, which returns a modifiable array,
whose
    change will be applied back to the vector
  - add a release_data(), to release the array returned by data()

o introduce some variant of vector garantied to be contiguous
  (the old good dyn_array ;-)

o change vector to garanty contiguity, which IMO breaks the
  nice abstraction

[PREFERED]
o separate the fact that a deque is double ended from the fact
  that it allocates in chuncks; then garanty contiguity for
  vector and deque, knowing that the user can still use the
  noinval containner adaptator; see
       http://www.eleves.ens.fr:8080/home/bonnard/deque.html

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

> >If vectors cannot be assumed to be contiguous, they cannot be used
> >with functions that take a pointer and an element count, which is a
> >very common scenario...
> If you want to write good code, use vector<>.  If you want to be punished,
> use functions that take a pointer and an element count...

Forgive me, but this bit about methods that take a pointer originally
started when someone pointed out how many legacy functions
there that do so, e.g. memset, memcpy, fread,  etc.

Peace

Peter


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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 <199805120621.IAA06855@lnzx05.co.at>,
Zeisel Helmut <zeisel@lnzx16.vai.co.at> wrote:

> > You're quite correct.  Such functions should be rewritten to take
> > a vector iterator and an element count.

> And what is the recommended solution if that function
> cannot be changed because it is part of a third party C library?
> valarray??????

The same solution as when a third-party function has any
other portability bug.  There is nothing special about this
particular problem.
--
    --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              ]

Valentin Bonnard quotes Jim Barry quoting James Kanze quoting Bjarne
Stroustrup:
> >
> > ===> I'm not sure that the requirements can be met by any non-perverted
> > implementation that doesn't allocate elements contiguously.  It is at least
> > possible to read the standard as requiring contiguous allocation. In real code
> > (as opposed to code used to illustrate formal properties of the standard), I'd
> > simply use the efficient way. Maybe the committee ought to clarify this. Maybe
> > you could send a request for clarification to the UK panel to get the process
> > started?

Yes, please do.

> There is nothing in the standard which directly says or indirectly
> implies that vector<> shall or should have continuous representation.
> Nothing which even recommand that. At least no-one have been able to
> cite such a thing. I don't understand Bjarne's comment, but IMO it's
> completly unfounded.
>
> My personnal reading is that it's not even expected from implementers.

The standard places very stringent requirements on the complexity of
vector operations, and a very experienced and skillful implementer
once told me that he knew of no other way to meet those requirements.
I've certainly never seen any other conforming implementation.  So I
don't think implementers need the freedom to use other implementations.

> > Sure, I can write my own contiguously-allocating vector but I had
> > hoped that would be something the standard library would provide.
> > Until I come up with a better idea, I'll just take advantage of VC's
> > contiguous implementation. It makes me queasy but, after all, code
> > written to Win32 has limited portability anyway.
>
> If it's a common scenario, perhaps we should do something about it.

Agreed.

> Ideas so far:
>
> o data() variants:
>   - add a data() function, which returns a non-modifiable array
>   - add a mutable_data() function, which returns a modifiable array,
> whose
>     change will be applied back to the vector
>   - add a release_data(), to release the array returned by data()

Ugly and error prone, IMHO.

> o introduce some variant of vector garantied to be contiguous
>   (the old good dyn_array ;-)

Too late for now.

> o change vector to garanty contiguity, which IMO breaks the
>   nice abstraction

I don't see what the abstraction is worth.  I would like to see
a technical corrigendum to the standard to simply replace the
following four lines in 23.2.4 Template class vector:

   typedef implementation defined iterator;       // See 23.1
   typedef implementation defined const_iterator; // See 23.1
   typedef implementation defined size_type;      // See 23.1
   typedef implementation defined difference_type;// See 23.1

with

   typedef typename Allocator::pointer iterator;
   typedef typename Allocator::const_pointer const_iterator;
   typedef typename Allocator::size_type size_type;
   typedef typename Allocator::difference_type difference_type;

> [PREFERED]
> o separate the fact that a deque is double ended from the fact
>   that it allocates in chuncks; then garanty contiguity for
>   vector and deque, knowing that the user can still use the
>   noinval containner adaptator; see
>        http://www.eleves.ens.fr:8080/home/bonnard/deque.html

Interesting idea, but how does it help vector?

Greg Colvin


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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 <MDRLdUlulsRd-pn2-FcODfUiVNDQE@localhost>#1/1,
  peter.garner@toward.com (Peter Garner) wrote:
> Yes, please do!  I have read books that state that
> vector is a CONTIGUOUS array.   I think a lot of
> people are under that (mis)impression.  According
> to "The STL Tutorial and Reference Guide" by
> Musser and Saini (ISBN 0-201-63398-1) in section
> 19.3.3 it states that "Vectors are containers that
> arrange elements of a given type in a strictly linear
> arrangement and allow fast random access to any
> element (i.e. any element can be accessed in
> constant time). "

IMHO, this does not say that the elements of the vector must
be stored in contiguous memory locations.  My own dynamic
array class met these requirements, but did not store elements
contiguously.

Unless I've misunderstood something, linear, in this context,
means that for i < j, if v[ i ] exists and v[ j ] exists, all
intermediate elements also exist.  (A linked list is also linear.)

Access in constant time means just that, and says nothing concerning
the arrangement in memory.

> Of course this is just an author's
> opinion not the ISO Standard.  Of course this goes
> to show that others, (including myself) have made
> the assumption that vectors are contiguous and
> linear.

I presume that people make this assumption because of the name, and
not from anything in the description of the class.  And far too many
people just look at the implementation on their machine, and suppose
that it is universal.

> Frankly if the committee does not clarify
> this in a such a manner as to support the idea
> that vectors are contiguous it will necessitate
> the rewrite of a great deal of code of which I
> am aware.

The same could be say about modifying a variable twice without an
intervening sequence point.  When I first started using C, the same
could be said about dereferencing a null pointer.  (In the early '80s,
most Unix implementations mapped the address 0 to a block of memory
that contained zeros, and there was a lot of code which used the null
pointer and "" interchangeably.)

The fact that people write incorrect code that happens to work on
one particular implementation is not a valid motive for modifying the
standard.

> I SERIOUSLY doubt that ANYONE
> has written code that depends upon vectors
> being NON-CONTIGUOUS.

Of course not.  Since it is not guaranteed.  But I find it hard to
believe that any professional has written code that depended on vectors
being contiguous.  Such code certainly wouldn't get through any serious
code reveiw.

> For this reason
> I encourage all involved parties to consider
> clarifying the Standard so that it requires
> vectors to be implemented in a contiguous
> fashion.

And break my implementation:-)?

(Seriously, insofar as vector is the official alternative to C style
arrays, and there are no fixed length vectors which don't use dynamic
allocation, I would be extremely surprised if any implementation did
not use contiguous memory, since it results in additional run-time
overhead in operator[]. My solution, however, would be to define a
static
vector, whose length was a template argument, and which would guarantee
basically the same as what is guaranteed by C style arrays: contiguous
memory, no dynamic allocations within the vector, and the size
determined
by size()*sizeof( ElementType ).

--
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

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 don't think that's necessary. Many people use unportable
> constructs, assume sizeof(long) = sizeof(int) = sizeof(T*)
> for any T, clutter their code with far/_far/__far/
> ____veryfar, or that sub-functions exist in C. This doesn't
> mean that a clarification is needed in the standard.

No, because the standard is very clear in stating that the
above assumptions are incorrect.

> > I have read books that state that
> > vector is a CONTIGUOUS array.
>
> Then these books are bad.
>
> > I think a lot of
> > people are under that (mis)impression.

These books are not necessarly "bad".  I
was referencing them as evidence that a
great deal of misunderstanding or difference
of opinion exists regarding this matter.

> But the standard is perfectly clear. I understand the
> addition of a comment as this could be usual mis-interpretation.
> But saying that the standard is unclear in order to
> force a change isn't honest - OTOH arguing that the std
> classes are unusable is ok (even if I disagre).

Well, I think there is a point to be made in both cases.
non-contiguous vectors are certainly less usefull
than those guarenteed to be contiguous.  But I do
not find the standard to be clear on this point.
Nor does Bjarne Stroustrup, Jim Barry, the authors
of various books and other participants in this echo.
The fact that the standard "clearly" states one thing
to you and states the opposite to others is de facto
proof that a clarification is needed!  I.e. You may be
entirely correct in that your interpretation is exactly
what the committe intended when they wrote that
section.  However, since that intention seems
muddled to a number of people, perhaps it should
be clarified.


Thanks

Peter


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

> IMHO, this does not say that the elements of the vector must
> be stored in contiguous memory locations.  My own dynamic
> array class met these requirements, but did not store elements
> contiguously.
> Unless I've misunderstood something, linear, in this context,
> means that for i < j, if v[ i ] exists and v[ j ] exists, all
> intermediate elements also exist.  (A linked list is also linear.)

Good point

> The fact that people write incorrect code that happens to work on
> one particular implementation is not a valid motive for modifying the
> standard.
> But I find it hard to
> believe that any professional has written code that depended on vectors
> being contiguous.  Such code certainly wouldn't get through any serious
> code reveiw.

Well, to tell you the truth, what I have done in code for which
I am paid is to use a home grown template array class that
has a similiar interface and commented it with the lament
that the STL vector class is preferred since it is part of the
standard library and should be used to replace the home
grown class should the standard be clarified in favour of
contiguous arrays.

> > For this reason
> > I encourage all involved parties to consider
> > clarifying the Standard so that it requires
> > vectors to be implemented in a contiguous
> > fashion.
>
> And break my implementation:-)?

Sorry :-)   I would be content if the issue were
clarified in the standard one way or the other!

Thanks

Peter


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 in message
<6ipu9s$hm8@netlab.cs.rpi.edu>...
>Unless I've misunderstood something, linear, in this context,
>means that for i < j, if v[ i ] exists and v[ j ] exists, all
>intermediate elements also exist.  (A linked list is also linear.)

You could equally well take it to mean a linear arrangement in memory.

>I presume that people make this assumption because of the name, and
>not from anything in the description of the class.  And far too many
>people just look at the implementation on their machine, and suppose
>that it is universal.

Among the people who make this assumption are two language experts I
have consulted on the matter, one of whom invented C++.

>The fact that people write incorrect code that happens to work on
>one particular implementation is not a valid motive for modifying the
>standard.

The fact that a bunch of existing code relies on a reasonable
assumption that nobody thought to make explicit in the standard is
most certainly a reason to make it explicit now.

>Of course not.  Since it is not guaranteed.  But I find it hard to
>believe that any professional has written code that depended on
vectors
>being contiguous.  Such code certainly wouldn't get through any
serious
>code reveiw.

If vectors cannot be assumed to be contiguous, they cannot be used
with functions that take a pointer and an element count, which is a
very common scenario. Workarounds are ugly and inefficient, and pretty
much outweigh the benefits that vector offers. I want C++ to help me
write good code, not to punish me for trying to make effective use of
new language developments.

>(Seriously, insofar as vector is the official alternative to C style
>arrays, and there are no fixed length vectors which don't use dynamic
>allocation, I would be extremely surprised if any implementation did
>not use contiguous memory, since it results in additional run-time
>overhead in operator[].

Right.

>My solution, however, would be to define a static
>vector, whose length was a template argument, and which would
guarantee
>basically the same as what is guaranteed by C style arrays:
contiguous
>memory, no dynamic allocations within the vector, and the size
>determined by size()*sizeof( ElementType ).

A fixed-size array class is not very useful compared with the
facilities that vector provides. And other than knowing it's own size,
I can't think of any advantages it might offer over built-in arrays.

- Jim

--
Jim Barry, Thermoteknix Systems Ltd., Cambridge, UK.
Antispam address courtesy of http://www.bigfoot.com
Or e-mail direct: jim at thermoteknix dot co dot uk



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]

Jim Barry wrote:
...
> If vectors cannot be assumed to be contiguous, they cannot be used
> with functions that take a pointer and an element count, which is a
> very common scenario. Workarounds are ugly and inefficient, and pretty
> much outweigh the benefits that vector offers. I want C++ to help me
> write good code, not to punish me for trying to make effective use of
> new language developments.

Would a valarray<> serve your needs? According to section 26.3.2.3, if
we have

 valarray<T> a;
 size_t i, j;

Then a[i] must return T&, and if i+j<=a.size(), then &a[i+j] == &a[i]+j,
so contiguity is guaranteed.

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 <6is62p$qj7@netlab.cs.rpi.edu>,
  peter.garner@toward.com (Peter Garner) wrote:

> Well, to tell you the truth, what I have done in code for which
> I am paid is to use a home grown template array class that
> has a similiar interface and commented it with the lament
> that the STL vector class is preferred since it is part of the
> standard library and should be used to replace the home
> grown class should the standard be clarified in favour of
> contiguous arrays.

When I have special requirements, I write my own classes too:-).

> > > For this reason
> > > I encourage all involved parties to consider
> > > clarifying the Standard so that it requires
> > > vectors to be implemented in a contiguous
> > > fashion.
> >
> > And break my implementation:-)?
>
> Sorry :-)   I would be content if the issue were
> clarified in the standard one way or the other!

I think it is clear.  An implementation is free to do whatever it
wants as long as it conforms to the requirements explicitly stated
in the standard, or rather, as long as its "observable behavior" for
a legal program is that documented in the standard.  Can anyone quote
a statement from the standard which even implies, no matter how weakly,
that the memory for vector must be contiguous?

--
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

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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 <6isd34$sgo@netlab.cs.rpi.edu>,
  "Jim Barry" <jim.barry@bigfoot.com> wrote:
>
> jkanze@otelo.ibmmail.com wrote in message
> <6ipu9s$hm8@netlab.cs.rpi.edu>...
> >Unless I've misunderstood something, linear, in this context,
> >means that for i < j, if v[ i ] exists and v[ j ] exists, all
> >intermediate elements also exist.  (A linked list is also linear.)
>
> You could equally well take it to mean a linear arrangement in memory.

The usual word for this is contiguous, I believe.

> >I presume that people make this assumption because of the name, and
> >not from anything in the description of the class.  And far too many
> >people just look at the implementation on their machine, and suppose
> >that it is universal.
>
> Among the people who make this assumption are two language experts I
> have consulted on the matter, one of whom invented C++.

Really.  If I understood Bjarne's quotation correctly, he said that
if you thought the question unclear, you should as for a clarification
from the standards committee.  Given the discussions I've had with
some members, I rather suspect that the clarification would be simple:
to my knowledge, there is no text in the standard which even suggests
that there are any constraints on the implementation of a vector, except
for the fact that operator[] must execute in constant time.  Having
learned about vector from the text in the standard, it never occured
to me that anyone could suppose that its memory must be contiguous.
(Obviously, from what you say, some implementers document it as such,
without signalling that this is a particularity of their implementation.
If you learned vector from such implementer's documentation, it is not
surprising that you expect the memory to be contiguous.)

> >The fact that people write incorrect code that happens to work on
> >one particular implementation is not a valid motive for modifying the
> >standard.
>
> The fact that a bunch of existing code relies on a reasonable
> assumption that nobody thought to make explicit in the standard is
> most certainly a reason to make it explicit now.

What is a reasonable assumption?  Many people think there is a reasonable
definition of "f( i ++ ) + f( i ++ )".

One of the traditional goals in C/C++ is to constraint the implementation
as little as possible.  You may disagree with that goal -- I'm not
convinced myself that it is right -- but it is one of the guiding
principles in the design of the language.  If you are going to insist
that the language defines "reasonable assumptions", you are going to
have a lot of rewording to do.

(Personally, I see nothing "reasonable" about supposing that a class
uses some particular representation internally, unless it is explicitly
documented to do so.)

> >Of course not.  Since it is not guaranteed.  But I find it hard to
> >believe that any professional has written code that depended on
> vectors
> >being contiguous.  Such code certainly wouldn't get through any
> serious
> >code reveiw.
>
> If vectors cannot be assumed to be contiguous, they cannot be used
> with functions that take a pointer and an element count, which is a
> very common scenario.

So common that I've never seen it in C++ code.

Some support is necessary for string/char*, because of the large amount
of legacy C code, including system interfaces.  I'm not aware of any
equivalent amount of code which uses arrays.  (Which isn't to say that
it doesn't exist, of course.  Perhaps in application specific libraries.)

Obviously, in C++ code, the situation doesn't occur, since any C++
code would expect either a vector<>&, or iterators:-).

> Workarounds are ugly and inefficient, and pretty
> much outweigh the benefits that vector offers. I want C++ to help me
> write good code, not to punish me for trying to make effective use of
> new language developments.
>
> >(Seriously, insofar as vector is the official alternative to C style
> >arrays, and there are no fixed length vectors which don't use dynamic
> >allocation, I would be extremely surprised if any implementation did
> >not use contiguous memory, since it results in additional run-time
> >overhead in operator[].
>
> Right.
>
> >My solution, however, would be to define a static
> >vector, whose length was a template argument, and which would
> guarantee
> >basically the same as what is guaranteed by C style arrays:
> contiguous
> >memory, no dynamic allocations within the vector, and the size
> >determined by size()*sizeof( ElementType ).
>
> A fixed-size array class is not very useful compared with the
> facilities that vector provides. And other than knowing it's own size,
> I can't think of any advantages it might offer over built-in arrays.

Well, it won't convert to a pointer at a drop of a hat, to begin with.
It can be passed and returned by value to and from a function.  In
general, it acts just like every other type (which built-in arrays
certainly don't).

--
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

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]


[ 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:
>
> Access in constant time means just that, and says nothing concerning
> the arrangement in memory.

I'm no mathematician, but it seems to me that the only arrangement that
could achieve constant time is either contiguous, or fixed sized pages
with a fixed number of levels of indirection. That leaves out a lot of
possible useful noncontiguous arrangements, because they'd be O*log(N).

--

Ciao,
Paul

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]



[ 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 wrote in message <6itnro$6oo@netlab.cs.rpi.edu>...
>Would a valarray<> serve your needs?

No - valarray is not a vector that happens to be contiguously
allocated. It is a fixed-size array designed for high-performance
numerics, and does not provide the facilities that make vector an
attractive alternative to built-in arrays.

- Jim

--
Jim Barry, Thermoteknix Systems Ltd., Cambridge, UK.
http://www.thermoteknix.co.uk Queen's Award for Export 1998
Antispam address courtesy of http://www.bigfoot.com
Or e-mail direct: jim at thermoteknix dot co dot uk



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]



[ 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 comp.std.c++ Jim Barry <jim.barry@bigfoot.com> wrote:
: jkanze@otelo.ibmmail.com wrote in message
: <6ipu9s$hm8@netlab.cs.rpi.edu>...
: >Unless I've misunderstood something, linear, in this context,
: >means that for i < j, if v[ i ] exists and v[ j ] exists, all
: >intermediate elements also exist.  (A linked list is also linear.)

: You could equally well take it to mean a linear arrangement in memory.

: >I presume that people make this assumption because of the name, and
: >not from anything in the description of the class.  And far too many
: >people just look at the implementation on their machine, and suppose
: >that it is universal.

: Among the people who make this assumption are two language experts I
: have consulted on the matter, one of whom invented C++.

They are both wrong. However, I betcha you will not find their
code which relies on this non-portable assumption.

: >The fact that people write incorrect code that happens to work on
: >one particular implementation is not a valid motive for modifying the
: >standard.

: The fact that a bunch of existing code relies on a reasonable
: assumption that nobody thought to make explicit in the standard is
: most certainly a reason to make it explicit now.

No it's not. Should we also mandate that after year 1999
comes year 1900, while we are at it?

: >Of course not.  Since it is not guaranteed.  But I find it hard to
: >believe that any professional has written code that depended on
: vectors
: >being contiguous.  Such code certainly wouldn't get through any
: serious
: >code reveiw.

: If vectors cannot be assumed to be contiguous, they cannot be used
: with functions that take a pointer and an element count, which is a
: very common scenario.

Right.

: Workarounds are ugly and inefficient,

Wrong. The workaround is not break a nice and beautiful
abstraction of a vector as we know it. The workaround
is to write your own containers for that. This
workaround is beautiful and efficient. It would be nice
if the standartization committee provided a standard
one, but it didn't happen. As usual, two wrongs will
not make right.

[...]

: A fixed-size array class is not very useful compared with the
: facilities that vector provides. And other than knowing it's own size,
: I can't think of any advantages it might offer over built-in arrays.

1. Ability to pass by value.
2. Absense of implicit DCD -- Deadly Conversion of Death (to pointer).
3. Proper interaction with inheritance.
4. No need to remember to use delete[] instead of delete. No need
   to introduce auto_array<>
5. Ability to supply useful constructors (iterator range, default
value).
6. Ability to initialize in the contructor initializer lists.
7. Copy constructor, copy assignement.
8. Readable begin(), end() methods.
9. as well as other vector-like parts of the interface.
10. Less shocking syntax. No f(int(&)[10]).
11. Ability to modify the implementation within the constraints
    of the interface.
12. No need to know if a particular type is a typedef for
    an array or not. See 1, 2, 3, 4, 7.

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

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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 am crossposting this reply to both comp.lang.c++.moderated and comp.std.c++.

 [Moderator's note: in fact the article was posted separately to both
 groups rather than cross-posted.  However, I have directed followups
 so that they will crosspost to both groups.
  -Moderator of comp.std.c++ (fjh).]

I think this issue regarding the implementation
of the STL <vector> class deserves some
concern.

jim.barry@bigfoot.com wrote

> I asked Bjarne Stroustrup about this, and he basically said that he
> though it was unlikely that a vector implementation would meet
>It was possible  to read the standard as requiring contiguous
>allocation. He suggested I send a request for clarification to the
>committee, so that's what I'll do.

Yes, please do!  I have read books that state that
vector is a CONTIGUOUS array.   I think a lot of
people are under that (mis)impression.  According
to "The STL Tutorial and Reference Guide" by
Musser and Saini (ISBN 0-201-63398-1) in section
19.3.3 it states that "Vectors are containers that
arrange elements of a given type in a strictly linear
arrangement and allow fast random access to any
element (i.e. any element can be accessed in
constant time). "  Of course this is just an author's
opinion not the ISO Standard.  Of course this goes
to show that others, (including myself) have made
the assumption that vectors are contiguous and
linear.  Frankly if the committee does not clarify
this in a such a manner as to support the idea
that vectors are contiguous it will necessitate
the rewrite of a great deal of code of which I
am aware.  I SERIOUSLY doubt that ANYONE
has written code that depends upon vectors
being NON-CONTIGUOUS.  For this reason
I encourage all involved parties to consider
clarifying the Standard so that it requires
vectors to be implemented in a contiguous
fashion.

Thanks to all!

Peter Garner
---
[ 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              ]

Peter Garner wrote:

> I think this issue regarding the implementation
> of the STL <vector> class deserves some
> concern.

I agree

> jim.barry@bigfoot.com wrote
>
> > I asked Bjarne Stroustrup about this, and he basically said that he
> > though it was unlikely that a vector implementation would meet
> >It was possible  to read the standard as requiring contiguous
> >allocation. He suggested I send a request for clarification to the
> >committee, so that's what I'll do.
>
> Yes, please do!

I don't think that's necessary. Many people use unportable
constructs, assume sizeof(long) = sizeof(int) = sizeof(T*)
for any T, clutter their code with far/_far/__far/
____veryfar, or that sub-functions exist in C. This doesn't
mean that a clarification is needed in the standard.

> I have read books that state that
> vector is a CONTIGUOUS array.

Then these books are bad.

> I think a lot of
> people are under that (mis)impression.

As with the above impressions.

> According
> to "The STL Tutorial and Reference Guide" by
> Musser and Saini (ISBN 0-201-63398-1) in section
> 19.3.3 it states that "Vectors are containers that
> arrange elements of a given type in a strictly linear
> arrangement and allow fast random access to any
> element (i.e. any element can be accessed in
> constant time). "

It depends on the definition of 'strictly linear arrangement'.
Every sequence is a linear arrangement of elements. But it
could also mean that the *representation* is 'strictly linear'.
To me, the natural interpretation is the former.

> Of course this goes
> to show that others, (including myself) have made
> the assumption that vectors are contiguous and
> linear.  Frankly if the committee does not clarify
> this in a such a manner as to support the idea
> that vectors are contiguous it will necessitate
> the rewrite of a great deal of code of which I
> am aware.

Would a member function data() help with this code ?
Two member functions, data and mutable_data ?

> I SERIOUSLY doubt that ANYONE
> has written code that depends upon vectors
> being NON-CONTIGUOUS.

As most implementations (all ?) are continuous, this
code would almost never work.

> For this reason
> I encourage all involved parties to consider
> clarifying the Standard so that it requires
> vectors to be implemented in a contiguous
> fashion.

But the standard is perfectly clear. I understand the
addition of a comment as this could be usual mis-interpretation.
But saying that the standard is unclear in order to
force a change isn't honest - OTOH arguing that the std
classes are unusable is ok (even if I disagre).

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]
---
[ 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              ]