The Beauty of Lists

So, if you take a look at my last post, you can see that I have taken a liking to the use of vectors over arrays in C++. While the current project in OOP naturally calls for a "has-many" relationship between two classes, I have found that there are other, possibly better options to use than vectors.

Lists, under the right circumstance, can prove to be a good option when random access is not required. This last week in another project from an operating systems course, a situation called for use of a linked list. It required a list of objects that was sorted under some characteristic defined in the class, and it required that addition of elements be as cheap as possible. Well, it turns out the C++ STL has a wonderfully built list already that I have only begun to scratch the surface of. In order to maintain the list in sorted order, it is as simple as overloading the "<" operator, pushing an object to the front of the list and then simply calling the sort function from list. i.e. someList.push_front(someObject) and then doing someList.sort(). While sorting vectors typically involves copying, for lists all that is required is rearrangement. Or in the words of the C++ reference:


The entire operation does not involve the construction, destruction or copy of any element object. They are moved within the container.


Sorting a vector, on the other hand, typically calls for the use of algorithm's sort unless a custom sort is created, but I really do not see why you would when creating comparison functions and using built-in sorts are so easy.

Some might argue that inserting into a list is actually more expensive than inserting into a vector. In some cases I could see this, because for small types it is extremely simple for the L2 cache to do its work on the entire vector (say if we are pushing to the front of the vector). For larger objects, as containers grow in size, this could prove to be a problem as the amount of copy calls grows. 


I would love to hear some points on the efficiencies of vectors vs. lists in the comments!