Alain Miniussi wrote:

> Francis Glassborow wrote:

> > In article <37A1EF82.3C920D40@sophia.cnrs.fr>, Alain Miniussi
> > <alain@sophia.cnrs.fr> writes
> > >So, has an implementor, use a contiguous array, as a client, I will
> > >probably be happy with that choice. The point is, it's in the
> > >_standard_.
> >
> > Standards are about portability.  The question is very specific re
> > vector, should all programmers write code that assumes that the elements
> > of a vector may be non-contiguous because one day some stupid or
> > brilliant implementor (yes it could be either way) chooses a mechanism
> > for which contiguity is not an invariant.
>
> Yes.

Contiguous vectors have an important property: they give the
most efficient iterators possible: all ++ -- += -= == < are
one instruction, and * is free (I mean w/o checks -- even with
checks, it's pretty efficient).

If the user wants other caracterisitcs, like:
- large max_size on segement architectures
- efficient reallocations
- fast insertion near beginning
he should use a deque.

> And no one found a best accessor to that implementation than
> &(v.front()) ?

Yes, it's not pretty.

And there is no way to access it with an empty vector, so yu
have to write:

std::vector<int> vi;
int dummy;
if (v.empty())
    foo (&dummy, 0);
else
    foo (&v.front (), v.size());

> I mean, if the use of the contiguity is planed from the start, some
> decent way to access the data should have been provided (IMO)

Like:

    foo (v.data(), v.size());

?

> > Alternative collections (sequence mechanisms) were provided with
> > other costs.  To me, one of the great steps forward with the STL part of
> > the C++ Standard library was the specification of performance
> > guarantees.
>
> Yes, but I don't think we are talking about that.

We are talking about the implicit guaranty that vector is as fast
as it can be. If you want people to switch to vector, it's a very
important argument.

--

Valentin Bonnard
---
[ 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:

[...]

> And c_array as presented earlier in this thread is a fixed-size
> container. To really be useful it would need to be dynamic, and then it
> would look a lot like, well, vector. It seems like you want programmers
> to cart around their own home-grown vector look-alike to use when they
> run into C-style APIs.

If it is just for C style APIs, you probably only use it on PODs,
right? In this case, an implementation using malloc/realloc would
be possible, which would probably be faster anyway:

template<typename POD> class PodArray
{
public:
  PodArray(): arrsize(0), p(0) {}
  PodArray(size_t n): arrsize(n), p(malloc(n*sizeof(POD))) {}
  ~PodArray() { free(p); }
  void resize(size_t n) { p=realloc(p,n*sizeof(POD)); arrsize=n; }
  POD* begin() { return p; }
  POD* end() { return p+size; }
  size_t size() { return arrsize; }
private:
  size_t arrsize;
  POD* array;
};

Of course you can change this to be more vector-like by
maintaining separate capacity and size, and by supporting
back() and push_back() and whatever else you need.
Some error checking on malloc/realloc would be a good
idea as well.

[...]


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

P.J. Plauger <pjp@plauger.com> wrote...
>
> It turns out that vector could really profit from being
> implemented as a circular buffer stored in an array.

In what way? Did you write about it in an article?
---
[ 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              ]

Francis Glassborow wrote:
>
> In article <37A1EF82.3C920D40@sophia.cnrs.fr>, Alain Miniussi
> <alain@sophia.cnrs.fr> writes
> >So, has an implementor, use a contiguous array, as a client, I will
> >probably be happy with that choice. The point is, it's in the
> >_standard_.
>
> Standards are about portability.  The question is very specific re
> vector, should all programmers write code that assumes that the elements
> of a vector may be non-contiguous because one day some stupid or
> brilliant implementor (yes it could be either way) chooses a mechanism
> for which contiguity is not an invariant.

Yes.

> Most of those involved in the design intended that contiguity of
> elements was a class invariant for vector (at the none cost of
> invalidating iterators, cost of copying elements when expanding a vector
> etc.)

And no one found a best accessor to that implementation than
&(v.front()) ?
I mean, if the use of the contiguity is planed from the start, some
decent way to access the data should have been provided (IMO)

> Alternative collections (sequence mechanisms) were provided with
> other costs.  To me, one of the great steps forward with the STL part of
> the C++ Standard library was the specification of performance
> guarantees.

Yes, but I don't think we are talking about that.

>  Compare the various C++ sorting mechanisms with C's qsort()
> which provides no performance guarantees (apart from the fact that it
> explicitly is not required to be a stable sort)


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

Alain Miniussi wrote:

> (hash set are usefull, general purpose, not in the
> standard and do not need to be home-grown).

But they would be a lot more useful if they were in the standard. ;-)

> So, you too are involved in that conspiracy ? I should have guessed
> ;-)

