poenitz@gmx.net (Andr    P   nitz) wrote in message news:<b9d60b$qf7$1@narses.hrz.tu-chemnitz.de>...
> Howard Hinnant <hinnant@metrowerks.com> wrote:
> > It depends on how you define movable.  I prefer to define movable as
> > something with the semantics of auto_ptr "copy", but not with the
> > syntax of copy.  Indeed it is my humble opinion that moving with copy
> > syntax is a design flaw.
>
> My personal idea of  move(to, from)  is "make 'to' a copy of 'from' and
> leave 'from' in a state suitable for destruction".
>
> So  both  operator=()  and  std::swap() are "legal" replacements, and
> move() could simply use (by overloading) whatever is faster for a given
> type.

Why don't we invent a new operator, such as "operator~=" ?

    class X
    {
        X& operator=(const X&);     // copy
        X& operator~=(X&);          // move
    }

--
KIM Seungbeom <musiphil@bawi.org>

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

In article <bd47bb0e.0305082140.757e121d@posting.google.com>, KIM
Seungbeom <musiphil@bawi.org> wrote:

| poenitz@gmx.net (Andr=E9 P=F6nitz) wrote in message
| news:<b9d60b$qf7$1@narses.hrz.tu-chemnitz.de>...
| > Howard Hinnant <hinnant@metrowerks.com> wrote:
| > > It depends on how you define movable.  I prefer to define movable a=
s
| > > something with the semantics of auto_ptr "copy", but not with the
| > > syntax of copy.  Indeed it is my humble opinion that moving with co=
py
| > > syntax is a design flaw.
| >=20
| > My personal idea of  move(to, from)  is "make 'to' a copy of 'from' a=
nd
| > leave 'from' in a state suitable for destruction".
| >=20
| > So  both  operator=3D()  and  std::swap() are "legal" replacements, a=
nd
| > move() could simply use (by overloading) whatever is faster for a giv=
en
| > type.
|=20
| Why don't we invent a new operator, such as "operator~=3D" ?
|=20
|     class X
|     {
|         X& operator=3D(const X&);     // copy
|         X& operator~=3D(X&);          // move

Both suggestions above [move(to,from) and op~=3D] assume that the only
time we need move semantics is in implementing a move assignment
operator.  However move assignment is not the only time you want to
move.

A move constructor can also be very handy.  Consider:

template <class T>
void
swap(T& x, T& y)
{
    T tmp(move(x));
    x =3D move(y);
    y =3D move(tmp);
}

In this example, swap makes good use of both a move constructor, and
move assignment.

And the list doesn't stop there.

Containers could make good use of move semantics when inserting values.=20
For example, maybe the client has a heavy object that he wants to move
into a vector instead of copy it in:

vector<Heavy> v;
Heavy h;
....
v.push_back(move(h));  //  moving push_back

It would be extremely elegant if the moving version of push_back would
be automatically called when given a temporary Heavy:

v.push_back(create_a_Heavy());  // moving push_back

Another application could be in optimizing operator+ for a String class:

String operator+(const String& x, const String& y)
{
   String r(x);
   r +=3D y;
   return r;
}

String operator+(MoveFromThis String& x, const String& y)
{
   x +=3D y;
   return x;
}

....

String s1, s2, s3, s4;
....
String s0 =3D s1 + s2 + s3 + s4;

In this example "s1 + s2" happens as usual (without move semantics).=20
But the result of that operation should be moved from.  There is no
need to create a new temporary to append s3 to.  Just append s3 (and
s4) to the temporary created from the previous operation.  The
temporary that is continually being appended to will probably work up
enough excess capacity that it won't even have to go to the heap.  It
should be effectively the same as:

String s0 =3D s1 + s2;
s0 +=3D s3;
s0 +=3D s4;

And if s0 gets contructed via RVO, then things are really moving well!
:-)

These examples are meant to demonstrate several things:

1.  Don't move with copy syntax from lvalues.
2.  Do move with copy syntax from rvalues.
3.  There are many times when you might want to move (many more than I
have imagined I'm sure).

--=20
Howard Hinnant
Metrowerks

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

Howard Hinnant <hinnant@metrowerks.com> wrote:
> It depends on how you define movable.  I prefer to define movable as
> something with the semantics of auto_ptr "copy", but not with the
> syntax of copy.  Indeed it is my humble opinion that moving with copy
> syntax is a design flaw.

My personal idea of  move(to, from)  is "make 'to' a copy of 'from' and
leave 'from' in a state suitable for destruction".

So  both  operator=()  and  std::swap() are "legal" replacements, and
move() could simply use (by overloading) whatever is faster for a given
type.

Andre'

--
Those who desire to give up Freedom in order to gain Security, will not have,
nor do they deserve, either one.     (T. Jefferson or B. Franklin or both...)

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

qrczak@knm.org.pl ("Marcin 'Qrczak' Kowalczyk") wrote in message news:<1315773.3X0zHOGsjL@qrnik.knm.org.pl>...
> witoldk wrote:
>
> > I take your statement to mean: memcpy is the wrong solution, because
> > there is no way to prove it would work. Discussing whether the wrong
> > solution could/would/might/is optimal is quite pointless.
>
> I meant that the current C++ as a language is not optimal in this respect.

I'm not sure I understand. You say that the fact that _generic_ container
must not use the techniqe good for only some _specific_ types of contained
objects makes C++ not optimal. How come?

> If illegal C++ can be much faster than legal C++, perhaps the problem is in
> the laws.

Taking your point further one might say that _any_ illegal language
can be much faster than the legal language :)


> And I've seen one way to improve them (the proposal about moving
> constructors and moving assignment).

Yes, efficiency seems to be the goal. I personally hope move semantic
would make RVO obsolete :)

> C++ implementations can painfully and partially improve the situation even
> in current C++. Namely they can provide specializations of containers for
> standard types which implement resizing better, with the knowledge of the
> representation of the element types or just the knowledge that memcpy works
> for them.

