vectors faster than lists?
Hi,
sooo when I learned about lists I was told that in order to search for a value we'd have to go through every single node
whereas in an array we could just access it by index
which is way faster.
and that the only reason we use lists is because they don't have a fixed size like an array
but...recently learned about vectors which are as fast as arrays?
but doesn't have a fixed size? :o
is that true?
because if it is...
then why does lists even exist?
and why do arrays even exist?
sooo when I learned about lists I was told that in order to search for a value we'd have to go through every single node
whereas in an array we could just access it by index
which is way faster.
and that the only reason we use lists is because they don't have a fixed size like an array
but...recently learned about vectors which are as fast as arrays?
but doesn't have a fixed size? :o
is that true?
because if it is...
then why does lists even exist?
and why do arrays even exist?
Last edited on
closed account (E0p9LyTq)
| then why does lists even exist? |
http://www.cplusplus.com/reference/list/list/
| Compared to other base standard sequence containers (array, vector and deque), lists perform generally better in inserting, extracting and moving elements in any position within the container for which an iterator has already been obtained, and therefore also in algorithms that make intensive use of these, like sorting algorithms. |
---------
| and why do arrays even exist? |
Arrays were in C, were added to C++. C++ was originally implemented as enhancements to C (classes, OOP, etc.).
C++11 added an
array<> container that combines the performance and accessibility of a C-style array with the benefits of a standard container, such as knowing its own size, supporting assignment, random access iterators, etc.
Last edited on
| but...recently learned about vectors which are as fast as arrays? but doesn't have a fixed size? :o |
Yes and no.
Array is a continuous block of memory. The size of plain array (and std::array) is set during compilation.
The vector does allocate an array too, but dynamically when the program runs, with size based on input data.
It is possible to make the vector larger, but it means that
1. a new larger array is allocated
2. elements of the old are copied to the new array
3. the old array is deallocated
The list simply allocates space for the new elements.
Some programs use objects that cannot be copied. A vector cannot store them. (C++11 does change that a bit.)
| why does lists even exist? |
Why do screwdrivers exist? An able man can do a lot with a plain hammer and duct tape.
Why do humans live all around the Earth? Why spread to barren and cold places from lush and temperate areas?
New, different possibilities.
> but...recently learned about vectors which are as fast as arrays?
> but doesn't have a fixed size?
Yes. std::vector<> is at least as fast as a C-style resizeable array.
> then why does lists even exist?
std::list<> exists because it has two properties that std::vector<> does not have:
a. Addition, removal and moving the elements within the list or across several (allocator-compatible) lists does not invalidate iterators, pointers or references to elements in the list. An iterator or reference is invalidated only when the element referred to is deleted.
b. std::list<> has strong exception guarantees (commit-or-rollback) for some operations for which std::vector<> and std::deque<> provide only weak exception guarantees (consistency).
And a third, insert/erase performance, which would be relevant for monstrously large sequences.
Unfortunately, reality is often quite different from what career-teachers teach in classrooms. The value of N (the size of the sequence) above which std::list<> begins to outperform std::vector<> with insert/erase operations in arbitrary positions is so high that it is seldom encountered in practice. (This has become particularly true after C++11 and the advent of move semantics.)
Stroustrup gives an example: http://www.cplusplus.com/forum/general/155310/#msg800593
It is quite easy to construct a similar example using a non-trivially copyable, but moveable type like std::string and measure std::list<> vs.std::vector<> performance.
If performance is important for the program, measure it. One measurement for the typical use-case in a program is more valuable than a thousand opinions.
> but doesn't have a fixed size?
Yes. std::vector<> is at least as fast as a C-style resizeable array.
> then why does lists even exist?
std::list<> exists because it has two properties that std::vector<> does not have:
a. Addition, removal and moving the elements within the list or across several (allocator-compatible) lists does not invalidate iterators, pointers or references to elements in the list. An iterator or reference is invalidated only when the element referred to is deleted.
b. std::list<> has strong exception guarantees (commit-or-rollback) for some operations for which std::vector<> and std::deque<> provide only weak exception guarantees (consistency).
And a third, insert/erase performance, which would be relevant for monstrously large sequences.
| Compared to other base standard sequence containers (array, vector and deque), lists perform generally better in inserting, extracting and moving elements in any position within the container for which an iterator has already been obtained |
Unfortunately, reality is often quite different from what career-teachers teach in classrooms. The value of N (the size of the sequence) above which std::list<> begins to outperform std::vector<> with insert/erase operations in arbitrary positions is so high that it is seldom encountered in practice. (This has become particularly true after C++11 and the advent of move semantics.)
Stroustrup gives an example: http://www.cplusplus.com/forum/general/155310/#msg800593
It is quite easy to construct a similar example using a non-trivially copyable, but moveable type like std::string and measure std::list<> vs.std::vector<> performance.
If performance is important for the program, measure it. One measurement for the typical use-case in a program is more valuable than a thousand opinions.
Topic archived. No new replies allowed.