Does the C++ vector template class use pointer-based link lists?

Discussion in 'C++' started by Ash Lux, Feb 19, 2004.

  1. Ash Lux

    Ash Lux Guest

    Does the C++ vector template class use pointer-based link lists?

    Could I get a link explaining how it works, regardless of what it uses?

    Thank You,

    Ash Lux
    Ash Lux, Feb 19, 2004
    #1
    1. Advertising

  2. Ash Lux

    David Rubin Guest

    Ash Lux wrote:

    > Does the C++ vector template class use pointer-based link lists?


    Although the standard does not specify how classes should be implemented,
    vectors are almost certainly not implementd as linked lists. I imagine the
    typical implementation is a single contiguous array of elements (as opposed to a
    deque).

    /david

    --
    Andre, a simple peasant, had only one thing on his mind as he crept
    along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
    -- unknown
    David Rubin, Feb 19, 2004
    #2
    1. Advertising

  3. Ash Lux

    E. Mark Ping Guest

    In article <>,
    Ash Lux <> wrote:
    >Does the C++ vector template class use pointer-based link lists?


    No. A recent clarification of the standard requires std::vector to
    use contiguous memory. So that for:

    int n = some_size;
    int i = some_index_less_than_n;
    vector<T> v(n);
    T* p = &v[0];

    The expressions p and v refer to the same object.

    >Could I get a link explaining how it works, regardless of what it uses?


    There have been numerous print articles and posts over the years.
    What you really want is a comparison of the various containers, their
    performance rules, and behaviors.

    A brief overview is here:
    http://www.cs.rpi.edu/projects/STL/htdocs/node52.html

    Dinkumware's documentation is superb (and they supply the standard
    library for MS Visual C++ 6.0 and .Net which are some of the most
    common implementations). You can browse it online or buy it.

    Containers are listed here:
    http://www.dinkumware.com/manuals/reader.aspx?b=p/&h=lib_cont.html
    --
    Mark Ping
    E. Mark Ping, Feb 19, 2004
    #3
  4. "Ash Lux" <> wrote in message
    news:...
    > Does the C++ vector template class use pointer-based link lists?
    >
    > Could I get a link explaining how it works, regardless of what it uses?
    >
    > Thank You,
    >
    > Ash Lux


    http://www.dinkumware.com/refxcpp.html

    john
    John Harrison, Feb 19, 2004
    #4
  5. Ash Lux wrote:
    >
    > Does the C++ vector template class use pointer-based
    > link lists?
    >
    > Could I get a link explaining how it works, regardless
    > of what it uses?


    From memory, one of the requirements of the vector template
    specificed by the standard is O(1) access to all elements.
    This cannot be guaranteed by a linked list implementation.

    Erik
    --
    +-----------------------------------------------------------+
    Erik de Castro Lopo (Yes it's valid)
    +-----------------------------------------------------------+
    "There are two ways of constructing a software design. One way is
    to make it so simple that there are obviously no deficiencies
    and the other is to make it so complicated that there are no
    obvious deficiencies." -- C A R Hoare
    Erik de Castro Lopo, Feb 19, 2004
    #5
  6. "David Rubin" <> wrote in message
    news:c137eb$...
    > Ash Lux wrote:
    >
    > > Does the C++ vector template class use pointer-based link lists?

    >
    > Although the standard does not specify how classes should be implemented,
    > vectors are almost certainly not implementd as linked lists. I imagine the
    > typical implementation is a single contiguous array of elements (as

    opposed to a
    > deque).
    >


    I believe the next version of C++ will insist that vectors be implemented as
    a single contiguous block of memory. There's a defect report to this effect,
    http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#69.

    I think its generally agreed that its impossible to implement the current
    requirements any other way.

    john
    John Harrison, Feb 19, 2004
    #6
  7. Ash Lux

    Ash Lux Guest

    Thank You for the help, I appreciate it.
    Ash Lux, Feb 20, 2004
    #7
    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. Jonathan Bartlett
    Replies:
    3
    Views:
    433
  2. christopher diggins
    Replies:
    16
    Views:
    745
    Pete Becker
    May 4, 2005
  3. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    397
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  4. Replies:
    8
    Views:
    1,911
    Csaba
    Feb 18, 2006
  5. Replies:
    7
    Views:
    445
    Adam Nielsen
    Sep 28, 2007
Loading...

Share This Page