Please. Want specialized container? I'm afraid _you_ have to write it.
STL has _generic_ containers.

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> > I meant that the current C++ as a language is not optimal in this
respect.
>
> I'm not sure I understand. You say that the fact that _generic_
container
> must not use the techniqe good for only some _specific_ types of
contained
> objects makes C++ not optimal. How come?

    Depends on what you mean by "generic". In fact, container storing
"moveable" types is as generic as container storing "copy-constructible
and assignable" types. It has just different requirements for types
stored.

    And in fact, it can store much wider range of types (including e.g.
auto_ptr), so theoretically, in this respect, it is much more
generic....

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <9bed99bb.0305050519.6c501f59@posting.google.com>,
 on Mon, 5 May 2003 15:24:44 +0000 (UTC),
 witoldk@optonline.net (witoldk) wrote:

> qrczak@knm.org.pl ("Marcin 'Qrczak' Kowalczyk") wrote in message
> news:<1315773.3X0zHOGsjL@qrnik.knm.org.pl>...
[...]
> > C++ implementations can painfully and partially improve the situation even
> > in current C++. Namely they can provide specializations of containers for
> > standard types which implement resizing better, with the knowledge of the
> > representation of the element types or just the knowledge that memcpy works
> > for them.
>
> Please. Want specialized container? I'm afraid _you_ have to write it.
> STL has _generic_ containers.

Please. STL specifies generic containers, and Marcin is clearly
talking about explicit template specializations (14.7.3) of those
generic containers, and not "specialized containers". Any STL
implementation is free to provide specializations of std containers
for built-in types (and quite a lot of other types too). In fact, I
know of at least one implementation that _does_ provide
specializations of std::vector for built-in types for precisely the
reasons that are under discussion here.

Regards,
 Andy
--
"Light thinks it travels faster than anything but it is wrong. No matter
 how fast light travels it finds the darkness has always got there first,
 and is waiting for it."                  -- Terry Pratchett, Reaper Man

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

andys@despammed.com (Andy Sawyer) wrote in message news:<fzntwesl.fsf@ender.evo6.com>...
> In article <9bed99bb.0305050519.6c501f59@posting.google.com>,
>  on Mon, 5 May 2003 15:24:44 +0000 (UTC),
>  witoldk@optonline.net (witoldk) wrote:
>
> > qrczak@knm.org.pl ("Marcin 'Qrczak' Kowalczyk") wrote in message
> > news:<1315773.3X0zHOGsjL@qrnik.knm.org.pl>...
>  [...]
> > > C++ implementations can painfully and partially improve the situation even
> > > in current C++. Namely they can provide specializations of containers for
> > > standard types which implement resizing better, with the knowledge of the
> > > representation of the element types or just the knowledge that memcpy works
> > > for them.
> >
> > Please. Want specialized container? I'm afraid _you_ have to write it.
> > STL has _generic_ containers.
>
> Please. STL specifies generic containers, and Marcin is clearly
> talking about explicit template specializations (14.7.3) of those
> generic containers, and not "specialized containers". Any STL
> implementation is free to provide specializations of std containers
> for built-in types (and quite a lot of other types too). In fact, I
> know of at least one implementation that _does_ provide
> specializations of std::vector for built-in types for precisely the
> reasons that are under discussion here.

I thought we were _supposed_ to be discussing memory efficiency of vector
and list :) What I think I _was_ discussing with Marcin was how
"the current C++ as a language is not optimal in this respect". And "this
respect" I understood was the fact that memcpy could be more efficient
for the vector to use when resizing storage, _if_ it only could be used.
As the std::vector must not use memcpy for UDTs the only way for an
improvement would be to write the specialized container, that knows it's
elements could be copied around by memcpy. The fact that implementations
could (and as you point out likely do) specialize std::vector for built-ins
does not add much to our discussion, I'm afraid. The reason I think that, is
Marcin saying:
"Unfortunately the implementation can't do this for user defined types.
The programmer can't do this either because it depends on internals of
containers". So I take it as a need for a specialized container, and not
std::vector specialized for a built-in. Hence my advice.

I'm not sure what do you understand was "under discussion here".

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Andr    P   nitz" <poenitz@gmx.net> p   e v diskusn   m p      sp   vku
news:b8tggu$4uu$1@narses.hrz.tu-chemnitz.de...
> John G Harris <john@nospam.demon.co.uk> wrote:
> > No-one has ever claimed that the STL contains every utility class.
You
> > sometimes you have to define your own classes.
>
> However, STL implementation could benefit from the availability of a
> std::move(T &, T&) with a default of  std::move() == operator=()
greatly.

    Yes this is one possibility. On the other hand, if you replace
"copy-constructible and assignable" requirement by "moveable", you can
in fact store much wider range of types into vector, including mythical

    vector< auto_ptr<T> >

    because auto_ptr is incidentally moveable... (I mean all current
implementations)

    You might lost ability to store some types, but so far (after 3
years of using "moveable requirement") I have not encountred any. That
means any type I could store in STL vector and not in my Vector with
moveable requirement.

    Of course, decision about requirements was done, C++ standard is
written, case is lost :)

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <b8tnpa$mn2$1@news.vol.cz>, Mirek Fidler <cxl@volny.cz>
wrote:

| On the other hand, if you replace
| "copy-constructible and assignable" requirement by "moveable", you can
| in fact store much wider range of types into vector, including mythical
|
|     vector< auto_ptr<T> >
|
|     because auto_ptr is incidentally moveable... (I mean all current
| implementations)
|
|     You might lost ability to store some types, but so far (after 3
| years of using "moveable requirement") I have not encountred any. That
| means any type I could store in STL vector and not in my Vector with
| moveable requirement.
|
|     Of course, decision about requirements was done, C++ standard is
| written, case is lost :)

