Vectors or Linked List?

[Thunderchook]

Hi,

I have just recently got back into C++ and learned that there are a number of newer ways of doing things.

I have an idea which I had intended to use a Linked List instead of a good old array, but I note that a vector appears to be simpler as they are simply an extendable-length array.

Which is generally preferred?
If using a vector, do you need to use memory allocation such as 'new' and 'delete' to ensure that you don't run out of space?
Is there anything else I should know?

Thanks,

Thunderchook.

[JLBorges]

> Which is generally preferred?

std::vector<> is the preferred sequence container.


> If using a vector, do you need to use memory allocation such as 'new' and 'delete'
> to ensure that you don't run out of space?

No.


> Is there anything else I should know?

Yes. Start with this: https://cal-linux.com/tutorials/vectors.html

[Thunderchook]

That's good advice.

Many thanks.

[gunnerfunner]

I have an idea ...

what exactly is your idea? std::vector is an ideal sequence container but if you need fast insertion or delete then std::list or std::forward_list might be more suitable or std::deque might be a halfway compromise with constant time insertion, deletion at both front and back && random access though its members are not stored contiguously

[JLBorges]

> if you need fast insertion or delete then std::list or std::forward_list might be more suitable

In the vast majority of real-life scenarios, even when there are a large number of inserts/deletes (at arbitrary positions), std::vector<> would still be the sequence container of choice.

Because of the different way in which list stores its data, it has some inherent properties which make it the sequence container of choice in certain contexts:

Modifiers of std::list<> do not invalidate iterators, references or pointers to the other elements.

std::list<> provides the 'strong-exception-guarantees' for modifiers; std::vector<> provides only the 'basic-exception-guarantee' for some modifiers

More information: http://www.cplusplus.com/forum/beginner/168846/#msg845650


Rationale for std::forward_list
http://www.cplusplus.com/forum/beginner/168846/#msg845410

[dhayden]

The right choice of vector, list, deque or any of the other containers depends largely on what operations you plan to do on it. If you have a lot of items in the container and you do a lot of insertions/deletions from the middle, then vector will make your i7 processor run like a Z80 because if you insert/delete the K^th item in a vector containing N items, then the program has to move items K+1 through N. If you're using a linked list, no items have to move at all.

On the other hand, if you need to access the K^th item frequently (for random values of K), then a vector will be smoking fast and a list will turn your computer into an Apple II. That's because finding the K^th element in a vector requires just a little arithmetic while finding the K^th element in a list requires traversing all K-1 items that precede it.

[JLBorges]

Repeat (verbatim now, instead of just a link):

In the vast majority of real-life scenarios, even when there are a large number of inserts/deletes, std::vector<> would still be the sequence container of choice.

I emphasize the importance of cache effects. In my experience, all but true experts tend to forget those when algorithms are discussed.

And, yes, my recommendation is to use std::vector by default. More generally, use a contiguous representation unless there is a good reason not to. Like C, C++ is designed to do that by default.
- Stroustrup http://www.stroustrup.com/bs_faq.html#list

Consider a simple example: generate N random integers and insert them into a sequence so that each is in its proper position in the numerical order. For example, if the random numbers are 5, 1, 4, and 2, the sequence should grow like this:
5
1 5
1 4 5
1 2 4 5

Once the N elements are in order, we remove them one at a time by selecting a random position in the sequence and removing the element there. For example, if we choose positions 1, 2, 0, and 0 (using 0 as the origin), the sequence should shrink like this:
1 2 4 5
1 4 5
1 4
4

Now, for which N is it better to use a linked list than a vector (or an array) to represent the sequence? If we naively apply complexity theory, that answer will be something like, “Is this a trick question? A list, of course!” We can insert an element into and delete from a linked list without moving other elements. In a vector, every element after the position of an inserted or deleted element must be moved. Worse still, if you don’t know the maximum number of elements in advance, it’s occasionally necessary to copy the entire vector to make room for another element.

