encryption problem

[James Kanze]

I'm not sure. I'm not sure that basic_string really is a
sequence; it just sort of looks like one. As late as CD2, for
example, it didn't support push_back. It's hard even to talk
about the intent of basic_string; so many people had their
fingers in it, and they all had different intents.

There is an explicit statement to the effect that the intent is
to allow (but not require) reference counted implementations.
In a reference counted implementation (like g++), neither
operator[] nor at() are constant time, since they may trigger a
complete copy.

Is that the reason some very old versions of g++ didn't support
at() for basic_strings?

I doubt it. If that were the case, they wouldn't support
operator[] either. A more likely reason is that they
implemented it before at() got added to the standard.

 

[Michael DOUBEZ]

James Kanze a écrit :

Is that the reason some very old versions of g++ didn't support
at() for basic_strings?

I doubt it. If that were the case, they wouldn't support
operator[] either. A more likely reason is that they
implemented it before at() got added to the standard.

IMO there is no relation with operator[]. If basic_string::size() is
O(n), I can still implement operator[] in O(1) but at() requires to know
the size (for bound check) and thus cannot be implemented in O(1).

Still I also think it is a pre-standard matter.

Michael

 

[Bo Persson]

Michael DOUBEZ wrote:
:: James Kanze a écrit :
:::: Michael DOUBEZ wrote:
:::::: Does the C++ standard state any speed requirements for the
:::::: at() method?
:::
::::: 23.1.1/12 specifies sequence container should implement it when
::::: it runs in constant time. IMO is applies to basic_string.
::
:::: Is that the reason some very old versions of g++ didn't support
:::: at() for basic_strings?
:::
::: I doubt it. If that were the case, they wouldn't support
::: operator[] either. A more likely reason is that they
::: implemented it before at() got added to the standard.
::
:: IMO there is no relation with operator[]. If basic_string::size()
:: is O(n), I can still implement operator[] in O(1) but at()
:: requires to know the size (for bound check) and thus cannot be
:: implemented in O(1).

But basic_string claims to be a Sequence container, which should have
a size() of "constant complexity" (23.1 Table 65).

I think James' problem is with a reference counted implementation,
where a non-const operator[] would have to un-share the internal
representation before returning a modifiable reference to the
character position. That would not be O(1), except sometimes.


Bo Persson

::
:: Still I also think it is a pre-standard matter.
::
:: Michael

 

[Michael DOUBEZ]

Bo Persson a écrit :

Michael DOUBEZ wrote:
:: James Kanze a écrit :
:::: Michael DOUBEZ wrote:
:::::: Does the C++ standard state any speed requirements for the
:::::: at() method?
:::
::::: 23.1.1/12 specifies sequence container should implement it when
::::: it runs in constant time. IMO is applies to basic_string.
::
:::: Is that the reason some very old versions of g++ didn't support
:::: at() for basic_strings?
:::
::: I doubt it. If that were the case, they wouldn't support
::: operator[] either. A more likely reason is that they
::: implemented it before at() got added to the standard.
::
:: IMO there is no relation with operator[]. If basic_string::size()
:: is O(n), I can still implement operator[] in O(1) but at()
:: requires to know the size (for bound check) and thus cannot be
:: implemented in O(1).

But basic_string claims to be a Sequence container, which should have
a size() of "constant complexity" (23.1 Table 65).

basic_sting claims no such thing; it is designated as an object
containing ... but not a Container. It defines a sequence but is not
bound by 23.1 Table 65 (but by 23.1 Table 66 - Reversible container
req). I have not found where basic_string<>::size() would be required to
be in constant time.

Michael

 

[Bo Persson]