The case is not lost ... yet. ;-)

It depends on how you define movable.  I prefer to define movable as
something with the semantics of auto_ptr "copy", but not with the
syntax of copy.  Indeed it is my humble opinion that moving with copy
syntax is a design flaw.

C++ will evolve with time.  Work has already begun on C++0X.  If we
define move appropriately, STL containers can augment their
requirements (with no backwards compatibility hit):

    copy-constructible and assignable
 or
    moveable (move constructible and move assignable)

Alas, this still will not safely allow vector<auto_ptr<T> >.  But the
/only/ reason it is not safe is because auto_ptr moves with copy
syntax.

We could have vector<move_ptr<T> > where move_ptr is much like
auto_ptr, but moves with syntax other than copy, at least from lvalues.
Then vector<move_ptr<T> > _would_ _be_ _completely_ _safe_, even for
generic code that did not know it was dealing with vector<move_ptr<T>
>.

vector (and other STL containers) can easily adapt at compile time to
deal with either copyable or movable elements.  Efficiency gains for
some types will be astounding.

--
Howard Hinnant
Metrowerks

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

witoldk wrote:

> I take your statement to mean: memcpy is the wrong solution, because
> there is no way to prove it would work. Discussing whether the wrong
> solution could/would/might/is optimal is quite pointless.

I meant that the current C++ as a language is not optimal in this respect.
If illegal C++ can be much faster than legal C++, perhaps the problem is in
the laws. And I've seen one way to improve them (the proposal about moving
constructors and moving assignment).

C++ implementations can painfully and partially improve the situation even
in current C++. Namely they can provide specializations of containers for
standard types which implement resizing better, with the knowledge of the
representation of the element types or just the knowledge that memcpy works
for them.

Unfortunately the implementation can't do this for user defined types.
The programmer can't do this either because it depends on internals of
containers.

>> as long as the objects don't contain backpointers,
[...]
>
> There might be other cases when it would not work either, no?

I don't know other realistic cases (i.e. not counting classes with a
side-effecting copying constructor written for the purpose of testing
whether the C++ implementation is correct).

--
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

qrczak@knm.org.pl ("Marcin 'Qrczak' Kowalczyk") wrote in message news:<1080854.ONcdY1Z8Ep@qrnik.knm.org.pl>...
> E. Mark Ping wrote:
>
> > Which do you want?  Earlier you criticized the STL for only being
> > useful for simple objects, but your comparison here is only valid for
> > simple objects.  That is, memcpy won't work on complex types anyway,
> > so why complain that STL is only optimal for simple types?
>
> The point is that the optimal solution even for most non-POD types is
> memcpy, only the implementation can't prove when it would work.

I take your statement to mean: memcpy is the wrong solution, because
there is no way to prove it would work. Discussing whether the wrong
solution could/would/might/is optimal is quite pointless.

> Invoking
> memcpy manually for non-POD types is formally incorrect but works in
> practice as long as the objects don't contain backpointers, i.e. really
> most of the time.

There might be other cases when it would not work either, no?

>
> C++ doesn't provide the programmer a way to say "my type is safe to move
> using memcpy, go ahead and use it!". Even if it would, in non-POD cases the
> programmer would not be allowed to say that even when it's really true.
> It's too hard to infer that property automatically - backpointers can be
> hidden in an apparently unrelated part of code.
>
> So usually there is a fast potential implementation but neither the
> programmer alone is allowed to choose it nor the implementation alone is
> smart enough to choose it. Hardly "as efficient as possible".

Quite the opposite. Given that the "fast potential implementation" could
not be proven to work, the existing implementation is likely as efficient
as possible.
You would not reasonably expect the implementation to be as efficient
as...impossible, would you?

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> >     std::vector<std::map<std::string, std::vector<std::string> > >
>
> The above shows little more than the bad container choice.

    I wonder what container you plan to use instead of std::map....

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <b8il5i$1nr5$1@news.vol.cz>, Mirek Fidler <cxl@volny.cz>
writes
  <snip>
>> What makes it unoptimal, and  what you estimate as the impact on the
>performance?
>>
>
>    Freedom and need to make deep copies, caused by wrong interfaces.
  <snip>

At least the standard says very clearly what the assumptions and
requirements are, which is more than could be said for most pre-STL
libraries.

No-one has ever claimed that the STL contains every utility class. You
sometimes you have to define your own classes.

  John
--
John Harris
  mailto:john@jgharris.demon.co.uk

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> I'm having a hard time understanding your point. Containers in STL
> being generic could hardly be expected to work "at full speed".
> I'm afraid the full speed code has to be written by hand. In all
> likelyhood, after you are done writing and debugging (as one poster
> suggested already :) your code implementing something equivalent to
> your std::vector<std::map<std::string, std::vector<std::string> >

    Well, for the begining you could try something like

    std::vector<std::map<std::string, std::vector<std::string> *> *>

    There are better solution, but this might show the point.

> So, what is your point?

    Again: Original poster asked about vector efficiency. All I said was
that you cannot use vector to store any type that satisfies its
requirements effectively. My intention was to warn him that there are
some limits. OK ?

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Mirek Fidler"" <cxl@volny.cz> wrote in message
news:b8p55s$1sus$1@news.vol.cz...
> > >     std::vector<std::map<std::string, std::vector<std::string> > >
> >
> > The above shows little more than the bad container choice.
>
>     I wonder what container you plan to use instead of std::map....

Maybe:

std::deque<std::multimap<std::string,std::string> >

Ken


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> > Invoking
> > memcpy manually for non-POD types is formally incorrect but works in
> > practice as long as the objects don't contain backpointers, i.e.
really
> > most of the time.
>
> There might be other cases when it would not work either, no?

    Well, you can sum it up this way:

    You can use memcpy

    - if you can use memcpy for base class (if any) and any member
variable

    and

     - there is no method in class that stores pointer to base class or