You lost me there. What do you mean?

> Consider <string> for example, one could just apply your argument
> to string implementation.

That is a valid point, and one that I have considered. I think that the
usage patterns of strings and vectors are sufficiently different that
they cannot really be compared. I am told that there are existing
non-contiguous string implementations that deliver tangible benefits.
But the people who tell me that do not seem to think that the same
applies to vector.

> And if vector wa supposed to be used that way from the start, the
> internal buffer would be accessible with a real accessor, not
> &(v.front()).

Perhaps so. I would use &v[0] myself. Of course you could also write
that for a deque but you wouldn't expect it to work. ;-)

> So you're not completly convinced ? :-)

I don't say that it's impossible, only improbable. The benefits of
making vector contiguous seem to outweigh any benefits that a
non-contiguous vector is likely to offer.
---
[ 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 ...
>P.J. Plauger <pjp@plauger.com> wrote...
>>
>> It turns out that vector could really profit from being
>> implemented as a circular buffer stored in an array.
>
>In what way? Did you write about it in an article?

No, I haven't written about it yet. But my Java version of vector
is a circular buffer, and I find I use it in most places where one
would normally use the much more complex deque. The main
thing it gets you is push_front and push_back both work in
constant time if there's any reserve storage at all.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ 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:
>
> Alain Miniussi wrote:

> > Consider <string> for example, one could just apply your argument
> > to string implementation.

At least string provides data.

> I don't say that it's impossible, only improbable. The benefits of
> making vector contiguous seem to outweigh any benefits that a
> non-contiguous vector is likely to offer.

The point here is that contiguous vector gives real benefits
while vector with unspecified contiguity gives hypothetical
benefits.

And

  s/vector/any_std_class/
  s/contiguous/any_guaranty/

in the above.

--

Valentin Bonnard
---
[ 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 <37A5D56D.1310@wanadoo.fr>, Valentin Bonnard
<Bonnard.V@wanadoo.fr> wrote:

> Jim Barry wrote:
> >
> > Alain Miniussi wrote:
>
> > > Consider <string> for example, one could just apply your argument
> > > to string implementation.
>
> At least string provides data.
>
> > I don't say that it's impossible, only improbable. The benefits of
> > making vector contiguous seem to outweigh any benefits that a
> > non-contiguous vector is likely to offer.
>
> The point here is that contiguous vector gives real benefits
> while vector with unspecified contiguity gives hypothetical
> benefits.

So constant-time insertion at the beginning and end is hypothetical?

I think it's clear now that this all comes down to a question of
granularity, and the inherent tradeoffs. Two different vector classes,
where one exposes a C-style array representation, and the other doesn't
(thus allowing implementors to use more efficient representation). Is
providing to too much for the standard? Should the user provide their own
if they want the implementation to be less-restrictive?


[ 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 <37A1EF82.3C920D40@sophia.cnrs.fr>, Alain Miniussi
<alain@sophia.cnrs.fr> writes
>So, has an implementor, use a contiguous array, as a client, I will
>probably be happy with that choice. The point is, it's in the
>_standard_.

Standards are about portability.  The question is very specific re
vector, should all programmers write code that assumes that the elements
of a vector may be non-contiguous because one day some stupid or
brilliant implementor (yes it could be either way) chooses a mechanism
for which contiguity is not an invariant.

Most of those involved in the design intended that contiguity of
elements was a class invariant for vector (at the none cost of
invalidating iterators, cost of copying elements when expanding a vector
etc.)  Alternative collections (sequence mechanisms) were provided with
other costs.  To me, one of the great steps forward with the STL part of
the C++ Standard library was the specification of performance
guarantees.  Compare the various C++ sorting mechanisms with C's qsort()
which provides no performance guarantees (apart from the fact that it
explicitly is not required to be a stable sort)

Francis Glassborow      Journal Editor, Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
[ 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              ]

P.J. Plauger wrote:

> (First rule of optimization: customers always want highly predictable
> behavior except when they want the code to go really fast. Then they
> want both.)

;-)

> It turns out that vector could really profit from being implemented as a
> circular buffer stored in an array.

Profit in which case ?

When the user wants to use ``vector::push_front''
(ie v.insert (v.begin (), ...)) -- when he should
have used a deque.

But for iterators, ++/-- will be about twice slower,
<, > between 3 times slower, += four times slower.

That is, when the user really wants a vector for its
caracterisitcs: efficient insert/erase only near end,
efficient iterator operations, he looses.

> The C++ Standard *almost* permits
> this representation, but not quite. So it is what it is.

I think that the current standard  (that is, w/o the
contiguity requirement) allows it.

--

Valentin Bonnard


[ 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 <sM7m3.2039$2b.354613@nnrp.gol.com>, davidjl@gol.com
says...

[ ... ]

> In general, I find the idea of taking the address of an element in a
> standard container to be a very strange idea, since the idea behind the
> containers is that they store _values_ not memory representations.
>
> Have I missed something?

I'm not sure -- I can, however, see situations in which it's useful to
do this sort of thing.  Just for example, at times quite a few OSes
require the base addresses of arrays of objects you want them to
operate on.  If vector<> (for example) can use noncontiguous storage,
that means you can't use a vector to store objects for this sort of
situation.

In short, containers not only have to be internally consistent but
also, at least at times, have to interact with the outside world.  For
internal consistency, almost any sort of storage will work as long as
the member functions and operators are overloaded correctly.  For
interaction with the outside world, the requirements can become more
stringent though.

Quite a bit of the time you could deal with things like this by
copying your entire array from the vector<> to a valarray<>.  If you
had to do this very often at all, the copying itself would probably
outweigh any savings you got from using non-contiguous storage for
vector<>.  In addition, in this scenario, you'd need all the storage
necessary for two complete copies of the array, at least temporarily.


[ 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 problems with contiguous arrays are:
> - difficult to reallocate (must copy the whole thing)
> - limited max_size on segmented architectures

I know you don't like it, but the answer in both cases is to use deque.
The presence of vector::reserve seems to me a strong hint that vector is
not the best choice for a collection that changes size often. In fact,
it has been suggested (e.g. GOTW #54) that deque is generally preferable
to vector. The segmented architecture issue is tricky, but remember that
the maximum size of built-in arrays is limited in the same way. A vector
implementation on a segmented architecture that allowed a large element
count would probably perform more like a deque anyway.

--
Jim Barry, Thermoteknix Systems Ltd., Cambridge, UK.
http://www.thermoteknix.co.uk - Queen's Award for Export 1998
http://www.geocities.com/SiliconValley/2060



[ 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:
> Hum. Given its obvious answer, I was surprised by your question.

Too much holidays :-)

> > The requirement could be restricted to vector<char>.
> How the type ``char'' is a special case is beyond me.

Well, restricted to types used for buffering in C APIs.

> > So my question is, was there a real argumentation, or did it just
> > seems to be a good idea at the time ? (I don't think so, but I would
> > like to be sure).
>
> Well, it seemed obvious to anyone (but me) that vector should be
> contiguous. Some people (probably including BS) also said that
> it was something that everyone had in mind since the beginning,
> and that they just realised that this requirement wasn't written
> in the standard.

Ok, I am worried by that kind of poccess but it answer the question.

Thanks

Alain
---
[ 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 <37989AFF.7B98@wanadoo.fr>,
  Valentin Bonnard <Bonnard.V@wanadoo.fr> wrote:
> Well, it seemed obvious to anyone (but me) that vector should be
> contiguous. Some people (probably including BS) also said that
> it was something that everyone had in mind since the beginning,
> and that they just realised that this requirement wasn't written
> in the standard.
>
> The problems with contiguous arrays are:
> - difficult to reallocate (must copy the whole thing)
> - limited max_size on segmented architectures
>
> --
>
> Valentin Bonnard

If someone is worried about the cost of copying the elements, they
should use a deque instead of a vector.

If you do not guarantee the contiguity (is that a word?) of vector,
what you have left is a deque. (Actually a semi-crippled deque, because
front inserts would not be performed in constant time)

I have been using vector as a replacement for primitive buffers for
some time now.  I always feel like I am cheating and dirty when I do
something like
{
//...
  vector<char> myVector;
  myVector.resize( someDynamicSize );
  int bytes = read( fd , myVector.begin() , myVector.capacity() );
//...
}

Can I do this without using vector? Sure. But I think it looks less
readable.
{
  char * pBuffer = NULL;
  // ...
  try
  {
    pBuffer = new char[ someDynamicSize ];
    int bytes = read( fd , pBuffer , someDynamicSize );
    // ...
    delete[] pBuffer;
  }
  catch (...)
  {
    delete[] pBuffer;
    throw;
  }
}

But why should I write code to  dynamically allocate and delete memory
in an exception-safe manner, when I have such a convenient and safe way
of managing a buffer?  Every extra line of code written is an
opportunity for bugs as well as making the code less readable.

I would love it if there were a guarantee of contiguous memory along
with a portable way of accessing the buffer.
Perhaps a function, vector<T>::begin_data(), that is defined as
returning a T*.
In every vector implementation I have seen begin_data() would be the
same as begin(), but it would be portable to a vector implementation
that decided to use something other than a primitive pointer as an
iterator.

BTW,
I think that the efficiency semantics
Mark Borgerding
mborgerding (at) acm.org


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
---
[ 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:
>
> Alain Miniussi wrote:
> ...
> > It seems that there should be a very good reason for freezing the
> > vector implementation in such a way and enabling the reachability
> > of any element from front. And compatibility with C api does
> > not seems to be valid for various reasons: if the api is
> > really usefull, the C++ api can be done or is already done.
>
> That's a highly optimistic assumption.

Not really optimistic, it's just that, after a few years, I don't
see a lot of data that does against that assumption. But I am
ready to accept "optimistic", that's not really the important point.

> There's a whole lot of C code out there;
> no one has the time to rewrite all of it in a C++ compatible
> form. No one even has time to write C++ wrappers for all of it,

If true, considering the small amount of time needed to build such
wrappers (considering that the wrapper need to be wrote only once,
that you're supposed to spend time reading the C documentation etc...)
I would not trust the developper who consider that (s)he doesn't have
time to pend on that problem (because then, I will think that (s)he
does not even spend time reading the documentation).

Note that the time spent in putting that extra requirement on
vector can be considered as time spent in finding a solution to that
problem. So, someone had that time to spend, and the cost was not
considered prohibitive. The problem is the validity of the solution.

One last point: there a lot of languages (well, all language but
C and C++) that can afford that.

> and the
> kind of wrapper needed for this case is fairly expensive. In the general
> case, where the C code both reads and writes from the array passed by a
> pointer, the wrapper has to create a temporary array, copy into from an
> iterator range, then copy out from it to the iterator range after the
> function call. This is a particularly galling inefficiency,

Correct arguments, that can justify the creation of some c_buffer
template.
If that template become stable, then c_buffer can be considered for
integration in the standard. (in the meantime, it can be used whitout
being in the standard).

> given that
> virtually every real implementation does in fact possess contiguous
> memory,

I don't accept that argument. It implies that if, at some point (ie
today),
an implementation is considered "good enough", you can throw away the
notion
of encapsulation, and not just for today. I think encapsulation should
be
more respected than that.

> and that the only justification for this wrapper is that the
> standard doesn't guarantee it.

No, the justification is that another solution does not exist, I am
not sure that the purpose of a standard is to decide the best
implementation for a general purpose template.

23.2.4/1 does not indicate: "vector is a wrapper around an publicaly
accessible array" (well, it should, in the next version).


Thank you (and to Valentin) I got the answer to my questions.

Alain
---
[ 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 26 Jul 1999 18:50:03 GMT, "Jim Barry" <jim.barry@bigfoot.com> wrote:
>Valentin Bonnard wrote:
>> The problems with contiguous arrays are:
>> - difficult to reallocate (must copy the whole thing)
>> - limited max_size on segmented architectures
>
>I know you don't like it, but the answer in both cases is to use deque.

I agree, but in fairness let me add a caveat: Be aware that not everyone
agrees with me about deque. I say a few more words about this in the
October 1999 issue of C++ Report.

Having said that, I do think that everything you're saying here is
perfectly valid.

>The presence of vector::reserve seems to me a strong hint that vector is
>not the best choice for a collection that changes size often. In fact,
>it has been suggested (e.g. GOTW #54) that deque is generally preferable
>to vector.

Right, except for those specific cases where measurement shows that the
(often small) performance difference does matter.

> The segmented architecture issue is tricky, but remember that
>the maximum size of built-in arrays is limited in the same way. A vector
>implementation on a segmented architecture that allowed a large element
>count would probably perform more like a deque anyway.

Good point. I'd go further: It would pretty much have to be a deque.

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

PeerDirect Inc.     2695 North Sheridan Way, Suite 150
www.peerdirect.com  Mississauga Ontario Canada L5K 2N6
---
[ 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 <7nhu8q$hmf$1@nnrp1.deja.com>, mborgerd@my-deja.com wrote:

> In article <37989AFF.7B98@wanadoo.fr>,
>   Valentin Bonnard <Bonnard.V@wanadoo.fr> wrote:
> > Well, it seemed obvious to anyone (but me) that vector should be
> > contiguous. Some people (probably including BS) also said that
> > it was something that everyone had in mind since the beginning,
> > and that they just realised that this requirement wasn't written
> > in the standard.
[snip]
> I have been using vector as a replacement for primitive buffers for
> some time now.  I always feel like I am cheating and dirty when I do
> something like
> {
> //...
>   vector<char> myVector;
>   myVector.resize( someDynamicSize );
>   int bytes = read( fd , myVector.begin() , myVector.capacity() );
> //...
> }
>
> Can I do this without using vector? Sure. But I think it looks less
> readable.

Really?

// library

    template<typename T>
    class c_array {
        T* const  p;
        std::size_t const size;
        c_array( c_array const& );
        c_array& operator = ( c_array const& );
    public:
        c_array( std::size_t s ) : p( new T [s] ), size( s ) { }
        ~c_array() { delete [] p; }

        T* begin() const { return p; }
        std::size_t size() const { return size; }
    };

// your example

    c_array<char> buffer( someDynamicSize );
    int bytes = read( fd, buffer.begin(), buffer.capacity() );

Wow, that sure is much less readable :-)

c_array can be expanded as necessary (to support more of the STL container
interface).

[snip]

> But why should I write code to  dynamically allocate and delete memory
> in an exception-safe manner, when I have such a convenient and safe way
> of managing a buffer?
[snip]

I agree. Using something similar to c_array<> is very convenient. What was
the problem again?
---
[ 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:

> And actually, the complexity
> requirements make it implausible to implement vector any other way.

I am strongly in favor of contiguous vector, because
it helps when you want to interract with C-arrays.

But your argument (quoted above), simply saying that some
implementation is obvious and that others are <<implausible>>
is preciselly the kind of argument I dislike in this discussion.

--

Valentin Bonnard
---
[ 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 <01a101bed9d3$73f53850$6400000a@thermoteknix.co.uk>...
>I cannot really understand your hostile attitude. As a user of vector,
>if you need contiguity then you will be glad if it is there. If not,
>then it does not affect you. As an implementor of vector, the constraint
>should only make your job simpler. And actually, the complexity
>requirements make it implausible to implement vector any other way.

Overspecification very seldom makes an implementor's job easier.
Okay, so you have an excuse to do a job the One Right Way -- if
customers complain, they're still mad at you, not the C++ Standard.
(First rule of optimization: customers always want highly predictable
behavior except when they want the code to go really fast. Then they
want both.)

It turns out that vector could really profit from being implemented as a
circular buffer stored in an array. The C++ Standard *almost* permits
this representation, but not quite. So it is what it is.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ 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:

> I am strongly in favor of contiguous vector, because
> it helps when you want to interract with C-arrays.
>
> But your argument (quoted above), simply saying that some
> implementation is obvious and that others are <<implausible>>
> is preciselly the kind of argument I dislike in this discussion.

I concede that it is only a secondary argument. All I really meant was
that if there were existing or likely non-contiguous vector
implementations, then requiring contiguity would not be a serious
option. Fortunately, there are not. I think that vector is a special
case, as you do also. I do not, for example, think that the standard
should say that a map has to be implemented as a red-black tree.
---
[ 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:
>
> Alain Miniussi wrote:
> > So what ? Are you suggesting that it justify the adoption of a
> > quick and dirty kludge ? c_array illustrate the fact what the
> > argument "we don't have time to write wrappers, let sacrifice
> > vector because {every one use that implementation anyway, I save
> > me one template, it's next on the alphabetical order[?], I already
> > use it that way, other}" does not hold.
>
> It's not (just) a matter of having time to write wrappers. Without a
> guarantee of contiguity, the wrapper is inherently inefficient because
> it must allocate a temporary buffer to pass to the C-style API, then
> copy the elements from the buffer into the vector.

Right, that would be a bad implementation for buffers.

> And c_array as presented earlier in this thread is a fixed-size
> container. To really be useful it would need to be dynamic, and then it
> would look a lot like, well, vector.

Right. A shared implementation would probably be a good thing, from
the implementor point of vue. My point is that that kind of argument
should consider by implementor, not standardisation.

> It seems like you want programmers
> to cart around their own home-grown vector look-alike to use when they
> run into C-style APIs.

Well, I am not a big fan of that kind of solution. Now, if a usefull
and general purpose thing is not in the standard, one solution is to
argue for it's inclusion. And the intermediate workaroud does not need
to be home-grown (hash set are usefull, general purpose, not in the
standard and do not need to be home-grown).

> I cannot really understand your hostile attitude.

So, you too are involved in that conspiracy ? I should have guessed
;-)

> As a user of vector,
> if you need contiguity then you will be glad if it is there. If not,
> then it does not affect you.

Well, maybe that's the core of the argument:
If I don't need a requirement, the requirement is just a limitation
for the implementor, thus it can potentialy affect.

Consider <string> for example, one could just apply your argument
to string implementation.

Now, I think that contiguity is probably a good thing for vector
and I don't see how that limitation could affect me as a user not
concern by contiguity _but_ I don't think that this is a good reason
to specify the contiguity requirement in the standard because the
previous statement is different from
"contiguity is a good thing for vector and that limitation cannot
affect me as a user not concerned by contiguity" which is probably
very hard (impossible?) to establish and is the kind of thing dangerous
to assume when unproven (in a standard). And frankly, I don't really
care about vector, I have no real problem with _that_ decision, what
really annoy me is the question "who's next ?".

And if vector wa supposed to be used that way from the start, the
internal buffer would be accessible with a real accessor, not
&(v.front()).

> As an implementor of vector, the constraint
> should only make your job simpler.

So, has an implementor, use a contiguous array, as a client, I will
probably be happy with that choice. The point is, it's in the
_standard_.

> And actually, the complexity
> requirements make it implausible to implement vector any other way.
                       ^^^^^^^^^^^^
So you're not completly convinced ? :-)

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

blargg wrote:
> mborgerd@my-deja.com wrote:
> > But why should I write code to  dynamically allocate and delete
memory
> > in an exception-safe manner, when I have such a convenient and safe
way
> > of managing a buffer?
>
> I agree. Using something similar to c_array<> is very convenient. What
was
> the problem again?

One problem is that c_array is not in the standard library.

--
Jim Barry, Thermoteknix Systems Ltd., Cambridge, UK.
http://www.thermoteknix.co.uk - Queen's Award for Export 1998
http://www.geocities.com/SiliconValley/2060
---
[ 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:
>
> blargg wrote:
> > mborgerd@my-deja.com wrote:
> > > But why should I write code to  dynamically allocate and delete
> memory
> > > in an exception-safe manner, when I have such a convenient and safe
> way
> > > of managing a buffer?
> >
> > I agree. Using something similar to c_array<> is very convenient. What
> was
> > the problem again?
>
> One problem is that c_array is not in the standard library.

So what ? Are you suggesting that it justify the adoption of a
quick and dirty kludge ? c_array illustrate the fact what the
argument "we don't have time to write wrappers, let sacrifice
vector because {every one use that implementation anyway, I save
me one template, it's next on the alphabetical order, I already
use it that way, other}" does not hold.
There are a few documents explaining why encapsulation
is great and why breaking encapsulation is bad, which is
another problem (you can probably find one usefull application
to the use of the underlying of any standard class, does it
justify the removal of "private" ?)

Alain


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

Alain Miniussi wrote:
> So what ? Are you suggesting that it justify the adoption of a
> quick and dirty kludge ? c_array illustrate the fact what the
> argument "we don't have time to write wrappers, let sacrifice
> vector because {every one use that implementation anyway, I save
> me one template, it's next on the alphabetical order[?], I already
> use it that way, other}" does not hold.

It's not (just) a matter of having time to write wrappers. Without a
guarantee of contiguity, the wrapper is inherently inefficient because
it must allocate a temporary buffer to pass to the C-style API, then
copy the elements from the buffer into the vector.

And c_array as presented earlier in this thread is a fixed-size
container. To really be useful it would need to be dynamic, and then it
would look a lot like, well, vector. It seems like you want programmers
to cart around their own home-grown vector look-alike to use when they
run into C-style APIs.

I cannot really understand your hostile attitude. As a user of vector,
if you need contiguity then you will be glad if it is there. If not,
then it does not affect you. As an implementor of vector, the constraint
should only make your job simpler. And actually, the complexity
requirements make it implausible to implement vector any other way.
---
[ 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 <379F5EBB.9F899B02@sophia.cnrs.fr>, Alain Miniussi
<alain@sophia.cnrs.fr> wrote:

> Jim Barry wrote:
> >
> > blargg wrote:
> > > mborgerd@my-deja.com wrote:
> > > > But why should I write code to  dynamically allocate and delete
> > memory
> > > > in an exception-safe manner, when I have such a convenient and safe
> > way
> > > > of managing a buffer?
> > >
> > > I agree. Using something similar to c_array<> is very convenient. What
> > was
> > > the problem again?
> >
> > One problem is that c_array is not in the standard library.
>
> So what ? Are you suggesting that it justify the adoption of a
> quick and dirty kludge ? c_array illustrate the fact what the
> argument "we don't have time to write wrappers, let sacrifice
> vector because {every one use that implementation anyway, I save
> me one template, it's next on the alphabetical order, I already
> use it that way, other}" does not hold.
> There are a few documents explaining why encapsulation
> is great and why breaking encapsulation is bad, which is
> another problem (you can probably find one usefull application
> to the use of the underlying of any standard class, does it
> justify the removal of "private" ?)

That said, there should be an encapsulating (really encapsulating <shrug>)
vector that can implement its storage however damn well it pleases, and
the current one which will now be required to implement its storage as a
contiguous array.

I don't really have a problem with this, except the possible unnecessary
multiplicity of entities.
---
[ 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:
>
> Alain Miniussi wrote:
>
> > Gabriel Dos_Reis wrote:
>
> > > valarray<> is guaranteed by the current standard to be contiguous.
> > > vector<> will be, thanks to the next TC.
> >
> > Could someone enumerate the argument used for vector ? (or point me
> > to some documentation).
>
> void get_one_line_from_socket (Socket&, char* out, size_t max_size);
>
> std::vector<char> v (100);
> get_one_line_from_socket (my_sock, &v.front(), 100); // will be ok
>                                                      // after next TC

I knew that argument, just that it seems weak to me and I would like
to know if there are others arguments.

It is generaly considered a good practice to specify api (and, for
container, complexity requirement) and let the implementation satisfy
these requirement to the best of their possibility depending on the
situation (and it's even more important for standard classes, where
compiler can take advantage of the class semantic).

With that decision, _all_ vector (not only the ones potentially usefull
for C api, that is vector<char>, that could have been specialized) need
to be implemented as a public array of strictly contiguous elements
(which is probably the best choice (which doe not sound as a very wise
argument) but maybe not)

It seems that there should be a very good reason for freezing the
vector implementation in such a way and enabling the reachability
of any element from front. And compatibility with C api does
not seems to be valid for various reasons: if the api is
really usefull, the C++ api can be done or is already done. Specific
stream buffers could be used as an alternative. The requirement could
be restricted to vector<char>. It was not considered a good idea
for basic_string (and some are not implemented with a simple
array of character, which seems to indicate that it was not a good
idea). If the api is not part of the standard, that's the implementation
job to provide the good api.

There are also potential counter arguments: maybe vector was supposed,
from the start, to be just a wrapper around C arrays, not an abtraction,
and that any other implementation should be implemented with another
template (after all, the STL is built in order to enable easy
assimilation
of new containers). Vector can be replaced, string can't (well, in
most case).

So my question is, was there a real argumentation, or did it just
seems to be a good idea at the time ? (I dont think so, but I would
like to be sure).

Alain


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

Alain Miniussi wrote:

> Valentin Bonnard wrote:

> > Alain Miniussi wrote:
> >
> > > Gabriel Dos_Reis wrote:
> >
> > > > valarray<> is guaranteed by the current standard to be contiguous.
> > > > vector<> will be, thanks to the next TC.
> > >
> > > Could someone enumerate the argument used for vector ? (or point me
> > > to some documentation).
> >
> > void get_one_line_from_socket (Socket&, char* out, size_t max_size);
> >
> > std::vector<char> v (100);
> > get_one_line_from_socket (my_sock, &v.front(), 100); // will be ok
> >                                                      // after next TC
>
> I knew that argument, just that it seems weak to me and I would like
> to know if there are others arguments.

Hum. Given its obvious answer, I was surprised by your question.

> With that decision, _all_ vector (not only the ones potentially usefull
> for C api, that is vector<char>, that could have been specialized) need
> to be implemented as a public array of strictly contiguous elements

Correct

> It seems that there should be a very good reason for freezing the
> vector implementation in such a way and enabling the reachability
> of any element from front.

Yes, and many people think that there is.

> The requirement could be restricted to vector<char>.

How the type ``char'' is a special case is beyond me.

> So my question is, was there a real argumentation, or did it just
> seems to be a good idea at the time ? (I don't think so, but I would
> like to be sure).

Well, it seemed obvious to anyone (but me) that vector should be
contiguous. Some people (probably including BS) also said that
it was something that everyone had in mind since the beginning,
and that they just realised that this requirement wasn't written
in the standard.

The problems with contiguous arrays are:
- difficult to reallocate (must copy the whole thing)
- limited max_size on segmented architectures

--

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

Alain Miniussi wrote:
...
> It seems that there should be a very good reason for freezing the
> vector implementation in such a way and enabling the reachability
> of any element from front. And compatibility with C api does
> not seems to be valid for various reasons: if the api is
> really usefull, the C++ api can be done or is already done.

That's a highly optimistic assumption. There's a whole lot of C code out
there; no one has the time to rewrite all of it in a C++ compatible
form. No one even has time to write C++ wrappers for all of it, and the
kind of wrapper needed for this case is fairly expensive. In the general
case, where the C code both reads and writes from the array passed by a
pointer, the wrapper has to create a temporary array, copy into from an
iterator range, then copy out from it to the iterator range after the
function call. This is a particularly galling inefficiency, given that
virtually every real implementation does in fact possess contiguous
memory, and that the only justification for this wrapper is that the
standard doesn't guarantee it.
---
[ 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 in message <37989AFF.7B98@wanadoo.fr>...

>The problems with contiguous arrays are:
>- difficult to reallocate (must copy the whole thing)
>- limited max_size on segmented architectures


One more: It may not be possible to reallocate in a running program that has
fragmented its address space. (push_back() will fail far sooner than it
might otherwise.)

Still, since nearly all implementations use contiguous arrays, the above are
somewhat hypothetical.

Here are two objections that aren't irrelevant in implementations that use
contiguous arrays:

The addresses of objects contained in an array is not guaranteed not to
change: when push_back() grows a vector, anyone holding onto an old address
of an element is in trouble. Very thread unsafe. C arrays don't move around
in memory, and are the correct abstraction to use when passing data to OS or
C api functions that think in those terms.

The thing I find most strange about a contiguous guarantee for vector is
that the only way to get the address of the start of the memory would be
&vec[0]. The problem with this is that as a _container_ for objects, the
meaning (type) of &vec[0] is the address of the individual object stored. In
other words, it corresponds to a wart in the type system. I thought the idea
of C++ was to fix the problems with typing in C. This would seem to be
reverting to the same old type sloppiness C++ was trying to get away from.

In general, I find the idea of taking the address of an element in a
standard container to be a very strange idea, since the idea behind the
containers is that they store _values_ not memory representations.

Have I missed something?

David J. Littleboy
---
[ 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              ]

Alain Miniussi wrote:

> Gabriel Dos_Reis wrote:

> > valarray<> is guaranteed by the current standard to be contiguous.
> > vector<> will be, thanks to the next TC.
>
> Could someone enumerate the argument used for vector ? (or point me
> to some documentation).

void get_one_line_from_socket (Socket&, char* out, size_t max_size);

std::vector<char> v (100);
get_one_line_from_socket (my_sock, &v.front(), 100); // will be ok
                                                     // after next TC

You get the point.

--

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