C++: What is the difference between std::list and std::vector?

list — doubly linked list. vector — dynamic array.

std::list:

• Non-contiguous memory.
• Insert/delete O(1) anywhere.
• No random access.
• Cache-unfriendly.

1std::list<int> l = {1, 2, 3};
2l.push_back(4);
3l.insert(l.begin(), 0);  // O(1)
4// l[2];  // Error! No operator[]

std::vector:

• Contiguous memory.
• Random access O(1).
• Insert/delete middle O(n).
• Cache-friendly.

1std::vector<int> v = {1, 2, 3};
2v.push_back(4);
3v[2] = 10;  // O(1) random access

When to use:

• list — frequent insert/delete in middle.
• vector — most other cases.