any member variable to variable that survives the scope of method.

    I bet most classes you ever wanted to store into std::vector
satisfied this requirement.

> > So usually there is a fast potential implementation but neither the
> > programmer alone is allowed to choose it nor the implementation
alone is
> > smart enough to choose it. Hardly "as efficient as possible".
>
> Quite the opposite. Given that the "fast potential implementation"
could
> not be proven to work, the existing implementation is likely as
efficient

    It can be proved to work. It works. We have tens of megabytes of
code relying on it. Anyway, this has nothing to do with original post...

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

Mirek Fidler wrote:

>     Another nice example is
>
>     std::map<std::string, std::vector<T> >
>
>     which is effectivelly disallowed to work optimal by map interface
> and definition.

Could you provide more detail on this ?

Davide Bolcioni
--
Paranoia is an afterthought.

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

cxl@volny.cz ("Mirek Fidler") wrote in message news:<b8p4rc$1sov$1@news.vol.cz>...

> > So, what is your point?
>
>     Again: Original poster asked about vector efficiency. All I said was

It seems that OP was mostly concerned about _per_ _element_ memory
overhead for elements stored in vector (list). By efficiency he meant
efficient memory management.

> My intention was to warn him that there are some limits. OK ?

OK, but there are some limits to everything, so what is the point?

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

cxl@volny.cz ("Mirek Fidler") wrote in message news:<b8p6so$1v34$1@news.vol.cz>...

> > > smart enough to choose it. Hardly "as efficient as possible".
> >
> > Quite the opposite. Given that the "fast potential implementation"
>  could
> > not be proven to work, the existing implementation is likely as
> efficient
>
>     It can be proved to work. It works.

Mamcpy works? Yes, absolutely.
It is just that given the requirements, std::vector must not use 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> > > not be proven to work, the existing implementation is likely as
> > efficient
> >
> >     It can be proved to work. It works.
>
> Mamcpy works? Yes, absolutely.
> It is just that given the requirements, std::vector must not use it.

    Right. That is the reason for not using std::vector :)

    Appart from this discussion thread, I think that stl requirements
are wrong.

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> > My intention was to warn him that there are some limits. OK ?
>
> OK, but there are some limits to everything, so what is the point?

    Point is that limits should be known. Kind of question original
poster asked made me think that he might not be aware about this
problem. Most of respones my comment invoked hardened me in opinion that
this concrete issue might not be well known. OK ? :)

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

John G Harris <john@nospam.demon.co.uk> wrote:
> No-one has ever claimed that the STL contains every utility class. You
> sometimes you have to define your own classes.

However, STL implementation could benefit from the availability of a
std::move(T &, T&) with a default of  std::move() == operator=() greatly.

In many cases this alone would solve "performance problems" without any
need to fully implement a new specialized container class.

Don't get me wrong: I am fairly happy with the STL. But I see no reason why
"obvious" improvements should not incoporated in due time, especially if
they are completely transparent to "user code".

Andre'

--
Those who desire to give up Freedom in order to gain Security, will not have,
nor do they deserve, either one.     (T. Jefferson or B. Franklin or both...)

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

cxl@volny.cz ("Mirek Fidler") wrote in message news:<b8rsm8$2f94$1@news.vol.cz>...

>     Point is that limits should be known. Kind of question original
> poster asked made me think that he might not be aware about this
> problem.

The "problem" you seem to see with the vector is that it _could_
be implemented faster for _some_ types of contained data. As such,
your comments are off base, since std:vector (and the rest of STL)
is _meant_ to be generic.
Furthermore, you are not really helping the OP, because your comments
seem to be aimed at discouraging the use of std::vector. Think about
how likely are the people not aware of the "problems" you are pointing
out to do any better than std::vector when trying to implement it's
functionality by writing the code themselves. I think unlikely, and
that is the very reason why they _should_ use std::vector,
despite your claims that in _some_ cases _you_ could do better than
std::vector.

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

witoldk wrote:
> cxl@volny.cz ("Mirek Fidler") wrote in message news:<b8k79j$2puq$1@news.vol.cz>...
>
>
>>>you can easily use something like boost's shared pointer (along with
>>>their dereferencing iterator for some cleanliness) and very easily
>>>store reference types in STL containers, at full speed.
>>
>>    By using boost's shared pointer you simply admit that there are
>>types that cannot be stored in STL effectively. And even using shared
>>pointer is suboptimal - it is hardly "at full speed".
>
>
> I'm having a hard time understanding your point. Containers in STL
> being generic could hardly be expected to work "at full speed".

Why ?  This statement is unsubstantiated.

I suggest that STL provides a model that is NOT generic and far too
limiting.  A richer set of containers are needed.

I think STL is a good start, don't get me wrong, it's just - not good
enough and you should expect "full speed".

One of the underlying principles of good design in C++ is not to pay for
what you don't need.  Well, the current set of STL containers work great
  for a small set of real world problems.  Programmers (I for one) are
forever working around limitations of STL and inevitably creating less
efficient more complex code than is needed.

To that extent, in my most recent task, I've implemented a more generic
std::list look-alike that allows an object to be contained within
multiple lists as well as making the contained object aware of it's
iterator so it may manage which lists it is a member of.

The self-awareness of membership of lists or maps is essential to good
object oriented design.  To achieve this with std::list and std::map you
have perform unholy acts and creating other distinct objects that manage
the object that should be managing itself hence introducing significant
levels of inefficiency and complexity.

For a final rebuke - YES, I expect the "standard" containers to allow me
to create code that runs at full speed and as they stand today; as they
stand today they fail in this expectation.

> I'm afraid the full speed code has to be written by hand.

What do you think the STL is ?  Written by a foot ?

One way of looking at C++ templates is that they allow the user to write
compiler extensions of their own.

You can write containers that allow any level of complexity you need.
The trick is to design them correctly.  The stl is a excellent attempt
but it misses in some significant ways.