Depending on the machine architecture and the programming language, the answer will be that the vector is best for small to medium values of N. When I ran the experiment on my 8-Gbyte laptop, I found N to be much larger than 500,000.

...

In an attempt at fairness, I didn’t use a binary search to speed up insertion into the vector. Nor did I use random access to find the deletion point in the vector version. This keeps the number of elements traversed the same for all versions. In fact, I used identical generic code for the vector and the lists.

Is this an academic curiosity? No. Infrastructure application developers tell me that compactness and predictable access patterns are essential for efficiency.
- Stroustrup http://www.stroustrup.com/Software-for-infrastructure.pdf

When the type of the elements in the sequence are more complex than an integer (say std::string), still consider using std::vector<> as the sequence container. Move semantics has profoundly changed the way that we think about performance.

For instance, for a sequence of 16000 random string insertions, 8000 removals from the middle:

echo '======== clang++ ========' && clang++ -std=c++14 -stdlib=libc++ -O3 -Wall -Wextra -pedantic-errors main.cpp && ./a.out
echo '========== g++ ==========' && g++ -std=c++14 -O3 -Wall -Wextra -pedantic-errors main.cpp && ./a.out
======== clang++ ========
vector:  1330 millisecs
  list:  3630 millisecs
========== g++ ==========
vector:   780 millisecs
  list:  4110 millisecs

http://coliru.stacked-crooked.com/a/216ea83c08605c45

Even when we refuse to exploit random access that std::vector<> provides, it still performs on par with std::list<> (for the above test, on the same machine.)

echo '======== clang++ ========' && clang++ -std=c++14 -stdlib=libc++ -O3 -Wall -Wextra -pedantic-errors main.cpp && ./a.out
echo '========== g++ ==========' && g++ -std=c++14 -O3 -Wall -Wextra -pedantic-errors main.cpp && ./a.out
======== clang++ ========
vector:  3070 millisecs
  list:  3120 millisecs
========== g++ ==========
vector:  2570 millisecs
  list:  3390 millisecs

http://coliru.stacked-crooked.com/a/49dea20dd2be73d2

[gunnerfunner]

I checked the performance of std::vector vs std::list vis-a-vis insert and this outcome is also quite in favor of std::vector. If there's anything do shout out.

#include <iostream>
#include <numeric>
#include <vector>
#include <list>
#include <ctime>
#include <cstdlib>
#include <iterator>

constexpr auto TRIALS = 10000;

int main()
{
    std::vector<int> myVec(10000);
    std::iota(myVec.begin(), myVec.end(), 0);
    const auto startVec = std::clock() ;
    srand( (unsigned)time( NULL ) ); 
    for (int i = 0; i < TRIALS; ++i)
    {
        auto pos = rand()%(myVec.size() - 1);
        auto itrVec = std::begin(myVec) + pos;
        myVec.insert(itrVec, 1);
    }
    auto timeVec = (std::clock() - startVec ) * 1000.0 / CLOCKS_PER_SEC ;

    std::list<int> myList(10000);
    std::iota(myList.begin(), myList.end(), 0);
    const auto startList = std::clock() ;
    srand( (unsigned)time( NULL ) ); 
    for (int i = 0; i < TRIALS; ++i)
    {
        auto pos = rand()%(myList.size() - 1);
        auto itrList = myList.begin();
        std::advance(itrList, pos);
        myList.insert(itrList, 1);
    }
    auto timeList = (std::clock() - startList ) * 1000.0 / CLOCKS_PER_SEC ;

    std::cout << "Vector: " << timeVec << '\n';
    std::cout << "List: " << timeList << '\n';
}

Sample Output

Vector: 70
List: 2500

[JLBorges]

To measure the difference in pure insert performance, replace line 20
// auto itrVec = std::begin(myVec) + pos; // O(1)
with

auto itrVec = std::begin(myVec) ;
for( ; pos != 0 ; --pos ) ++itrVec ; // O(N) 

and the difference in performance would be somewhat less dramatic.

http://coliru.stacked-crooked.com/a/199f7de552a7f501