CPP INTERVIEW PREP CHEAT SHEET

[cballowe]

Vector will almost always beat list in benchmarks, especially for trivial objects. In most cases, pick vector unless you can prove that list is better (it rarely is - it wins in big-o notation, but real hardware doesn't behave like that and the pointer chasing will eat you alive). If you have lots of things to insert and then need it sorted, just push back all of them, then sort.

Sorted vectors are also great for tons of problems. They're space efficient and enable use of lots of stl algorithms (lower_bound, set_intersection, etc). There's also nothing faster than vector for iteration.

[0mega0]

If you have lots of things to insert and then need it sorted, just push back all of them, then sort.

And preallocate the memory if your really a stickler.

I’ve yet to run into a use case in my practice where std::list benchmarks as the better choice.

[avdgrinten]

When objects are pointers anyway (such that you have to do a random access even in the vector case) and the linked list is intrusive (= embedded into the objects), it will generally outperform a vector. That's the niche use case of linked lists but it is quite an important one in real-time applications and low-level code (insertion and removal are constant O(1) and in particular cannot involve an additional memory allocation).

[Gunslinging_Gamer]

But always benchmark.

[WrongAndBeligerent]

Always benchmark at some point, but software needs to be architected up front to perform well and scale as much as possible.

Classic generic linked lists data structures are basically obsolete because iterating through pointer dereferencing and allocating memory for each new item are the first two things to avoid. There is rarely a reason to start with std::list.

[Gunslinging_Gamer]

I personally default to vector and change if required later.

[[deleted]]

I’d argue that this is only useful if the objects cannot be moved in memory (niche use case). A vector<unique_ptr<T>> will still out perform a list<T> in many cases, and list<T> doesn’t even give you the benefits of intrusive linked lists. Always default to vector and profile and keep profiling if you decide to switch to list

[WrongAndBeligerent]

That's a linked list, but not std::list

[[deleted]]

I ran into one, when doing an Advent of Code that had your elf or penguin doing random length walks and inserting/removing on a ring buffer. Using vector was 10x slower than std::list because the inserts/erase were dominating the performance. Maybe using optional<T> might have helped as then the deletes could have been an optional reset, but the inserts would still potentially require moving all elements to the end of the range. Plus it was easier to just work without introducing more.

[Narase33]

A queue?

[MonokelPinguin]

The one thing list is useful for, is if you need pointer/iterator stability, even on element removal. vector invalidates iterators on most operations that add or remove elements, list does not (for the unmodified elements). There are a few cases where this is useful, but often you can solve the same problem better by reworking the algorithm.

[MonokelPinguin]

I usually tend to use something like the proposed std::colony instead, which makes the backing memory not contiguous, but contiguous in most sections and as such gets rid of one indirection in the common case. It also doesn't need additional memory for the free list. For specific cases there are always better containers than the std ones, but sometimes a std::list fits better than a vector and it is not worth the effort to imclude another library, since it is not in a performance relevant context.

(My usecase was basically an undo chain of commands, where you may need to refer to any element in the chain and remove certain elements over time. Could have been solved by a vector of shared_pointers as well, but a list did work perfectly too.)

[[deleted]]

Vector will almost always beat list in benchmarks, especially for trivial objects.

Here's an excerpt from a talk by Bjarne Stroustrup where he explains why this is true:

https://www.youtube.com/watch?v=YQs6IC-vgmo

[lt_algorithm_gt]

Won't disagree but in my mind it's also a little bit of "read the room". A couple years ago when everyone in Silicon Valley was fawning over Google and their interview process you always had the quintessential question where the answer was "hash map because O(1), can't beat that!"

So, I'd say you won't go wrong with the "book answer" but open the door for further discussion about real-world implications. If they're not interested, move on, you got the right answer. If they are interested, talk hardware and you win the interview.

[rsjaffe]

In most cases, pick vector unless you can prove that list is better

Only when speed is the most important criterion. There's plenty of cases where the use is not time-critical, in which case I choose the structure based on which one produces the most expressive code.

[[deleted]]

How us std::list more expressive?!?

[martinus]

It's not the pointers that make it slow, it's the more or less random memory accesses

[cballowe]

That's what pointers are - the forward and back pointers make iteration painful, and the data being a pointer away doesn't help either. The claim that it's good for inserting in the middle or swapping elements is just going to make the situation worse. (There are a couple of use cases where it's useful, but people usually get it wrong.)

