Why Strings as Classes?

[Bill Baxter]

On Wed, Aug 27, 2008 at 9:49 AM, Michiel Helvensteijn <nomail at please.com> wrote:
> Dee Girl wrote:
>
>>> Yes, the first 'trick' makes it a different datastructure. The second
>>> does not. Would you still be opposed to using opIndex if its
>>> time-complexity is O(log n)?
>>
>> This is different question. And tricks are not answer for problem. Problem
>> is list has other access method than array.
>
> And what's the answer?
>

The complexity of STL's std::map indexing operator is O(lg N).
So it is not the case even in the STL that [] *always* means O(1).

Plus, if the element is not found in the std::map when using [], it
triggers an insertion which can mean an allocation, which means the
upper bound for time required for an index operation is whatever the
upper bound for 'new' is on your system.

But std::map is kind of an oddball case.  I think a lot of people are
surprised to find that merely accessing an element can trigger
allocation.  Not a great design in my opinion, precisely because it
fails to have the behavior one would expect out of an [] operator.

--bb