доступ к std :: list в середине

Question

У меня есть дурацкий вопрос. Я всегда читал, что контейнер C ++ std::list имеет постоянное время для вставки элементов в начале, в конце и в середине: Как правильно вставить элемент прямо в середину std::list? Может быть, это?

  std::list<int> l;
  l.push_back(10);
  l.push_back(20);
  l.push_back(30);
  l.push_back(40);
  l.push_back(50);
  l.push_back(60);
  l.insert( l.end()- l.begin() /2 ); //? is this 
  // inserting directly in the middle?

Когда мы говорим «вставка в середину», мы действительно подразумеваем, что мы экономим линейное время, чтобы перейти от начала списка к желаемой точке (обходя один за другим через все связанные элементы между ними)?

Answer 1

Вы можете сделать математику итератора в общем, как это:

 std::list<int>::iterator it = l.begin();
 std::advance(it, std::distance(l.begin(), l.end())/2);
 l.insert(it, value);

Это будет работать для любого типа итератора (кроме OutputIterator или InputIterator)

Конечно, гораздо эффективнее сказать

 std::advance(it, l.size()/2);
 l.insert(it, value);

К сожалению, l.insert(l.begin + (l.size()/2), value) не будет работать, потому что итераторы списков не являются произвольным доступом, поэтому не определено operator+ (чтобы избежать неожиданностей в производительности!). Помните, что std::advance() может быть дорогостоящей операцией в зависимости от типа итератора (она будет медленной для обратных итераторов , реализованных в контейнере только для пересылки, например).

Answer 2

Здесь «середина» означает произвольную точку в списке, если у вас уже есть итератор, ссылающийся на эту точку.Учитывая это, вставка - это просто вопрос изменения нескольких указателей вокруг точки вставки.

Если у вас еще нет итератора для точки вставки, и он не где-то просто, как начало иликонец, затем потребуется линейное время, чтобы пройти по списку, чтобы найти его.

Answer 3

Вставка в «середину» списка означает вставку куда-то, кроме начала или конца.Но для выполнения вставки требуется итератор до точки вставки.Если у вас есть такой итератор, время вставки остается постоянным, но получение такого итератора в первую очередь является отдельной проблемой.

Answer 4

Нет, когда мы говорим «вставка посередине», мы не подразумеваем «нахождение точки вставки в соответствии с какими-либо критериями, которые принимают пересечение всей или неопределенной части списка».

Answer 5

Когда мы говорим «вставка в середину», мы действительно подразумеваем, что мы экономим линейное время, чтобы перейти от начала списка к желаемой точке (обходя один за другим через все связанные элементы между ними)?

Да.
По сути, это означает, что список должен просто изменить указатели, чтобы вставить новый элемент, а не перемещаться по всему списку или копировать содержимое и т. Д. Поэтому вставка выполняется с постоянным временем, потому что нет необходимости обходить список или копировать контейнеры и т. Д.