Find в списке, когда указаны начало и конец

[Сионист]

Линейный список имеет три перегруженные версии члена-функции Find. Одна ищет по всему списку, одна от указанного элемента до конца списка и одна между двумя указанными элементами, включая оба. Интересует именно эта третья версия. Надо ли делать проверку порядка указанных элементов, то есть защиту от дурака, который задаст поиск вперёд от одного элемента до другого, предшествующего ему?

[Romeo]

Обычно таких проверок не делают. Сам передал - сам дурак.

И, кстати, "включая оба" - это неправильная практика в C++. Тут принято последний не включать. По очень многим причинам это удобнее.

А попробовать срастить свой список с std::find не хочешь? Просто ради интереса.

[Сионист]

И, кстати, "включая оба" - это неправильная практика в C++. Тут принято последний не включать. По очень многим причинам это удобнее.

Почему? По-нерусски же получится.

Обычно таких проверок не делают. Сам передал - сам дурак.

То есть если иттератор To адресует элемент, предшествующий элементу, адресуемому итератором From, то надо искать до конца списка, несмотря на приём двух итераторов? А в массиве также? Или там проверку делать?

[Romeo]

Почему? По-нерусски же получится.

Оно и не должно быть по-русски. Мы на другом языке пишем. Он называется С++.

На самом деле тебе это странным кажется только потому, что у тебя не хватает опыта. Если ты немного поразмыслишь над этим, то поймёшь, что это очень логично из-за самой сути С-шной индексации.

Как мы объявляем С-массив и как проходим по нему? В объявлении мы пишем N в квадратных скобках, но при этом индексы у элементов будут от 0 до N-1, верно? Иными словами до N не включая. А общепринятым обходом цикла считается цикл от 0 до N, тоже не включая. Видишь закономерность? Причём разность, вычисленная из значений границ этого интервала, даёт точную сумму элементов массива. Без всяких "плюс один" или "минус один". Это, действительно, очень логично и удобно.

Когда появился С++, то этот общепринятый подход перенесли и на итераторы. Обращал внимание, как обычно выглядят все циклы для итераторов? Всегда begin() включается в процессинг, а end() не включается.

Код: Выделить всё

for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it)
{
   // do something with *(it)
}

Все контейнера работают именно так. И все алгоритмы из <algorithm> тоже. То есть, по сути, такой подход стал стандартным уже с первой версии С++. В новом же стандарте С++11, ко всему прочему появилась range based форма for. Если программист захочет, чтобы самописный контейнер поддерживал эту форму for, то от правила "интервал, не включающий правую границу" уже никак нельзя будет отвертеться.

То есть если иттератор To адресует элемент, предшествующий элементу, адресуемому итератором From, то надо искать до конца списка, несмотря на приём двух итераторов? А в массиве также? Или там проверку делать?

Если ты откроешь <algorithm> и посмотришь, как реализован find, то увидишь, что там просто делается цикл от begin до end (не включая) и проверяется равен ли текущий элемент заданному или нет. Никаких дополнительных хитрых проверок. То, что два переданных в функцию итератора находятся на своих местах, является инвариантом функции. То есть это требование, которое функция накладывает на вызывающий код, и если вызывающий код не выполняет его, то он сам в этом виноват. Мне такой подход нравится. Если нравится и тебе - то бери и используй.

[Сионист]

Оно и не должно быть по-русски. Мы на другом языке пишем. Он называется С++.

Когда коллеги спросили одного мелкомягкого, почему его код выглядит так странно, он ответил, что это потому, что он написан по-венгерски. Писал он на c.

Если ты немного поразмыслишь над этим, то поймёшь, что это очень логично из-за самой сути С-шной индексации.

Язык одинаково допускает и

Код: Выделить всё

for (i=0; i<n; ++i)

и

Код: Выделить всё

for (i=0; i<=last; ++i)

. Ни каких проблем с индесацией это не вызывает.

Как мы объявляем С-массив и как проходим по нему? В объявлении мы пишем N в квадратных скобках, но при этом индексы у элементов будут от 0 до N-1, верно? Иными словами до N не включая.

Нет. От 0, всего N. Это количество, а не индекс.

А общепринятым обходом цикла считается цикл от 0 до N, тоже не включая.

Вот только итератор соответствует указателю. Как перебирают по указателю?

Код: Выделить всё

for (p=a+n-1; p>=a; --p)

, то есть есть и -1, и включение границы. Это когда направление не имеет значения, либо требуется перебрать именно с конца к началу.

[Romeo]

