Complexity requirement for indexing

Discussion in 'C++' started by Alf P. Steinbach /Usenet, Aug 27, 2010.

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

    But then I ended up doing the same for std::vector::eek: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

    --
    blog at <url: http://alfps.wordpress.com>
    Alf P. Steinbach /Usenet, Aug 27, 2010
    #1
    1. Advertising

  2. Alf P. Steinbach /Usenet wrote:

    > I started out searching for complexity requirements for
    > std::deque::eek:perator[].
    >
    > But then I ended up doing the same for std::vector::eek: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!
    Johannes Schaub (litb), Aug 27, 2010
    #2
    1. Advertising

  3. Alf P. Steinbach /Usenet <> wrote:
    > 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.
    Juha Nieminen, Aug 27, 2010
    #3
  4. Juha Nieminen wrote:

    > Alf P. Steinbach /Usenet <> wrote:
    >> 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.



    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.
    Johannes Schaub (litb), Aug 27, 2010
    #4
  5. * Johannes Schaub (litb), on 27.08.2010 13:13:
    > Alf P. Steinbach /Usenet wrote:
    >
    >> I started out searching for complexity requirements for
    >> std::deque::eek:perator[].
    >>
    >> But then I ended up doing the same for std::vector::eek: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

    --
    blog at <url: http://alfps.wordpress.com>
    Alf P. Steinbach /Usenet, Aug 27, 2010
    #5
  6. * Juha Nieminen, on 27.08.2010 13:19:
    > Alf P. Steinbach /Usenet<> wrote:
    >> 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.


    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

    --
    blog at <url: http://alfps.wordpress.com>
    Alf P. Steinbach /Usenet, Aug 27, 2010
    #6
  7. Johannes Schaub (litb) wrote:

    > Juha Nieminen wrote:
    >
    >> Alf P. Steinbach /Usenet <> wrote:
    >>> 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.

    >
    >
    > 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 :)
    Johannes Schaub (litb), Aug 27, 2010
    #7
  8. Alf P. Steinbach /Usenet

    Pavel Guest

    Alf P. Steinbach /Usenet wrote:
    > * Johannes Schaub (litb), on 27.08.2010 13:13:
    >> Alf P. Steinbach /Usenet wrote:
    >>
    >>> I started out searching for complexity requirements for
    >>> std::deque::eek:perator[].
    >>>
    >>> But then I ended up doing the same for std::vector::eek: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

    >
    > Oh, goshdarn, but anyway, thanks! :)
    >
    >
    > Cheers,
    >
    > - Alf
    >
    Pavel, Aug 31, 2010
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. C
    Replies:
    0
    Views:
    490
  2. reducing complexity

    , Oct 12, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    339
  3. Emin
    Replies:
    4
    Views:
    407
    Paul McGuire
    Jan 12, 2007
  4. Skybuck Flying
    Replies:
    30
    Views:
    1,093
    Bill Reid
    Sep 19, 2011
  5. C
    Replies:
    3
    Views:
    215
    Manohar Kamath [MVP]
    Oct 17, 2003
Loading...

Share This Page