Search code examples
listvectorcontainers

Good sources to understand Containers

I'm studying containers and their different performances.
When , for a vector, I read something like

"inserting elements other than the back is slow"

but for a list:

"fast insert/delete at any point"

My questions are:

  • How a vector is different from a list in such a way that the two sentences above are true?

  • How its a vector built differently from a list?

  • Is because they store their elements in different memory parts?

I was searching some sources to better understand these concepts.

Solution

  • All examples will be linked to C++ language as I believe it is perfectly described there

    Vectors

    Vectors are the same as dynamic arrays with the ability to resize themselves automatically when an element is inserted or deleted, with their storage being handled automatically by the container. Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators. In vectors, data is inserted at the end. Inserting at the end takes differential time, as sometimes there may be a need of extending the array. Removing the last element takes only constant time because no resizing happens. Inserting and erasing at the beginning or in the middle is linear in time.

    Vector is the dynamic array, but which can manage the memory allocated to itself. This means that you can create arrays whose length is set at runtime without using the new and delete operators (explicitly specifying the allocation and deallocation of memory).

    Lists

    Lists are sequence containers that allow non-contiguous memory allocation. As compared to vector, the list has slow traversal, but once a position has been found, insertion and deletion are quick. Normally, when we say a List, we talk about a doubly linked list. For implementing a singly linked list, we use a forward list.

    There are 2 types of lists:

    • Double linked list where each element has an address of [next] and [previous], to access first or last element you could you a specific function (e.g. in C++ front() or back() on the list - listName.front() will return you the 1st(0) element in your list), head.previous point to NULL and the tail.next point to NULL;
    • Single linked list where each element only has the link(knows) about the [next] element, and the last element in this list points to NULL.

    Now let's get back to your question:

    how a vector is different from a list in such a way that the two sentences above are true? How is a vector built differently from a list? Is it because they store their elements in different memory parts? I was searching some sources to better understand these concepts.

    As I have mentioned there are 2 types of lists (single linked and double liked), they are good when you are going to have:

    • many insertion/deletion everywhere except the end of a list;

    You could use vector in case you are planning to:

    • frequently access insert/delete elements at the end of a list;
    • access elements at the random position (as you could use [N] to access the element at any point, where the N is the index/position of an element.

    Whereas in the List you would need to use iterators to access the element at the position/index N.

    So vector is a dynamic array and they tend to perform faster when you are accessing it (since there is no additional wrapper over it, and you directly access a point in memory by the pointer).

    The list is a sequence container (so this one has a wrapper over some base language functionality) that sacrifices some point in favor of additional simplicity of insertion and deletion by providing a user with some useful methods to work with its elements.

    And to resolve you question, we could conclude the following:

    Vector

    inserting elements other than the back is slow

    List

    fast insert/delete at any point

    This can be judged by the structure they have what they are.

    • Insertion is swift in List because it is a linked list and this means what? Exactly, This means that the only change is to be taken to achieve it is to change the pointer of the [previous ] and the [next] item, and we are done!
    • Whereas in Vector it would take waaaay more time to insert an element anywhere other than at the end. This could be proven by the array concept. If you have an array of one million elements and you want to replace/delete/insert the element at the very beginning of the array it would need to change the position of each element that is coming after the altered element.

    List vs Vector Image: enter image description here

    images were taken from this sources: singly linked list double linked list double linked list 2nd image vector

    Also, try having a look here vector-vs-list-in-stl. Their comparison is well described there. + look through the-c-standard-template-library-stl, by going to the "Containers" section and checking the description and its methods.