---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> >     Keep also in mind that using STL for storing anything else than
> > fundamental data types results in unoptimal performance.
>
> Would you explain that?    STL is too big a term, let's limit to
vector as it is in STL. What kind of implemetation you'd think optimal,
to be used for A) small PODs , b) big PODs, C) non-PODs.

>
> What makes it unoptimal, and  what you estimate as the impact on the
performance?
>

    Freedom and need to make deep copies, caused by wrong interfaces.

    OK, I must admit you can use STL to store very samll PODs
effectively too...

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Mirek Fidler"" <cxl@volny.cz> skrev i meddelandet
news:b8jj6j$2dsu$1@news.vol.cz...
> >>     Then it obviously failed. Try to create
> >>
> >>     std::vector<std::map<std::string, std::vector<std::string> > >
>
> > Yes, what is the problem?
>
> Problem is that while above construction will work, it will work rather
> slow...
>
> You will be able to improve things a bit by not using 'push_back' for
> adding elements (or use it for adding empty containers instead), but in
> any case, when outer vector will have to expand, it will have to copy
> all inner maps and inner maps will have to copy inner vectors...

Ok, so if growing is a problem, try using std::list or std::deque instead.
:-)

>
> Mirek
>
>


Bo Persson
bop2@telia.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://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Mirek Fidler"" <cxl@volny.cz> wrote in message
news:b8jj6j$2dsu$1@news.vol.cz...
> >>     Then it obviously failed. Try to create
> >>
> >>     std::vector<std::map<std::string, std::vector<std::string> > >
>
> > Yes, what is the problem?
>
> Problem is that while above construction will work, it will work rather
> slow...
>
> You will be able to improve things a bit by not using 'push_back' for
> adding elements (or use it for adding empty containers instead), but in
> any case, when outer vector will have to expand, it will have to copy
> all inner maps and inner maps will have to copy inner vectors...
>

    Does the standard really say this?  Could a conforming implementation
implement vector reallocation as follows?

     1)  Create a new vector with capacity() == 2 * current-vector's
capacity(), size() == current-vector's size(), and every element
default-constructed.
     2) swap() every element of the original vector with the corresponding
element of the new vector. (Many classes, including all the STL containers,
have constant-time swap())
    3) swap() the original vector with the new vector.

Joe Gottman

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> >>>     Then it obviously failed. Try to create
> >>>
> >>>     std::vector<std::map<std::string, std::vector<std::string> > >
> >
> >> Yes, what is the problem?
> >
> >Problem is that while above construction will work, it will work
rather
> >slow...
> >
> >You will be able to improve things a bit by not using 'push_back' for
> >adding elements (or use it for adding empty containers instead), but
in
> >any case, when outer vector will have to expand, it will have to copy
> >all inner maps and inner maps will have to copy inner vectors...
>
> This is a specious argument.  You're complaining about parameters for
> which std::vector was not designed.  If you use quicksort on nearly

    Hey ! All I said is that STL is optimal only for simple types. Well,
you can extend it beyond fundamental types and add simple PODs. I even
was not complaining !

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

E. Mark Ping wrote:

> Which do you want?  Earlier you criticized the STL for only being
> useful for simple objects, but your comparison here is only valid for
> simple objects.  That is, memcpy won't work on complex types anyway,
> so why complain that STL is only optimal for simple types?

The point is that the optimal solution even for most non-POD types is
memcpy, only the implementation can't prove when it would work. Invoking
memcpy manually for non-POD types is formally incorrect but works in
practice as long as the objects don't contain backpointers, i.e. really
most of the time.

C++ doesn't provide the programmer a way to say "my type is safe to move
using memcpy, go ahead and use it!". Even if it would, in non-POD cases the
programmer would not be allowed to say that even when it's really true.
It's too hard to infer that property automatically - backpointers can be
hidden in an apparently unrelated part of code.

So usually there is a fast potential implementation but neither the
programmer alone is allowed to choose it nor the implementation alone is
smart enough to choose it. Hardly "as efficient as possible".

The only part which could realistically be improved is to provide the
programmer a way to say "here is how objects of my type are moved".
In this case inferring by an implementation that memcpy works is at least
imaginable, and even if implementations aren't that smart, type-specific
moving is much better than copy & destruct.

These are the consequences of value-passing semantics.

--
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> > >>     std::vector<std::map<std::string, std::vector<std::string> >
>
> >
> > > Yes, what is the problem?
> >
> > Problem is that while above construction will work, it will work
rather
> > slow...
> >
> > You will be able to improve things a bit by not using 'push_back'
for
> > adding elements (or use it for adding empty containers instead), but
in
> > any case, when outer vector will have to expand, it will have to
copy
> > all inner maps and inner maps will have to copy inner vectors...
>
> Ok, so if growing is a problem, try using std::list or std::deque
instead.
> :-)

    I am afraid they are little bit slow as associative containers...

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

cxl@volny.cz ("Mirek Fidler") wrote in message news:<b8il1e$1nqn$1@news.vol.cz>...
> ""Joe Gottman"" <jgottman@carolina.rr.com> p   e v diskusn   m p      sp   vku
> news:IiZqa.20705$pr.4708899@twister.southeast.rr.com...
> >
> > ""Mirek Fidler"" <cxl@volny.cz> wrote in message
> > news:b8fvg7$1ur8$1@news.vol.cz...
> > >     Keep also in mind that using STL for storing anything else than
> > > fundamental data types results in unoptimal performance.
> >
> >    How so?  I thought the fundamental purpose of the STL was to create
> > generic containers that are as efficient as possible. Every reference
> I have
>
>     Then it obviously failed. Try to create
>
>     std::vector<std::map<std::string, std::vector<std::string> > >

The above shows little more than the bad container choice.

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

>      1)  Create a new vector with capacity() == 2 * current-vector's
> capacity(), size() == current-vector's size(), and every element
> default-constructed.

    Well, here is the glitch (perhaps one of). STL does not require