Michael DOUBEZ wrote:
:: Bo Persson a écrit :
::: Michael DOUBEZ wrote:
::::: James Kanze a écrit :
:::::: On Jul 30, 12:03 pm, Juha Nieminen <[email protected]>
:::::: wrote:
::::::: Michael DOUBEZ wrote:
::::::::: Does the C++ standard state any speed requirements for the
::::::::: at() method?
::::::
:::::::: 23.1.1/12 specifies sequence container should implement it
:::::::: when it runs in constant time. IMO is applies to
:::::::: basic_string.
:::::
::::::: Is that the reason some very old versions of g++ didn't
::::::: support at() for basic_strings?
::::::
:::::: I doubt it. If that were the case, they wouldn't support
:::::: operator[] either. A more likely reason is that they
:::::: implemented it before at() got added to the standard.
:::::
::::: IMO there is no relation with operator[]. If
::::: basic_string::size() is O(n), I can still implement operator[]
::::: in O(1) but at() requires to know the size (for bound check)
::::: and thus cannot be implemented in O(1).
:::
::: But basic_string claims to be a Sequence container, which should
::: have a size() of "constant complexity" (23.1 Table 65).
::
:: basic_sting claims no such thing; it is designated as an object
:: containing ... but not a Container. It defines a sequence but is
:: not bound by 23.1 Table 65 (but by 23.1 Table 66 - Reversible
:: container req). I have not found where basic_string<>::size()
:: would be required to be in constant time.
::

Doesn't a reversible container first have to be a container?

Ok, my reasoning goes like this:

21.3/2
"The class template basic_string conforms to the requirements of a
Sequence, as specified in (23.1.1). Additionally..."

23.1.1/1
"A sequence is a kind of container that..."

Table 67 also says "Sequence requirements (in addition to container)".
I take this as a reference to Table 65.


Bo Persson

 

[Michael DOUBEZ]

Bo Persson a écrit :

Michael DOUBEZ wrote:
:: Bo Persson a écrit :
::: Michael DOUBEZ wrote:
::::: James Kanze a écrit :
:::::: On Jul 30, 12:03 pm, Juha Nieminen <[email protected]>
:::::: wrote:
::::::: Michael DOUBEZ wrote:
::::::::: Does the C++ standard state any speed requirements for the
::::::::: at() method?
::::::
:::::::: 23.1.1/12 specifies sequence container should implement it
:::::::: when it runs in constant time. IMO is applies to
:::::::: basic_string.
:::::
::::::: Is that the reason some very old versions of g++ didn't
::::::: support at() for basic_strings?
::::::
:::::: I doubt it. If that were the case, they wouldn't support
:::::: operator[] either. A more likely reason is that they
:::::: implemented it before at() got added to the standard.
:::::
::::: IMO there is no relation with operator[]. If
::::: basic_string::size() is O(n), I can still implement operator[]
::::: in O(1) but at() requires to know the size (for bound check)
::::: and thus cannot be implemented in O(1).
:::
::: But basic_string claims to be a Sequence container, which should
::: have a size() of "constant complexity" (23.1 Table 65).
::
:: basic_sting claims no such thing; it is designated as an object
:: containing ... but not a Container. It defines a sequence but is
:: not bound by 23.1 Table 65 (but by 23.1 Table 66 - Reversible
:: container req). I have not found where basic_string<>::size()
:: would be required to be in constant time.
::

Doesn't a reversible container first have to be a container?

Ok, my reasoning goes like this:

21.3/2
"The class template basic_string conforms to the requirements of a
Sequence, as specified in (23.1.1). Additionally..."

23.1.1/1
"A sequence is a kind of container that..."

An later:
"[..]The library provides three basic kinds of sequence container:
vector, list and deque.[...]"

No basic_string here so there are some misfit in the requierements with
a sequence container (perhaps simply iterator invalidation).

Table 67 also says "Sequence requirements (in addition to container)".
I take this as a reference to Table 65.

The "(in addition to container)" is not clear to me here but I agree it
argues in the sense of applying the complexity requirement of
container to string. What trigger my doubts is that 21.3/2 mention the
"Reversible container" and "sequence container" conformity but not the
"container" conformity; it carefully avoids it.

FROM SGI (perhaps outdated):
"Note that the C++ standard does not specify the complexity of
basic_string operations.[...]"

Appart from that, you can note that "Note A" is a SHOULD and not a MUST;
by example, list::size() complexity is linear (because of some
constraints on splice() methods). Here, we could say it is the opposite
case of list<>, basic_string::size() must be O(1) in order to allow the
implementation of at() in O(1) complexity.

Michael