From: Daniel Krügler on
On 10 Jul., 21:23, dhruv <dhruvb...(a)gmail.com> wrote:
> So, on a slightly tangential note, will ref-counted/COW/non-contiguous
> implementations _most_ likely be implemented as having a separate
> buffer for supporting the c_str() and data() functions? Does the
> standard mandate the complexity of these functions?
>
> For example say there is a string implementation that always breaks up
> the string into a maximum of 10 parts if it exceeds (say) 1MB. Such an
> implementation can guarantee O(1) lookup but not O(1) c_str() and
> data().

AFAIK none of the existing standard libraries did have
a non-contiguous implementation, at least this was my
understanding during the Sophia Antipolis meeting.
Nevertheless it was IMO a defect in the C++03 standard
that the complexity of a call of c_str() or data() wasn't
specified at all - the wording would have allowed even a
complexity of O(N^2). In C++0x both are required to be
of O(1).

HTH & Greetings from Bremen,

Daniel Kr�gler




--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]