elements to be default-constructible.

    Anyway, good try :)

    But again: Original poster asked about std::vector efficiency. I
thought that suboptimal performance for many types of elements should
have been mentioned....

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

cxl@volny.cz ("Mirek Fidler") wrote in message news:<b8k79j$2puq$1@news.vol.cz>...

> > you can easily use something like boost's shared pointer (along with
> > their dereferencing iterator for some cleanliness) and very easily
> > store reference types in STL containers, at full speed.
>
>     By using boost's shared pointer you simply admit that there are
> types that cannot be stored in STL effectively. And even using shared
> pointer is suboptimal - it is hardly "at full speed".

I'm having a hard time understanding your point. Containers in STL
being generic could hardly be expected to work "at full speed".
I'm afraid the full speed code has to be written by hand. In all
likelyhood, after you are done writing and debugging (as one poster
suggested already :) your code implementing something equivalent to
your std::vector<std::map<std::string, std::vector<std::string> >
the money spent could be put to better use. Maybe have you do
something usefull, and spend the savings on hardware?
BTW: why would you put maps in vector when at the same time copying
was a problem? To pass all these maps to C API?
The point of _using_ STL (one of many points) is that software
developement is inherently error prone and time consumming. I think
I remember a thread here or on c.l.c++.m about fast implementation
of hash map. If memory serves me, the map was in fact fast, but only
when the data matched the hashing function's "requirements". And that
was shown not to be too common :) It only shows how hard it is to
write the "full speed" code to begin with.
So, what is your point?

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <b8l70b$128s$1@news.vol.cz>, cxl@volny.cz ("Mirek Fidler")
wrote:

> > > >>     std::vector<std::map<std::string, std::vector<std::string> >
> > >
> > Ok, so if growing is a problem, try using std::list or std::deque
> instead.
>
>     I am afraid they are little bit slow as associative containers...
>
> Mirek

Not noticeably slower than vector.

(Oops, I think I snipped a :-) somewhere.)

Best wishes,
Matthew Collett

--
Those who assert that the mathematical sciences have nothing to say
about the good or the beautiful are mistaken.          -- Aristotle

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

It all depends on the STL implementation. Most current ones don't have
much overhead at all. Even for a straightforward implementation of
vector, the overall cost should only be T*N + F, where T is the size
of the object you're storing in the vector, N is the number of objects
in the buffer (often rounded to the nearest power of 2), and F is the
size of the vector object iself, which is about 12-16 bytes depending
on the STL implementation.

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> Hi:
>   I am very puzzled whether vector/list in STL is efficient enough for
> storing
> large size data. If we use array as a reference, say one integer
> element to be stored uses c in an array, then t*c for this element
> will be used in a vector/list. I don't know how large this constant t
> will be.
>   I feel t will be relatively large because each element corresponds
> to a class instance in vector/list, which will result large storage
> space. This is
> a reason why I am hesitating to use vector/list when I have large size
> data to store, even though vector/list is very convenient for dynamic
> array management.
>   Can anybody give some comment? Thanks.

    If you do not use reserve for vector capacity management and simply
use push_back to add elements, expect average 50% memory overhead for
vector (because capacity doubles each time vector has to expand). For
list, overhead depends on sizeof element stored, STL implementation,
allocator used etc.... For primitive implementation I would expect
16bytes overhead per element (8 bytes for list links, 8 bytes heap
managment).

    Keep also in mind that using STL for storing anything else than
fundamental data types results in unoptimal performance.

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Mirek Fidler"" <cxl@volny.cz> wrote in message
news:b8fvg7$1ur8$1@news.vol.cz...
>     Keep also in mind that using STL for storing anything else than
> fundamental data types results in unoptimal performance.

   How so?  I thought the fundamental purpose of the STL was to create
generic containers that are as efficient as possible. Every reference I have
read suggests that a good STL implementation is as good as hand-crafted
code, unless the hand-crafted code uses specific knowledge of the data type
being held to improve efficiency.

Joe Gottman

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Mirek Fidler"" <cxl@volny.cz> wrote in message news:b8fvg7$1ur8$1@news.vol.cz...

>     Keep also in mind that using STL for storing anything else than
> fundamental data types results in unoptimal performance.

Would you explain that?    STL is too big a term, let's limit to vector as it is in STL. What kind of implemetation you'd think optimal, to be used for A) small PODs , b) big PODs, C) non-PODs.

What makes it unoptimal, and  what you estimate as the impact on the performance?

Paul

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Joe Gottman"" <jgottman@carolina.rr.com> p   e v diskusn   m p      sp   vku
news:IiZqa.20705$pr.4708899@twister.southeast.rr.com...
>
> ""Mirek Fidler"" <cxl@volny.cz> wrote in message
> news:b8fvg7$1ur8$1@news.vol.cz...
> >     Keep also in mind that using STL for storing anything else than
> > fundamental data types results in unoptimal performance.
>
>    How so?  I thought the fundamental purpose of the STL was to create
> generic containers that are as efficient as possible. Every reference
I have

    Then it obviously failed. Try to create

    std::vector<std::map<std::string, std::vector<std::string> > >

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Mirek Fidler"" <cxl@volny.cz> wrote in message news:b8il1e$1nqn$1@news.vol.cz...

> ""Joe Gottman"" <jgottman@carolina.rr.com> p   e v diskusn   m p      sp   vku
> news:IiZqa.20705$pr.4708899@twister.southeast.rr.com...
> >
> > ""Mirek Fidler"" <cxl@volny.cz> wrote in message
> > news:b8fvg7$1ur8$1@news.vol.cz...
> > >     Keep also in mind that using STL for storing anything else than
> > > fundamental data types results in unoptimal performance.
> >
> >    How so?  I thought the fundamental purpose of the STL was to create
> > generic containers that are as efficient as possible. Every reference
> I have
>
>     Then it obviously failed. Try to create
>
>     std::vector<std::map<std::string, std::vector<std::string> > >

