Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.69/16: Рейтинг темы: голосов - 16, средняя оценка - 4.69
5 / 5 / 1
Регистрация: 15.12.2015
Сообщений: 51
1

Почему итераторы в STL используют такой странный подход к индексации?

20.08.2019, 17:00. Показов 3184. Ответов 23
Метки нет (Все метки)

Здравствуйте. Вопросы касаются пока только последовательных контейнеров.

Почему при инициализации контейнера массивом из, например, 5 элементов, мы прибавляем к адресу массива во втором аргументе не 4, а 5? В первом аргументе содержится адрес первого элемента, сдвинулись 4 раза = получили все остальные, включая последний. Зачем делать ещё один лишний сдвиг и заходить за диапазон? Это касается и метода контейнера .end(), который возвращает значение итератора "последний элемент + 1".
1

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

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.08.2019, 17:00
Ответы с готовыми решениями:

Почему создатели языка C++ придумали такой странный синтаксис обращения к элементам одномерного массива?
К элементам массива можно обращаться разными способами. Обычно в квадратных скобках пишут номер...

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

STL. Итераторы и последовательные контейнеры
Немогу решить эти задачки: 1 Написать экземпляр класса queue на основе элементов типа string. ...

Итераторы потокового ввода/вывода stl
Возник такой вопрос при изучении stl. Берем файл, из которого нужно считать данные, через copy...

23
зомбяк
1533 / 1178 / 332
Регистрация: 14.05.2017
Сообщений: 3,824
20.08.2019, 17:18 2
Лучший ответ Сообщение было отмечено Марауль как решение

Решение

Цитата Сообщение от Марауль Посмотреть сообщение
Это касается и метода контейнера .end()
Этот итератор возвращает значение "вне диапазона контейнера".
Цитата Сообщение от Марауль Посмотреть сообщение
мы прибавляем к адресу массива во втором аргументе не 4, а 5
Потому что указывается конец 5го элемента. Да, он является началом (смещением к ) 6го элемента, которого в массиве нет и к которому обращаться нельзя. Но концом 5го он не перестаёт быть.
1
6738 / 4537 / 1839
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
20.08.2019, 17:29 3
Цитата Сообщение от Марауль Посмотреть сообщение
В первом аргументе содержится адрес первого элемента, сдвинулись 4 раза = получили все остальные, включая последний. Зачем делать ещё один лишний сдвиг и заходить за диапазон?
Ты в любом случае "сдвигаешься" пять раз, чтобы выполнилось условие выхода из цикла
C++
1
2
3
4
5
6
std::vector<int> arr{5};
size_t i = 0;
for (; i < arr.size(); ++i)
    std::cout << i << std::endl;
 
std::cout << i << std::endl; //i == 5
1
С чаем беда...
Эксперт CЭксперт С++
9156 / 4674 / 1269
Регистрация: 18.10.2014
Сообщений: 10,572
20.08.2019, 17:34 4
Лучший ответ Сообщение было отмечено Марауль как решение

Решение

