CODEWITHSUNDEEP
c++list
Joseph
Joseph

Reputation: 599

Does a std::list point to the same memory?

I was wondering if a std::list pointed to the same memory, like a std::vector, of if when an element is, for example, push_backed, it simply is allocated using new and it points to the other elements (with next and prev)?

template<class T>
    struct node
    {
    node<T> *next, *prev;
    T value;
    };

Upvotes: 0

Views: 133

Answers (4)

Matthieu M.
Matthieu M.

Reputation: 299760

The Standard does not precise how any container is implemented (list, deque, vector, ...) however the requirements are so strict that it can generally be inferred nonetheless.

For example, a std::vector of size N must guarantee that &vec[0] + i = &vec[i] for i in [0, N) (which is fancy wording to mean it has a contiguous storage).

On the other hand, std::list must guarantee that:

  • insertion/removal is O(1)
  • insertion/removal does not affect any other element of the list: iterators to them are not invalidated and their address is stable

This stability implies a node-based container, so the canonical implementation is a doubly-linked list.

Upvotes: 1

David Schwartz
David Schwartz

Reputation: 182753

Neither do. Both containers own their elements and so inserting an element into the container will involve creating a new element. It has to be this way. Here's why:

{
    SomeContainer <T> container;

    {
        T element;
        container.push_back(element);
    }
    // Here

At this point, element is out of scope and no longer exists, but the container is still in scope. So the container must have created its own T with a different scope.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

First, std::vector does not point to the same memory after push_back, at least not all the time: if the allocated size is insufficient, std::vector would re-allocate its internal data block, and so it would point to a different place in memory.

Unlike std::vector, std::list is a linked list, so its head will put to the same place in memory after a push_back. However, std::list does not support fast random access to its elements.

Upvotes: 1

Paul Evans
Paul Evans

Reputation: 27567

Only vector is guaranteed by the standard to return a pointer to a contiguous block of memory for the address of the first element, so not so for list

Upvotes: 1

Related Questions