Try to write it from scratch -- without using template classes map, string,
and vector -- and see how long it takes to get it debugged.

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Mirek Fidler"" <cxl@volny.cz> skrev i meddelandet
news:b8il1e$1nqn$1@news.vol.cz...
>
> ""Joe Gottman"" <jgottman@carolina.rr.com> p=ED=B9e v diskusn=EDm p=F8=ED=
sp=ECvku
> news:IiZqa.20705$pr.4708899@twister.southeast.rr.com...
> >
> > ""Mirek Fidler"" <cxl@volny.cz> wrote in message
> > news:b8fvg7$1ur8$1@news.vol.cz...
> > >     Keep also in mind that using STL for storing anything else than
> > > fundamental data types results in unoptimal performance.
> >
> >    How so?  I thought the fundamental purpose of the STL was to creat=
e
> > generic containers that are as efficient as possible. Every reference
> I have
>
>     Then it obviously failed. Try to create
>
>     std::vector<std::map<std::string, std::vector<std::string> > >

Yes, what is the problem?

>
> Mirek
>
>

Bo Persson
bop2@telia.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://www.jamesd.demon.co.uk/csc/faq.html                       ]

>>     Then it obviously failed. Try to create
>>
>>     std::vector<std::map<std::string, std::vector<std::string> > >

> Yes, what is the problem?

Problem is that while above construction will work, it will work rather
slow...

You will be able to improve things a bit by not using 'push_back' for
adding elements (or use it for adding empty containers instead), but in
any case, when outer vector will have to expand, it will have to copy
all inner maps and inner maps will have to copy inner vectors...

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

Bo Persson wrote:

>>     Then it obviously failed. Try to create
>>
>>     std::vector<std::map<std::string, std::vector<std::string> > >
>
> Yes, what is the problem?

That adding an element to the outer vector when the allocated space
overflows deeply rebuilds the entire structure of the maps, inner vectors
and strings, then destroying the originals - where in fact data is just
moved to another address and it could be theoretically archieved just by
moving sizeof(std::map<...>)*N bytes.

--
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <b8jj6j$2dsu$1@news.vol.cz>, Mirek Fidler <cxl@volny.cz>
wrote:

| >>     Then it obviously failed. Try to create
| >>
| >>     std::vector<std::map<std::string, std::vector<std::string> > >
|
| > Yes, what is the problem?
|
| Problem is that while above construction will work, it will work rather
| slow...
|
| You will be able to improve things a bit by not using 'push_back' for
| adding elements (or use it for adding empty containers instead), but in
| any case, when outer vector will have to expand, it will have to copy
| all inner maps and inner maps will have to copy inner vectors...

This is a problem that I hope will be addressed in the future.  A
solution is here:

http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm

--
Howard Hinnant
Metrowerks

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> | >>     Then it obviously failed. Try to create
> | >>
> | >>     std::vector<std::map<std::string, std::vector<std::string> >
>
> |
> | > Yes, what is the problem?
> |
> | Problem is that while above construction will work, it will work
rather
> | slow...
> |
> | You will be able to improve things a bit by not using 'push_back'
for
> | adding elements (or use it for adding empty containers instead), but
in
> | any case, when outer vector will have to expand, it will have to
copy
> | all inner maps and inner maps will have to copy inner vectors...
>
> This is a problem that I hope will be addressed in the future.  A
> solution is here:
>
> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm
>

    Yes I know. But while I like that proposal and while it would help
here, it is still not optimal solution - even move contructor in loop is
worse than simple memcpy working on huge memory block.

    Anyway, now and here (and for another four years at least) we are
speaking about current STL. And it is suboptimal for anything else than
simpliest data types.

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

>     Keep also in mind that using STL for storing anything else than
> fundamental data types results in unoptimal performance.
That's largely a myth these days. Used to be true in 1998, not
anymore. Today's highly optimizing compilers (I use GCC 3.2.2 and
Intel C++ 7.1) treat classes pretty much identically to fundemental
types. Just do simple experiments with vector or string and you'll
find out that they have pretty much zero performance hit for
user-defined types. Now one thing you do have to be aware of is that
the STL is value oriented. If you store large user-defined types,
there might be excess copying occuring. In my tests, for objects up to
128 or so bytes, the copy overhead (and the memory allocation overhead
at insert) is minimal enough that STL list performs about 70% as fast
as a straightforward, reference oriented, non-allocating (you allocate
before hand) data structure. For almost all cases, that 30% is not
worth worrying about. And if your objects are larger than 128 bytes,
you can easily use something like boost's shared pointer (along with
their dereferencing iterator for some cleanliness) and very easily
store reference types in STL containers, at full speed.

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

> types. Just do simple experiments with vector or string and you'll
> find out that they have pretty much zero performance hit for
> user-defined types. Now one thing you do have to be aware of is that

    I did. Simple std::vector<std::string>, with copy-on write reference
counted single threaded string implementation, performance difference is
about 100%. See


http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm#vector%
20Example

    for (perhaps) other string implementation.

    Another nice example is

    std::map<std::string, std::vector<T> >

    which is effectivelly disallowed to work optimal by map interface
and definition.

> worth worrying about. And if your objects are larger than 128 bytes,
> you can easily use something like boost's shared pointer (along with
> their dereferencing iterator for some cleanliness) and very easily
> store reference types in STL containers, at full speed.

    By using boost's shared pointer you simply admit that there are
types that cannot be stored in STL effectively. And even using shared
pointer is suboptimal - it is hardly "at full speed".

