Scott Meyers wrote:
>
> I have a suspicion that string::push_back is supposed to have amortized
> constant time complexity (just like vector::push_back, even though the
> standard says in 23.1.1 that vector::push_back offers constant time
> complexity, i.e., doesn't say that it's AMORTIZED constant time), but I
> wasn't sure, so I tried to find the answer in the standard.

I think that this is the problem, not basic_string<>. AFAIK all
containers use allocators and allocators are required only to have
amortized constant time behavior. Since any call to push_back can
trigger an allocator operation doesn't this imply that the overall
complexity of push_back is amortized constant time at best?


Regards, John.

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Tue,  5 Dec 2000 17:50:56 GMT, Scott Meyers <smeyers@aristeia.com>
wrote:

> Questions:
>   - Is there any complexity guarantee for string::push_back?

No.  The only complexity mentioned in the string class is constant
time for swap.

String is a schizophrenic class.  It has everything from <cstring>
in a form that looks more like basic.  It also has everything from
the STL with iterators.  Push_back was a late addition.  Should it
be s.insert(s.end(), c) or s.append(1, c)?  The latter is defined
in terms of constructing a string from c and appending it to s.

String was present before STL which brought complexity requirements.
It appears to allow flexibility without constraint.  There is no
requirement that s.find(s2) have a complexity better than s.length()
* s2.length(), for example.

It seems to me that string is a complete QoI issue for those who care
about complexity.

John

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

I have a suspicion that string::push_back is supposed to have amortized
constant time complexity (just like vector::push_back, even though the
standard says in 23.1.1 that vector::push_back offers constant time
complexity, i.e., doesn't say that it's AMORTIZED constant time), but I
wasn't sure, so I tried to find the answer in the standard.  Page 385 lists
string::push_back and suggests that its semantics will be given in 21.3.5,
but push_back isn't listed in 21.3.5.  In fact, I can't find any semantics
for string::push_back in the standard anywhere.  This sounds like a defect
to me, but I didn't see anything in the LWG list.

Questions:
  - Is there any complexity guarantee for string::push_back?
  - Does the standard give semantics for string::push_back somewhere?
  - If not, is this a defect?

Thanks,

Scott

--
I've scheduled more public seminars.  Check out
http://www.aristeia.com/seminars/ for details.

---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Scott Meyers" <smeyers@aristeia.com> wrote in message
news:MPG.1495ee5c840a300998975a@news.supernews.com...
> I have a suspicion that string::push_back is supposed to have amortized
> constant time complexity (just like vector::push_back, even though the
> standard says in 23.1.1 that vector::push_back offers constant time
> complexity, i.e., doesn't say that it's AMORTIZED constant time), but I
> wasn't sure, so I tried to find the answer in the standard.  Page 385
lists
> string::push_back and suggests that its semantics will be given in 21.3.5,
> but push_back isn't listed in 21.3.5.  In fact, I can't find any semantics
> for string::push_back in the standard anywhere.  This sounds like a defect
> to me, but I didn't see anything in the LWG list.
>
> Questions:
>   - Is there any complexity guarantee for string::push_back?
>   - Does the standard give semantics for string::push_back somewhere?
>   - If not, is this a defect?

21.3/2 says that basic_string conforms to the requirements of a Sequence as
specified in 23.1.1, which includes the table in 23.1.1/12 as you noted.

Given that I think it's safe to say you have a complexity guarentee (with
the amortized caveat above).

HTH

Ric


---
[ 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.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]