Цитата Сообщение от Марауль Посмотреть сообщение
Почему при инициализации контейнера массивом из, например, 5 элементов, мы прибавляем к адресу массива во втором аргументе не 4, а 5?
В языке С++ для представления диапазонов используется подход [a, b), т.е. с включением левого края диапазона и исключением правого края диапазона. Такой подход во многих отношениях весьма удобен и естественен. В частности, весьма удобно то, что конец предыдущего диапазона одновременно является началом следующего за ним диапазона. Также есть естественная возможность представления пустых диапазонов: [a, a).
1
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,275
Записей в блоге: 16
20.08.2019, 19:09 5
Марауль, так решил Создатель. Существует ряд подходов к хранению информации о размере. Можно хранить специальное поле, например. В этом случае для возврата итератора в ничто достаточно было бы статического объекта "ничто". То есть, когда поиск возвращает такой итератор то он не удался. Недостатком является невозможность декремента такого итератора.
Но и издержки достаточно велики (имхо). Больше всех досталось спискам. Список - король алгоритма. А в С++ он не является полноценно рекурсивным контейнером. Если бы размер присутствовал как поле экземпляра, то любой поддиапазон списка (валидный, конечно) мог бы быть реализован как полноценный список. Проблемы с равными адресами (при неравных размерах) можно бы решить. Но решили по другому. Ещё хуже то, что список получает свой размер от функции члена size() проходя по всему списку и считая элементы, в большинстве реализаций. Это касается и linked и двусвязного списка.
О преимуществах разделения на диапазоны, работы с итераторами для указания позиции вставки/удаления и пр. уже сказано и свой смысл в принятом подходе есть, безусловно.
То, что вы задаёте такой вопрос, это хорошо.
1
С чаем беда...
Эксперт CЭксперт С++
9156 / 4674 / 1269
Регистрация: 18.10.2014
Сообщений: 10,572
20.08.2019, 19:29 6
Цитата Сообщение от IGPIGP Посмотреть сообщение
Но и издержки достаточно велики (имхо). Больше всех досталось спискам. Список - король алгоритма. А в С++ он не является полноценно рекурсивным контейнером. Если бы размер присутствовал как поле экземпляра, то любой поддиапазон списка (валидный, конечно) мог бы быть реализован как полноценный список. Проблемы с равными адресами (при неравных размерах) можно бы решить. Но решили по другому. Ещё хуже то, что список получает свой размер от функции члена size() проходя по всему списку и считая элементы, в большинстве реализаций. Это касается и linked и двусвязного списка.
Вы о чем вообще? Стандарт C++11 уже требует, чтобы размер std::list хранился внутри объекта контейнера (т.е. в виде поля или еще как). Функции-члену size() больше не разрешается ни по чему "проходить" - она обязана отрабатывать мгновенно, за O(1). То есть дилемма о том, хранить или не хранить размер std::list наконец разрешилась раз и навсегда: да, хранить.

Вот только не ясно, как это все вообще относится к исходному вопросу.
1
749 / 352 / 72
Регистрация: 10.06.2014
Сообщений: 2,371
20.08.2019, 19:44 7
TheCalligrapher,
Так себе решение... Может мне вовсе не нужен сайз, почему я должен "платить" за это...
А кому нужен сайз за О(1), может сделать простую обёртку или чтоб стандарт такую предоставил...
Теперь те, кому не нужен сайз за О(1), точнее те, кто не хочет за это "платить", должны реализовать свой список а это сложнее чем реализация обёртки с сайзом за О(1)...
0
С чаем беда...
Эксперт CЭксперт С++
9156 / 4674 / 1269
Регистрация: 18.10.2014
Сообщений: 10,572
20.08.2019, 19:52 8
Цитата Сообщение от Undisputed Посмотреть сообщение
Так себе решение... Может мне вовсе не нужен сайз, почему я должен "платить" за это...
Стандартные контейнеры обязаны предоставлять size(), точка. А нужен он вам или не нужен - дело отдельное. Если для вас это критично, значит вам не подходят стандартные контейнеры.

Дилемма о хранении или не хранении размера - это дилемма о том, что важнее в практических применениях: эффективность size() или эффективность splice(). Авторы этого решения, очевидно, не монетку кидали, а все таки опирались на реальный накопленный к этому моменту опыт, на основе которого и было принято решение в пользу эффективного size().

Я понимаю полезность и элегантность splice(), но согласен с тем, что используется эта функция действительно редко.
1
749 / 352 / 72
Регистрация: 10.06.2014
Сообщений: 2,371
20.08.2019, 20:05 9
TheCalligrapher,
Я не против сайза вообще, но можно было бы оставить его за O(n)...
Конкретно в данном случае речь о добавлении/удалении элементов. Счётчик же придётся крутить, а это дополнительные операции... Иначе как сайз то формировать

Добавлено через 1 минуту
А там кому надо за О(1) напишет простую обёртку над стандартным списком...

Добавлено через 1 минуту
И память лишнюю придётся тратить под счётчик даже если он не нужен... То С++ это "плати только за то что используешь", то "мы тут порешали, что все равно будешь переплачивать"
0
С чаем беда...
Эксперт CЭксперт С++
9156 / 4674 / 1269
Регистрация: 18.10.2014
Сообщений: 10,572
20.08.2019, 20:17 10
Цитата Сообщение от Undisputed Посмотреть сообщение
Конкретно в данном случае речь о добавлении/удалении элементов. Счётчик же придётся крутить, а это дополнительные операции... Иначе как сайз то формировать
Операции и память, необходимые для "кручения счетчика" при добавлении единичных элементов никого не беспокоят и никакой роли не играют. В стандартном контейнере и так расходуется столько операции и памяти, что дополнительный счетчик никакой погоды не сделает. Все это уже давным-давно исключено из рассмотрения в С++.