Язык одинаково допускает и
Ни каких проблем с индексацией это не вызывает.

Я же не сказал, что это был единственный способ обхода. Да, были упорные паскалевцы, которые из-зо всех сил пытались оставаться в родной среде и писали циклы на ( i <= N-1 ). Я лишь сказал, что циклы до N не включая были общепринятыми среди настоящих С разработчиков. Студентики, которые ещё вчера писали на Паскале лабораторки - не в счёт. И логика в таком подходе действительно была. А после появления С++, это вообще стало стандартом, так как на этом принципе стали работать итераторы и алгоритмы из STL.

Нет. От 0, всего N. Это количество, а не индекс.

Верно, N - это количество. А я про индекс писал. Не передёргивай. Ты ведь отлично понял, о чём идёт речь.

Вот только итератор соответствует указателю. Как перебирают по указателю?

Код: Выделить всё

for (p=a+n-1; p>=a; --p)

, то есть есть и -1, и включение границы. Это когда направление не имеет значения, либо требуется перебрать именно с конца к началу.

У меня с трудом получается понять, о чём ты сейчас пытаешься спорить. Очень скомкано пишешь. Если что, для обратного прохода есть reverse iterator, который делает код таким же красивым, как и для forward итератора при прямом проходе, но, при этом, тоже использует открытый с одной стороны интервал.

Ты можешь более явно объяснить сейчас цель твоего спора? Так как я пока не могу понять этой цели, да и аргументы какие-то невнятные. Тебе не нравится, как спроектирован STL? Хорошо, пиши свой. Но, поверь, над созданием STL работали десятки людей, куда более умных, чем ты или я. Так что его принципы нужно, как минимум, внимательно проанализировать и взвесить все плюсы и минусы, даже если они с первого взгляда тебе покажутся нелогичными. Велика вероятность того, что после анализа ты признаешь, твоя первая оценка была ошибочной.

Да и вообще, почему я пытаюсь быть максимально корректным? Чёрт побери, да для меня настоящая дикость то, что человек писал 15 лет на языке, но при этом не использовал STL совсем, а разобраться, что же такое итераторы решил только сейчас! Неужели ты думаешь, что этот факт тебя красит? Ты понимаешь, что все эти 15 лет ты вместо того, чтобы заниматься реальным программированием, изобретал велосипеды?

[Сионист]

Да, были упорные паскалевцы

пасквилянты.

которые из-зо всех сил пытались оставаться в родной среде и писали циклы на ( i <= N-1 ).

А вот за это надо посылать в библиотеку с заданием прочитать 5 книг, посвящённых оптимизации: вычитание на каждом шагу. Я же имел ввиду вариант, когда индекс границ уже дан в явном виде. N - это количество, а не индекс. А если

Код: Выделить всё

int a[N];
size_t i;
size_t f;
size_t l;
for (i=0; i<N; ++i)
{
 std::cout<"a["<<i<<"]="; cin>>a[i];
}
std::cout<<"Введите инекс первого удваиваемого элемента"; std::cin>>f;
std::cout<<"Введите инекс последнего удваиваемого элемента"; std::cin>>l;
for (i=f; i<=l; ++i)
{
 a[i]*=2;
}
for (i=0; i<n; ++i)
{
 std::cout<<"a["<<i<<"]="<<a[i]<<std::cout;
}

, то +1 требуется уже для того, чтоб не включить правую границу, любо надо долго и нудно объяснять пользователю, которого не спроста дразнят конченным юзверем, что второй индекс должен быть не последнего удваиваемого элемента, а следующего за ним и он всё равно раз сорок перепутает. Два итератора в фаинде - это именно такой случай.

Верно, N - это количество. А я про индекс писал. Не передёргивай. Ты ведь отлично понял, о чём идёт речь.

Ты писал про N, а это количество.

У меня с трудом получается понять, о чём ты сейчас пытаешься спорить. Очень скомкано пишешь. Если что, для обратного прохода есть reverse iterator, который делает код таким же красивым, как и для forward итератора при прямом проходе, но, при этом, тоже использует открытый с одной стороны интервал.

Речь не о синтаксисе цикла с реверсивным итератором. Речь о том, что включается в диапазон, когда используются адреса обеих границ, а не признак завершённости перебора. Член end() ведь не адрес возвращает, а значение признака. Простейший перебор на адресной арифметике включает границу и в явном виде вычитает единицу.

Ты понимаешь, что все эти 15 лет ты вместо того, чтобы заниматься реальным программированием, изобретал велосипеды?