Mirek


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <b8jj6j$2dsu$1@news.vol.cz>, Mirek Fidler <cxl@volny.cz> wrote:
>>>     Then it obviously failed. Try to create
>>>
>>>     std::vector<std::map<std::string, std::vector<std::string> > >
>
>> Yes, what is the problem?
>
>Problem is that while above construction will work, it will work rather
>slow...
>
>You will be able to improve things a bit by not using 'push_back' for
>adding elements (or use it for adding empty containers instead), but in
>any case, when outer vector will have to expand, it will have to copy
>all inner maps and inner maps will have to copy inner vectors...

This is a specious argument.  You're complaining about parameters for
which std::vector was not designed.  If you use quicksort on nearly
sorted data you'll have problems too.  So?  You use the right tools
for the right job.  Please tell us how a container with the design
constraints of std::vector could behave better.

If the dominating factor in that structure are the maps, why isn't it
a std::list<std::map<std::string, std::vector<std::string> > > ?
--
Mark Ping
emarkp@soda.CSUA.Berkeley.EDU

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <b8jn1g$2h8r$1@news.vol.cz>, Mirek Fidler <cxl@volny.cz> wrote:
>Yes I know. But while I like that proposal and while it would help
>here, it is still not optimal solution - even move contructor in loop
>is worse than simple memcpy working on huge memory block.

Which do you want?  Earlier you criticized the STL for only being
useful for simple objects, but your comparison here is only valid for
simple objects.  That is, memcpy won't work on complex types anyway,
so why complain that STL is only optimal for simple types?

Don't get me wrong, I don't see the STL as perfect (though I do see
it as pretty good), but I don't see your argument as either consistent
or persuasive.
--
Mark Ping
emarkp@soda.CSUA.Berkeley.EDU

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hi:
  I am very puzzled whether vector/list in STL is efficient enough for
storing
large size data. If we use array as a reference, say one integer
element to be stored uses c in an array, then t*c for this element
will be used in a vector/list. I don't know how large this constant t
will be.
  I feel t will be relatively large because each element corresponds
to a class instance in vector/list, which will result large storage
space. This is
a reason why I am hesitating to use vector/list when I have large size
data to store, even though vector/list is very convenient for dynamic
array management.
  Can anybody give some comment? Thanks.

Best Regards

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <37135f62.0304241834.106496f5@posting.google.com>, lian wrote:
> Hi:
>   I am very puzzled whether vector/list in STL is efficient enough for
> storing
> large size data. If we use array as a reference, say one integer
> element to be stored uses c in an array, then t*c for this element
> will be used in a vector/list. I don't know how large this constant t
> will be.
>   I feel t will be relatively large because each element corresponds
> to a class instance in vector/list, which will result large storage
> space.
<snip>

A vector implementation need not allocate any additional per-element
storage.  The elements are intended to be stored in an array, although
the current standard does not explicitly say so.  The storage required
for a vector<T> of capacity n will normally be k + n * sizeof(T) where
k is some small constant.

Note, however, that the capacity (number of elements that the vector
has space for) is not the same thing as the size (number of elements
currently stored).  If the capacity of a vector is increased
automatically because the size would otherwise exceed it, then it
grows in exponential steps - typically doubling each time - so the
capacity can be nearly double the size.  If you know how much space
you need then you may be able to avoid this by using the reserve()
call in advance, though there's no guarantee that that doesn't round
up the capacity you specify.  Secondly, the capacity of a vector
generally does not shrink as the size does, and I think this is a
requirement of the standard.

For lists, you are right that additional storage is required (at
least two pointers per element) but I'd be interested to hear of a
list design that doesn't require 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

lian wrote:
> Hi:
>   I am very puzzled whether vector/list in STL is efficient enough for
> storing
> large size data. If we use array as a reference, say one integer
> element to be stored uses c in an array, then t*c for this element
> will be used in a vector/list. I don't know how large this constant t
> will be.

If I understand you correctly, t==1, so you can stop worrying
and start writing std::vector<> everywhere.

Comparing...

   MyType array[ /*Some constant, N*/ ];
   std::vector<MyType> vec;

Then the *total* storage required for the vector, for *any* value of
N will include a dozen bytes or so for the vector's own overhead and
that of the heap management, but the vector has the advantage that it
needn't allocate the N items until they are actually used.

>   I feel t will be relatively large because each element corresponds
> to a class instance in vector/list, which will result large storage
> space.

Arrays and vectors store exactly the same data for each element.


---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"lian" <jiangziya74@yahoo.com> skrev i en meddelelse
news:37135f62.0304241834.106496f5@posting.google.com...
> Hi:
>   I am very puzzled whether vector/list in STL is efficient enough for
> storing
> large size data. If we use array as a reference, say one integer
> element to be stored uses c in an array, then t*c for this element
> will be used in a vector/list. I don't know how large this constant t
> will be.
>   I feel t will be relatively large because each element corresponds
> to a class instance in vector/list, which will result large storage
> space. This is
> a reason why I am hesitating to use vector/list when I have large size
> data to store, even though vector/list is very convenient for dynamic
> array management.
>   Can anybody give some comment? Thanks.


Hi Lian


If you store n elements of size sz, the storage requirements are:

for vector: c1 + n*sz. Where c1 is the constant sizeof(std::vector< int >).
The vector may have some unused space, however which you can query with
capacity and request via reserve.
for list: c2 + n*(sz + c3). Where c2 is the constant sizeof(std::list< int
>) and c3 is some constant that will typically be 2*sizeof(void*).
One place where you will have to be careful with vectors is when growing
them - using e.g. push_back. If there is not room for a new element (size()
== capacity()), the vector will typically double in size. Thus the total
space for a vector with n elements could be  c1 + 2*n*sz. By using reserve()
you can avoid this, but it does require you to know how large a vector you
will need before you insert elements or be very careful with your
push_backs.
An alternative to using vector is std::deque, which will typically require
size c3 + n*(sz + c2), where c3 might be quite large (compared to vector)
but still constant and alpha is very small - probably less than one.

Kind regards
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://www.jamesd.demon.co.uk/csc/faq.html                       ]