Страдает от этого решения, как я сказал выше, только функция splice(), которая перестает быть O(1).
3
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,275
Записей в блоге: 16
20.08.2019, 20:50 11
Цитата Сообщение от Undisputed Посмотреть сообщение
Может мне вовсе не нужен сайз, почему я должен "платить" за это...
Список без этой функции (быстрой реализации) - УГ. Я рад, что наконец-то стандарт требует человеческого отношения. В целом, непротиворечивого решения тут нет. Но компромисс с нормальной функцией size() мне нравится больше. Тут конечно нужно поддерживать всеми операциями изменяющими размер, но оно того стоит. И это, кстати, отличный пример того, когда ленивые вычисления не рулят. Всё хорошо в меру.
Другой вопрос, что можно бы задавать размер без элемента за последним элементом. В данном случае в этом уже нет необходимости. Я думаю, тут играет роль инерция мысли от с-строк. Ноль терминатор и приёмы работы (итераций в основном) уже стали привычны.
1
Undisputed
20.08.2019, 22:31
  #12

Не по теме:

Не согласен. Было бы лучше дать выбор пользователю как например в векторе при доступе к элементам.
Хочешь быстро но с риском словить UB? Используй оператор [], иначе более безопасный но медленный at.
А тут как то топорно поступили. Если гибче это ведь лучше для конечного пользователя.

Кроме навязывания лишних операций (да, они простые но их нельзя назвать бесплатными) как уже говорил это доп. память, и это не просто доп. место в памяти, это так же может привести к тому что например массив списков определённого размера не будет вмешаться в кеш линию, хотя без счетчика спокойно вместился бы.

0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,275
Записей в блоге: 16
20.08.2019, 22:52 13
Цитата Сообщение от Undisputed Посмотреть сообщение
хотя без счетчика спокойно вместился бы
Одна слеза ребёнка может прожечь в этом мире дыру величиной с галактику. Undisputed, память для счётчика не проблема в списке. Список вообще враг кеша. Его рядом стоящие (по итерации) элементы могут лежать в разных мирах. Проблема скорее в том, что счётчик нужно обслуживать при каждой операции добавления/вставки/удаления и пр. А что касается навязывания, то велосипед без колёс не слишком хороший выбор. Список размером мегабайт, который считает размер так, как это было мне известно (спасибо TheCalligrapher, - за хорошую новость для меня), это не хорошо. Я хотел бы, чтобы комитет пошёл дальше. Ведь если контейнер должен
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Стандартные контейнеры обязаны предоставлять size(), точка.
То осталось добавить поля с размером в итератор (и текущую позицию) и -кайф! Ведь всё равно нельзя создать итератор без ссылки на контейнер.
Впрочем, последние сентенции могут быть дороговаты и я не настаиваю. Просто фантазия)
1
749 / 352 / 72
Регистрация: 10.06.2014
Сообщений: 2,371
20.08.2019, 23:09 14
IGPIGP,
Я не говорил про то как хранятся ноды списка а про то как сами списки могут храниться. К тому же ваше утверждение не так однозначно. Память под ноды можно выделять из пула, в котором ноды будут сидеть друг рядом с другом... Для списков фиксированного размера самое то.
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,275
Записей в блоге: 16
20.08.2019, 23:17 15
Цитата Сообщение от Undisputed Посмотреть сообщение
Я не говорил про то как хранятся ноды списка а про то как сами списки могут храниться.
Для меня это логически несовместные слова. Если под списком иметь ввиду ссылку, то говорить не очем в данном контексте.
Цитата Сообщение от Undisputed Посмотреть сообщение
Память под ноды можно выделять из пула
Кастомный аллокатор имеете ввиду? Его же тоже нужно обслужить. Думаете это ни чего не стоит?
Undisputed, я понимаю, что вы имеете ввиду. Предложить старую и новую реализации как разные контейнеры? Это дороже в плане поддержки для разработчиков библиотеки. Но я не против. Свобода, - самоценная штука.
0
749 / 352 / 72
Регистрация: 10.06.2014
Сообщений: 2,371
20.08.2019, 23:37 16
IGPIGP,
Если вы будете переходить из одного элемента (списка) к другому в цикле и скажем проверять не пуст ли он, то что лучше, если все эти списки (ссылки как вы выразились) будут в кеше или нет? Вопрос риторический...

