Complexity requirement for indexing

[Alf P. Steinbach /Usenet]

I started out searching for complexity requirements for std::deque:perator[].

But then I ended up doing the same for std::vector:perator[].

It seems to reduce to *(begin() + i), where begin() is guaranteed constant time,
but regarding the '+ i', for random access iterators that's defined by a loop,
with no complexity requirement that I can see.

Loopety-loop-loop, loop loop.

So, is there any complexity requirement at all (better than linear)?

Perhaps I'm blind on both eyes again, it has happened before...


Cheers,

- Alf

 

[Johannes Schaub (litb)]

I started out searching for complexity requirements for
std::deque:perator[].

But then I ended up doing the same for std::vector:perator[].

It seems to reduce to *(begin() + i), where begin() is guaranteed constant
time, but regarding the '+ i', for random access iterators that's defined
by a loop, with no complexity requirement that I can see.

Loopety-loop-loop, loop loop.

So, is there any complexity requirement at all (better than linear)?

Perhaps I'm blind on both eyes again, it has happened before...

I'm going to enlight you with c++03 23.1.1/12:

`Table 68 lists sequence operations that are provided for some types of
sequential containers but not others. An implementation shall provide these
operations for all container types shown in the "container" column, and
shall implement them so as to take amortized constant time.`

Cheers!

 

[Juha Nieminen]

It seems to reduce to *(begin() + i), where begin() is guaranteed constant time,
but regarding the '+ i', for random access iterators that's defined by a loop,
with no complexity requirement that I can see.

"random access iterator + integral" is defined as a constant-time
operation. It's different for non-random-access iterators.

 

[Johannes Schaub (litb)]

"random access iterator + integral" is defined as a constant-time
operation. It's different for non-random-access iterators.

The Standard says though

"In some cases the semantic requirements are presented as C++ code. Such
code is intended as a specification of equivalence of a construct to another
construct, not necessarily as the way the construct must be implemented."

Dunno, but it sounds to me as if such operational sematic descriptions don't
intend to state complexity requirements.

 

[Alf P. Steinbach /Usenet]

* Johannes Schaub (litb), on 27.08.2010 13:13:

I started out searching for complexity requirements for
std::deque:perator[].

But then I ended up doing the same for std::vector:perator[].

It seems to reduce to *(begin() + i), where begin() is guaranteed constant
time, but regarding the '+ i', for random access iterators that's defined
by a loop, with no complexity requirement that I can see.

Loopety-loop-loop, loop loop.

So, is there any complexity requirement at all (better than linear)?

Perhaps I'm blind on both eyes again, it has happened before...

I'm going to enlight you with c++03 23.1.1/12:

`Table 68 lists sequence operations that are provided for some types of
sequential containers but not others. An implementation shall provide these
operations for all container types shown in the "container" column, and
shall implement them so as to take amortized constant time.`

Thanks.

I was going to reply sooner but I got new Thunderbird version and it's even
worse than the previous one. It's up at 170 MiB memory usage and using 90% CPU
half the time. I am CONTINUALLY CURSING, using words I can't post here, but
suffice it to say that I now do not see much difference between Mozilla and
Microsoft competence in software development; if anything Mozilla's worse now.

Oh, goshdarn, but anyway, thanks!


Cheers,

- Alf

 

[Alf P. Steinbach /Usenet]

* Juha Nieminen, on 27.08.2010 13:19:

"random access iterator + integral" is defined as a constant-time
operation. It's different for non-random-access iterators.

Thanks Juha.

Had to search a bit to find it, but I found that also (after reading your reply).

T'was well hidden, as explanation of why tables /don't/ include complexity
requirements...


Cheers,

- Alf

 

[Johannes Schaub (litb)]

The Standard says though

"In some cases the semantic requirements are presented as C++ code. Such
code is intended as a specification of equivalence of a construct to
another construct, not necessarily as the way the construct must be
implemented."

Dunno, but it sounds to me as if such operational sematic descriptions
don't intend to state complexity requirements.

If they would, we would have a contradiction between the loop found by APS
and the definition of constant-time conplexity found by you

 

[Pavel]

* Johannes Schaub (litb), on 27.08.2010 13:13:

I started out searching for complexity requirements for
std::deque:perator[].

But then I ended up doing the same for std::vector:perator[].

It seems to reduce to *(begin() + i), where begin() is guaranteed
constant
time, but regarding the '+ i', for random access iterators that's
defined
by a loop, with no complexity requirement that I can see.

Loopety-loop-loop, loop loop.

So, is there any complexity requirement at all (better than linear)?

Perhaps I'm blind on both eyes again, it has happened before...

I'm going to enlight you with c++03 23.1.1/12:

`Table 68 lists sequence operations that are provided for some types of
sequential containers but not others. An implementation shall provide
these
operations for all container types shown in the "container" column, and
shall implement them so as to take amortized constant time.`

Thanks.

I was going to reply sooner but I got new Thunderbird version and it's
even worse than the previous one. It's up at 170 MiB memory usage and
using 90% CPU half the time. I am CONTINUALLY CURSING, using words I
can't post here, but suffice it to say that I now do not see much
difference between Mozilla and Microsoft competence in software
development; if anything Mozilla's worse now.

[OT]
Interesting. Seamonkey suite (re-christened Mozilla suite) works just
fine for me. Recently I have played with Google Chrome and it feels much
faster to me than either IE or Mozilla-family of browsers but I am
hesitant to migrate to it fully exactly because it lacks integrated
mail/news client.

Just checked my resource utilization: Seamonkey (browser+news/mail
reader windows are opened although no fancy pages are loaded) takes 49MB
and 0 to 1 % of CPU as I am typing this.

-Pavel