Как раз велосипедами я не занимался. Велосипедю я только сейчас. И с единственной целью - понять, как писать итераторы нестандартных контейнеров и поиск в них. Стловый "вектор" я вообще не понимаю, куда приткнуть, ограниченный массив Герберта Шилдта лучше. map ещё на что то похож, но слишком уж ограничен, одного ключа для каждого значения мало. Очередь вроде хороша. Только почему то в списке не видно ни стека, ни дерева, даже двоичного. А если понадобится коряга ещё позаковырестей? Или массиво-список (массив, каждый элемент которого "знает" обоих соседей)? Трёхмерный массив на пересекающихся списках?

[Romeo]

А вот за это надо посылать в библиотеку с заданием прочитать 5 книг, посвящённых оптимизации: вычитание на каждом шагу.

Если N - это define или константа, то вычитания на каждом шаге не будет, так как это будет соптимизировано на этапе компиляции. Более того, даже если это переменная, всё равно компилятор проведёт оптимизацию. Оптимизации не будет только в том случае, если вместо N будет стоять результат вызова функции. Да и вообще, не в этом была суть поста, а в том, чтобы указать, что были фанатики Паскаля, использующие <= наперекор принятой практике.

Я же имел ввиду вариант, когда индекс границ уже дан в явном виде

Ты правда считаешь, что я пытаюсь тебе доказать, что все циклы нужно писать, используя исключительно "<" ? Ну ты либо наивен, либо троллишь меня. Третьего не дано.

Ещё раз. Мой пример был об обходе обычного массива в направлении роста значения счётчика. Практика использования открытого справа интервала в таких случаях даёт множество удобств. Вот некоторые из них:

- Если идёт полный перебор массива, и N - это количество элементов, то не нужно писать конструкцию N-1 в проверке на выход.

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

- Разность между границами интервала численно равно количеству элементов в этом интервале (снова не нужно коррекция на 1).

Ты писал про N, а это количество.

Ты знаком с математическими обозначениями? Элементы имеют индексы 0, 1, 2, и так далее. Последний имеет какой индекс? N-1. А следующий элемент, который уже не входит в массив, имеет индекс N. Так что N может быть как количеством, так и значением индекса. Эти передёргивания контекста я считаю глупыми вдвойне, так как мы оба понимаем, о чём идёт речь, но ты всё равно продолжаешь спорить, видимо ради самого процесса.

Простейший перебор на адресной арифметике включает границу и в явном виде вычитает единицу

Не обязательно. По подобию с индексным перебором и с итераторами, можно делать перебор не включая правую границу:

Код: Выделить всё

const int N = 10;
int arr[N];

int* begin = arr;
int* end = arr + N;

for (int* cur = begin; cur != end; ++cur)
{
...
}

Как видишь, ни одной коррекции на единицу. В твоём же случае пришлось бы сделать минимум одну коррекцию.

А конец моего предыдущего сообщения ты прочёл? Ты мне можешь сказать в чём смысл спора, который ты сейчас ведёшь или нет?

[Сионист]

Ещё раз. Мой пример был об обходе обычного массива в направлении роста значения счётчика. Практика использования открытого справа интервала в таких случаях даёт множество удобств. Вот некоторый из них: - Если идёт полный перебор массива,

Для этого предназначена версия без параметров-итераторов.

и N - это количество элементов, то не нужно писать конструкцию N-1 в проверке на выход.

Дан итератор, то есть сама граница в явном виде, а не количество элементов.

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

Вот только если уж надо перебрать кусками, то они врядли так просто связаны. Перебор первой и третьей четвертей массива, или один кусок - первые две трети, а второй - две последние трети. Даже если куски следуют подряд, то лишь случайно, так как перебираются в независимых задачах и факт непосредственного следования второго куска за первым надо ещё проверять отдельным ифом. Тем более поиск. Он ведь возвращает итератор найденного элемента. Если он вернёт итератор следующего элемента, то надо будет городить ещё один цикл, чтоб отступить назад, а чтоб искать следующее вхождение в любом случае надо не включить как раз левую границу, взяв за неё предыдущее возвращённое значение:

Код: Выделить всё

for (Iterator=List.Find(4); Iteratot!=List.End(); Iterator=List.Find(++Iterator, 4))
{
 *Iterator=67;
}

.

[Romeo]

Я упорно не понимаю, почему ты продолжаешь спорить, и ты мне никак не ответишь на этот вопрос. Я все аргументы выложил. Если они не кажутся тебе логичными - делай по-своему. Дальнейшее обсуждение считаю бессмысленным.