IGPIGP,
Обслужить выделение из пула памяти значительно дешевле чем обслужить системный вызов...

Да ладно, не особо дороже поддерживать. Старая версия есть, новая тоже. Можно было и разделить. Целый компилятор написали, с копипастой что ли не справятся? Ну вот о гибкости и речь. Мне просто не понятна такая избирательность, где то предлагают варианты на выбор в плане гибкости а где то нет, хотя сделать это не так сложно
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,275
Записей в блоге: 16
21.08.2019, 01:32 17
Цитата Сообщение от Undisputed Посмотреть сообщение
то что лучше, если все эти списки (ссылки как вы выразились) будут в кеше или нет?
Сам список как и любой контейнер, - вектор например, это ссылка. А элементы, это другое. Я говорил о том, что счётчик не создаст проблем с кешем, скорее всего. Он создаётся с экземпляром и надежда, что он хранится где-то рядом с адресом (ссылкой на сам список как объект) контейнера и, возможно, даже с первым элементом имеет право на жизнь. А вот сами ноды - элементы списка аллоцируются произвольно (в общем случае). То есть, счётчик не проблема для дружбы с кэшем.
Цитата Сообщение от Undisputed Посмотреть сообщение
IGPIGP,
Обслужить выделение из пула памяти значительно дешевле чем обслужить системный вызов...
Я говорил о сравнении цены обслуживания счетчика. Вы же за это не хотите платить? Сравнивать аллокацию по умолчанию с кастомной, это неблагодарное занятие. Особенно в контексте работы функции size(). Это просто отдельная тема. И было бы славно увидеть хорошие примеры кастомной аллокации. Тут уже были вопросы от участников, так что тема была бы интересной.
Цитата Сообщение от Undisputed Посмотреть сообщение
Можно было и разделить.
Я уже написал, что не против различных реализаций.
Однако список как контейнер легко разделяемый на подконтейнеры был бы очень полезен. Можно было бы индексировать список частями (как группу списков) и получать выгоды в скорости доступа. Вот тут есть трехуровневый монстрик, решающий такую задачу:
https://www.cyberforum.ru/blog... g4772.html
0
С чаем беда...
Эксперт CЭксперт С++
9156 / 4674 / 1269
Регистрация: 18.10.2014
Сообщений: 10,572
21.08.2019, 01:40 18
Цитата Сообщение от IGPIGP Посмотреть сообщение
(спасибо TheCalligrapher, - за хорошую новость для меня
Тут еще не все копья сломаны. (Я уже писал об этом ранее, кажется.). Реализация стандартной библиотеки GNU изначально было подчинилась требованию стандарта и перешла на хранимый размер (раньше у них size() вычислялся). Но потом они обнаружили проблемы с бинарной совместимостью своих библиотек и откатили все взад. В данных момент GNU отказывается следовать требованиям стандарта языка и упорно держится руками и ногами за вычисляемый size(). Как бы не получилось так, что комитет сдастся и вернет все обратно...
1
Эксперт С++
8427 / 4100 / 894
Регистрация: 15.11.2014
Сообщений: 9,213
21.08.2019, 02:32 19
Цитата Сообщение от Undisputed Посмотреть сообщение
более безопасный но медленный at.
бесполезный.
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,275
Записей в блоге: 16
21.08.2019, 09:54 20
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Тут еще не все копья сломаны.
А я то думаю, - "Не уж-то я так от жизни отстал?" Хотя лучше бы отстал. Ну что же.. Будем надеяться на лучшее.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.08.2019, 09:54

STL. Не работает вывод через << в поток когда использую итераторы :(
Вроде бы ничего сложного, но почему-то работать не хочет. Никак не могу понять почему ( Ругается,...

Найти элемент в контейнере priority_queue, используя STL вские итераторы и алгоритмы
Здравствуйте, задача описана в навание темы. Можно перебрать в цикле все элементы очереди,...

Можно ли использовать такой подход в классах?
Подскажите пожалуйста. Можно ли в конструкторе класса В, создавать объект другого класса А и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.