C++ Resources

Updated on Nov 1  2020



C++CompilersCommandLineIDEsQuickSummary

Deborah R. Fowler



Vectors - and why to use them!

Posted on Nov 1  2020
Updated 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:
For more reading consider (wiki and websites)