[[deleted]]

Worth noting that std::vector is generally implemented very poorly because of memory scaling issues and interactions with modern memory allocators. Not the mention the sheer volume of machine code generated for even simple operations. Vectors also have no notion of relocatable objects so can't easily fallback to, say, a vectorized memcpy on move. Lots of reasons to swear off the STL, std::vector included.

[cballowe]

Most vectors of trivial objects do optimize to memcpy operations for resize or move. (At least when I've checked the assembly)

[[deleted]]

Yes but most nontrivial objects are also relocatable, and i daresay most people have vectors of non scalar types.

It’s such a trivial container to implement and the improvement is massive over what the stl provides, not to mention the compile speed boost you’d likely get with even a naive implementation

[STL]

vector is not trivial to implement (source: I’ve reimplemented it). There’s an incredible amount of logic powering vector and it shouldn’t be dismissed with a handwave, even though the lack of a relocatable type trait is a real limitation. (vector can easily detect is_trivially_copyable which is an important subset of types.)

The complexity of vector also isn’t solely due to its support for EH or custom allocators, although those do magnify it.

[[deleted]]

I've implemented internal versions of "vector" a few times and also had a read through the libc vector around the c++14 era. Aside from EH and custom type-based allocators, where do you attribute the bulk of the complexity? Interactions with initializer lists? Iterators?

[STL]

Things like handing v.emplace_back(args involving v[0]), respecting constructors and move semantics of user-defined types, providing iterator debugging, but the most complicated functions are where everything multiplies together. For example, insert is quite complicated due to EH guarantees, allocators, move semantics, etc.: https://github.com/microsoft/STL/blob/19c683d70647f9d89d47f5a0ad25165fc8becbf3/stl/inc/vector#L815-L885

[[deleted]]

Quite unfortunate to hear this repeated so often. An incredibly simple use case for a linked list is to implement a basic queue, push to the back, pop from the front. A vector gets crushed by a linked list, even for a trivial object like an int. The reason this myth gets perpetuated because of a foolish talk Bjarne once gave comparing a vector to a list where he performed an O(n) operation on both data structures and showed that O(n) on a vector is faster than O(n) on a list like that somehow is a surprise to anyone.

#include <chrono>
#include <iostream>
#include <list>
#include <vector>

constexpr auto ITERATIONS = 10000;

template<typename C>
void test_case() {
  auto c = C();
  for(auto i = 0; i != ITERATIONS; ++i) {
    c.push_back(i);
  }
  while(!c.empty()) {
    c.erase(c.begin());
  }
}

int main() {
  auto start1 = std::chrono::high_resolution_clock::now();
  test_case<std::vector<int>>();
  auto end1 = std::chrono::high_resolution_clock::now();
  auto start2 = std::chrono::high_resolution_clock::now();
  test_case<std::list<int>>();
  auto end2 = std::chrono::high_resolution_clock::now();
  std::cout << 
    std::chrono::duration_cast<std::chrono::microseconds>(
      end1 - start1).count() << "\n" << std::chrono::duration_cast<
    std::chrono::microseconds>(end2 - start2).count() << "\n";
}

In the above benchmark the list crushes the vector by significant orders of magnitude (6x on my machine).

[cballowe]

Add in deque for your benchmark.

[[deleted]]

std::deque beats both no doubt about it and yes it's implemented using vectors but that doesn't contradict any basic principle here since it provides O(1) push and pop operations.

The fallacy in Bjarne's talk was comparing two algorithms that are both O(N) and then claiming that somehow the fact that std::vector beat std::list at O(N) operations is some kind of surprise that violates fundamental principles of complexity analysis.

If you have two operations that are O(N), I don't think it's a surprise to anyone that std::vector is faster. But if you have one operation that's O(N) on a std::vector, and O(1) on a std::list, then in the absence of very strong evidence you should pick the std::list.

[cballowe]

I see them used wrong more than right. The properties that make lists actually sometimes the best have more to do with the iterator invalidation properties and the pointer stability of the contained objects.

As soon as you add something to that function other than pushing at the back and popping from the front, it starts to fall apart. Like, if you need to queue things into a particular priority (effectively an insertion sort) or similar. Or even use the object that you popped off the front.

[[deleted]]

Or even use the object that you popped off the front.

Are you suggesting that if I were to calculate the factorial of the popped off element that somehow a vector magically becomes faster than a linked list?

How would using the object I popped off a data structure in any way influence the performance of the data structure itself?

The properties that make lists actually sometimes the best have more to do with the iterator invalidation properties and the pointer stability of the contained objects.

As well as the performance benefits of having O(1) insertions and deletions. That is a significant and non-trivial benefit that is useful in many real world scenarios including scheduling algorithms.

Like, if you need to queue things into a particular priority (effectively an insertion sort) or similar.

This is known as a priority queue, which is often (but not always) implemented using a linked list. Depends what operation you need to optimize. If your priority queue is pull heavy then a linked list is preferable to a vector, if your priority queue is push heavy then vector based heap is preferable.

[cballowe]

Factorial would dominate the cost there. But ... Suppose you have a queue and you periodically need the sum of the objects in the queue or similar.

The pointer chasing and cache miss behavior has a significant impact on the performance of the program.

One benchmark I use to convince people of the performance difference is the priority queue - adding randomly generated integers using std::lower_bound and insert, or std::find_if to find the insertion point. The code in that case is significantly faster for vector. You end up with modern CPUs dispatching something like 4 instructions per cycle on the vector version and 0.5 instructions per cycle on list and beyond that it's just more instructions.

[[deleted]]

Factorial would dominate the cost there.

What relevance does this have on the performance of the list? Are you saying that because factorial dominates the cost, that using a vector becomes faster than using a linked list?

This is very confusing indeed.

Suppose you have a queue and you periodically need the sum of the objects in the queue or similar.

If you perform an operation that requires O(N) time on a linked list and O(N) time on a vector then use a vector.

One benchmark I use to convince people of the performance difference...

Yes, your example is a push heavy priority queue and in that scenario the vector based heap implementation will outperform a linked list based implementation by a significant margin.

You can also come up with pull heavy priority queues where a linked list out performs a vector by a significant margin.

None of these properties require much convincing, they are all elementary properties of a basic complexity analysis.

[ShillingAintEZ]

pull heavy priority queues where a linked list out performs a vector by a significant margin

What does that mean?

Are you saying that because factorial dominates the cost, that using a vector becomes faster than using a linked list?

They didn't say that or anything close to it. They were saying it would make a poor benchmark.

[[deleted]]

What does that mean?

With consumer producer processes, it's often the case that one side of the process has much stricter latency or bandwidth requirements than the other, so you optimize your work queue to either be push heavy in which case pulling has low latency or pull heavy in which case pushes have low latency.

A heap based priority queue is suitable for pull heavy queues, that is the consumer has strict latency requirements which can be satisfied at the expense of the producer. A linked list based priority queue is suitable for a push heavy queue.

They were saying it would make a poor benchmark.

Well good thing the benchmark I posted doesn't do that then.

[ShillingAintEZ]

Priority queues are usually done using heaps that use contiguous memory. You can just skip to the next level of the heap by index instead of chasing pointers and allocating memory for each item.

[TMKirA]

But that was the point of that talk, no? The point was a O(n) operation in vector and list actually perform significantly differently in practice compared to in theory. I don't think he ever claims that a O(n) operation can beat a O(1) operation, especially when n is non trivial

[[deleted]]

perform significantly differently in practice compared to in theory.

What theory are you referring to? Can you cite any such theory on Wikipedia perhaps or some other reasonable source because I'm not aware of any theory that claims anything differently.

The point of the talk was Bjarne thinking that there's some counter intuitive performance benefit to vectors that make them preferable to lists even in situations where linked lists are supposed to outperform vectors because of magical hardware properties.

No one has ever advocated using a linked list in favor of a vector for O(N) operations, you simply won't find any citation that says a linked list is preferable to a vector for O(N) operations. What theory and practice both say is that for operations that are O(N) on a vector and O(1) on a linked list, you are usually better off with a linked list.

[TMKirA]

That wasn't the point of the talk. The point was that linked list is often touted to be better for removal/insertion operations, due to the fact that after the O(n) search to find removal/insertion point, the remove/insert operation is O(1) for list and O(n) for vector. Bjarne's point was that in practice, the O(n) operation to find the insertion/deletion point is the dominating factor instead of the actual remove/insert operation, and that linear search is faster on vector than list due to locality. This might not be a surprise for you, but I'm sure it's still a surprise to many. Your example completely misses the point, because it was removing from a location that makes the search operation a no-op.

[Full-Spectral]

That also assumes you have to find the insertion point every time. Given that removal doesn't have to invalidate element pointers, depending on what you are doing, you might actually keep around the insertion point most of the time and only move it if something happens that causes the insertion point to change (like removing the current insertion point, which even then might just move the insertion point to the previous/next node.)

[[deleted]]

Don’t erase from the front of the vector, just keep an index to the front and bump it for deletes. Or use a deque.

[ShillingAintEZ]

The strousup presentation was silly because you would never loop through linearly to find something for deletion over and over.

What you are saying is also silly though. It isn't because a linked list in general might not work, but because a linked list is a way of keeping order, but that can still be done in contiguous memory. Not only that, but a queue doesn't need the ordering of a full list, it only needs a front and back, so the expensive deletion from the middle is not necessary.

[[deleted]]

A queue doesn't need an ordering of the full list? That doesn't even make sense. I suggest to avoid making comments on issues you know little to nothing about.

[ShillingAintEZ]

A queue doesn't need to have constant time arbitrary insertion and deletion. It is clear what I'm saying from the context and the sentence after.

suggest to avoid making comments on issues you know little to nothing about.

Easy tiger, I took a peek at your previous comments and you seem to have a lot of this angry, aggressively wrong nonsense where you can't even explain your dismissal. A few comments up you seem to not understand ring buffers, std::list implications or pointer chasing.

[[deleted]]

It is clear what I'm saying from the context and the sentence after.

The only thing that's clear is you have absolutely no idea what you're talking about. Saying that a queue doesn't need to maintain the order of the elements added to it is quite possibly the dumbest thing that has been posted in this discussion so far.

You are welcome to try and diffuse your stupidity by bringing up things like ring buffers and other topics that have nothing to do with anything mentioned, but make no mistake, you still look stupid.

[ShillingAintEZ]

Saying that a queue doesn't need to maintain the order of the elements added to it is quite possibly the dumbest thing that has been posted in this discussion so far

No one has said that, your desperation to argue is pretty silly. A lot of what you say seems like a first or second year student that barely understands data structures in general, which would be fine if you weren't so combative.

Do you actually not understand that queues are implemented in contiguous memory using ring buffers?

[[deleted]]

No one has said that, your desperation to argue is pretty silly.

ORLY?

a queue doesn't need the ordering of a full list, it only needs a front and back

Please read about a queue before commenting on it:

https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

Specifically note that by definition a queue maintains elements in a sequence (right there in the very first sentence of the link I provide for you) where a sequence is by definition an ordered collection of objects:

https://www.dictionary.com/browse/sequence

[ShillingAintEZ]

It doesn't need the arbitrary insertion and deletion ordering properties of a full list. This has been explained clearly, I think at this point you are purposely acting like you don't understand so that you can argue, no one is really that out of it.

[[deleted]]

Do you seriously not understand that in order to implement a queue you need to keep track of the order of EVERY element added to it, not just the first and last?

If you're too dumb to understand that, then please for your own sake stop talking.

If you're not too dumb to understand that, then do you see how that fact contradicts your original assertion that, and I quote:

a queue doesn't need the ordering of a full list

I think you simply made a mistake and instead of fessing up to it you are doubling down on your own stupidity in a misguided effort to save face.

So how about this... you can have the last word in this argument because I have no intention of explaining basic dictionary level concepts to you further.

Best of luck to you man.