Какие отличия существуют в трудности обращения к элементам в контейневах list и vector по индексу?

В контейнере vector доступ к элементам по индексу выполняется за константное время O(1), так как vector хранит элементы в непрерывном блоке памяти. Это позволяет быстро обращаться к любому элементу по индексу.

В контейнере list (двусвязный список) прямой доступ по индексу невозможен за константное время, так как элементы не лежат подряд в памяти. Чтобы получить элемент по индексу, нужно пройтись по списку от начала или конца, что занимает линейное время O(n).

Пример:

std::vector<int> v = {10, 20, 30};
int x = v[1]; // быстро, O(1)

std::list<int> l = {10, 20, 30};
// Чтобы получить элемент с индексом 1, нужно итерироваться:
auto it = l.begin();
std::advance(it, 1);
int y = *it; // медленнее, O(n)