0

Как можно, не используя итератор begin() и end(), двигаться в списке? Нужно просто next. Судя по описанию, то там нет просто next() итератора.
Как можно с центра списка передвинуться дальше?

Вот нашел по теме ответ с использованием массива и функции sizeof, только вот не получается применить пока.

На примере, что хочу.

list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);

Нужно вывести со второго.

5
  • Есть ещё rbegin и rend:) плюс есть куча алгоритмов, которые позволяют перебирать элемены контейнера без явного использования итераторов.
    – KoVadim
    26 ноя 2014 в 16:46
  • rbegin и rend - это все заставляет задействовать начало или конец. Получается, перейти просто к следующему никак?
    – TheStigger
    26 ноя 2014 в 16:58
  • Надо размер листа (l.size()) поделить пополам - так вы найдете центр и потом отступить от него, сколько вам нужно. И делаеться это обычно с помощью итератора (list<int>::iterator).
    – perfect
    26 ноя 2014 в 17:17
  • А теперь такой поворот: мне нужно реализовать скип-список с помощью STL. Когда я спускаюсь на 1 уровень, я просто нахожусь на позиции некоторого элемента (возможно, слева где-то, может, по центру, а может, и справа). Т.е. есть ссылка. Перехожу по ней. Далее нужно двигаться дальше по списку, не зная точной позиции.
    – TheStigger
    26 ноя 2014 в 17:32
  • next, prev нет, зато у многих итераторов есть инкремент / декремент 11 мая 2018 в 0:48

2 ответа 2

2

С++11 позволяет следующее:

for (auto& element : elements)
{
//    element делать что-то
}

Где elements - любой контейнер, поддерживающий как раз методы begin() и end(). Т.е. использование их в неявном виде все равно имеет место.

А вообще не понятно, речь идет о синтаксисе, или какой-то урезанной реализации std::list, у которой нет begin() и end(), у нее должен быть другой способ установить итератор в начало и конец...

Если это вопрос с собеседования (а абсурдность его наводит на такую мысль), то, наверное, они пытались выяснить, насколько хорошо Вы знаете внутреннее устройство контейнера, и, возможно, знаете, где точно в памяти будет располагаться первый элемент, и сможете проинициализировать итератор таким образом, а дальше уже двигать его через operator++. Возможно :) В таком случае, имхо, правильный ответ: реализации STL бывают разные, это является большой проблемой совместимости, например, экспорта данных между разными библиотеками, но Вы предполагаете, что очевидная реализация связного списка - где сам список и есть первый элемент + служебная информация (указатель на последний элемент, длина, какие-то еще данные/методы). Или получить информацию о первом и последнем элементе можно в "служебной информации", которая и будет представлять собой объект list.

5
  • Глобальная цель - реализация скип списка, но именно с использованием stl. Суть заключается в том, что, проходя по верхнему уровню, програма быстрее дойдет до нужного.
    – TheStigger
    26 ноя 2014 в 16:55
  • @theStigger, если у Вас есть итератор, то переход к следующему элементу через оператор++
    – Arkady
    26 ноя 2014 в 17:01
  • @TheStigger1, а чем это (github.com/petegoodliffe/skip_list), или множество других готовых реализаций не устраивают?)
    – Arkady
    26 ноя 2014 в 17:02
  • Судя по описанию, я так понял, что это не "скип список, реализованный с помощью stl", а "скип список как stl".
    – TheStigger
    26 ноя 2014 в 17:07
  • @TheStigger1, в Интернете полно реализаций, многие из них так или иначе используют STL. И реализация по ссылке использует STL.
    – Arkady
    27 ноя 2014 в 9:47
2

Функция advance

1
  • Но будьте предельно внимательны. Использование std::advance может негативно сказаться на производительности вашей программы. Конкретнее - она предназначена для работы с контейнерами, которые имеют итератор произвольного доступа (вектор, дек). Как известно двунаправленный список std::list таких итераторов не содержит и вызов std::advance будет занимать линейное время от к-во айтемов O(N) 25 сен 2016 в 14:52

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.