Deborah R. Fowler
Vectors - and why
to use them!
Posted on Nov 1 2020Updated on Nov 1 2020
Data structures are important for storing and accessing data quickly. More efficient data structures for the type of data that is being stored can make a significant difference. For example, in the context of computer graphics, OpenVDB implemented a data structure whose efficiency allowed films with volumetric effects to gain huge performance increases (see OpenVDB history).
One day I was thinking about the implementation of vectors and how they relate to arrays and it lead me to the following:
You may have learned that linked lists (lists that allow for ease of insertion and deletion by storing backward and forward pointers to elements in the list) were the best for data in which you are doing many insertions and deletions. Interestingly enough, this is now not the case. In 2012, Bjarne Stroustup presented research done by Jon Bentley in this area to dispute this believe, which was a surprise to Computer Scientist. This work is presented in two talks that I have included below. As it turns out, the implementation of vectors and the advantage of continguous memory placement far outweighs the advantage of linked lists, even with large amounts of data. Vectors for insertion or deletion, shuffle the other elements to maintain this consistency and that operation turns out to be fast.
Bottom line - use vectors!
Below are the links to the two presentations mentioned:
- Bjarne Stroustrup's presentation titled "Why you should
avoid Linked Lists" Jul, 2012 "he explains the
reason that linked lists, and linked structures, are so bad for
performance, even in the scenarios that programmers think that
linked lists would be good"
- Herb Sutter, Partner Program Manager, Microsoft "Modern C++ What you Need to Know" (timestamp 47:30)
- Bjarne Stroustrup wiki and stroustrup.com/
- Herb Sutter wiki and herbsutter.com