алгоритм std::remove_copy_if()

@Ingeniger · Регистрация: 19.04.2016

Студворк — интернет-сервис помощи студентам

Всем привет!

В документации сказано, что исходный и целевой диапазоны не должны пересекаться.
https://ru.cppreference.com/w/... emove_copy
Однако у Джосьютиса в книге по STL приводится реализация другого алгоритма remove_if(), использующая в своем теле алгоритм -сабж remove_copy_if() . В этой реализации remove_copy_if() использован с перекрывающимися диапазонами

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class ForwIter, class Predicate>
ForwIter std::remove_if(ForwIter beg, ForwIter end,
                                    Predicate op)
{
      beg = find_if(beg, end, op)
      if(beg == end)
                return beg;
      else {
             ForwIter next = beg;
             return remove_copy_if(++next, end, beg, op);          //конкретно здесь вызывется 
      }                                                                                    // remove_copy_if() для перекрывающихся 
                                                                                          // диапазонов
}

Так где ошибка? Реализация Джойстиса, судя по всему верна, т.к. особенности поведения remove_copy(), которые он объяснял такой реализацией, дейтвительно есть.
Спасибо.

@avgoor · 23.04.2020, 23:58

Ingeniger, реализаций может быть много. Если написано, что не должны пересекаться - значит не должны. В какой-то реализации прокатит, но при смене компилятора будет фэйл.

@Ingeniger · 24.04.2020, 00:05 **[ТС]**

Сообщение от avgoor

Ingeniger, реализаций может быть много. Если написано, что не должны пересекаться - значит не должны. В какой-то реализации прокатит, но при смене компилятора будет фэйл.

То есть в такой популярной книге по STL могут быть такие грубые ошибки?
Это ведь не первая редакция.

@TheCalligrapher · 24.04.2020, 00:08

Сообщение от Ingeniger

Однако у Джосьютиса в книге по STL приводится реализация другого алгоритма remove_if(), использующая в своем теле алгоритм -сабж remove_copy_if() . В этой реализации remove_copy_if() использован с перекрывающимися диапазонами

Реализация стандартной библиотеки написана не на языке С++ и не подчиняется ограничениями, правилам и требованиям языка С++ и стандартной библиотеки С++.

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

Вам же - клиенту стандартной библиотеки - этого не дозволяется.

Сообщение от Ingeniger

То есть в такой популярной книге по STL могут быть такие грубые ошибки?

В этом нет никакой ошибки, пока речь идет именно о реализации стандартной библиотеки.

@avgoor · 24.04.2020, 00:10

Ingeniger, почему ошибка? Он приводит пример реализации. Она соответствует требованиям? Соответствует. А то, что она работает даже с перекрывающимися диапазонами (верю вам на слово, не читал)... ну так замечательно. В другой реализации может быть не так.

@S_el · 24.04.2020, 00:10

Ingeniger, это не ошибка, итератор beg не находится в диапазоне [++next, end), он установлен левее, на next, так что все в порядке.

@TheCalligrapher · 24.04.2020, 00:12

Сообщение от S_el

это не ошибка, итератор beg не находится в диапазоне [++next, end), он установлен левее, на next, так что все в порядке.

Вы о чем вообще? Требования алгоритма remove_copy_if накладываются на диапазоны, а не на итераторы. И диапазоны в данном случае перекрываются, что не допускается remove_copy_if. То есть с точки зрения клиентского кода ошибка тут есть.

@avgoor · 24.04.2020, 00:16

Сообщение от TheCalligrapher

не подчиняется ограничениями, правилам и требованиям языка С++ и стандартной библиотеки С++.

Это да, но про это:

Сообщение от TheCalligrapher

Реализация стандартной библиотеки написана не на языке С++

Пожалуйста, поподробнее.

@S_el · 24.04.2020, 00:17

Сообщение от TheCalligrapher

Вы о чем вообще? Требования алгоритма remove_copy_if накладываются на диапазоны, а не на итераторы.

Правильно на диапазоны. Есть входной диапазон [first, last), а под выходным понимается d_first, точно такие-же требования как и для обычного std::copy, только там cppreference пишет об этом явно:

Copies the elements in the range, defined by [first, last), to another range beginning at d_first.

1) Copies all elements in the range [first, last) starting from first and proceeding to last - 1. The behavior is undefined if d_first is within the range [first, last). In this case, std::copy_backward may be used instead.

а здесь не уточняет.
Я не вижу причин почему для этой функции что-то может отличаться.

@Ingeniger · 24.04.2020, 00:20 **[ТС]**

Сообщение от S_el

Ingeniger, это не ошибка, итератор beg не находится в диапазоне [++next, end), он установлен левее, на next, так что все в порядке.

Диапазоны не совпадают (естественно, ++next уже на 1 элемент), но перекрываются.

TheCalligrapher, концептуальное и логичное объяснение, спасибо. Сам не подумал об этом.

@TheCalligrapher · 24.04.2020, 00:41

Сообщение от avgoor

Пожалуйста, поподробнее.

Так а что тут может быть "поподробнее"?

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

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

@avgoor · 24.04.2020, 00:57

Сообщение от TheCalligrapher

Реализация стандартной библиотеки пишется на чем угодно.

Это, возможно, ее ядро пишется на чем угодно, причем, что угодно - это, как правило, C. Но, при этом, исключая специфические вещи (например, из последнего: корутины, которые без поддержки на уровне компилятора не реализовать), вся STL может быть реализована в виде набора хедеров. Разумеется, в каждом (почти) из этих хедеров будет что-то определено в пространстве std, что, безусловно, нарушает требования к языку C++. Но тогда возникает логичный вопрос: если эти хедеры написаны не на языке C++, тогда на каком? Псевдокод не предлагать, т.к. после препроцессинга они станут частью исходника, по крайней мере, я не помню в стандарте обратного, могу ошибаться.

@Ingeniger · 24.04.2020, 01:00 **[ТС]**

Сообщение от avgoor

сли эти хедеры написаны не на языке C++

Я, конечно, далеко не эксперт, но причем тут хэдеры, если речь идет о реализации?
Хэдеры - это же интерфейс, он на С++, естественно.
А реализация уже скомпилирована.

@avgoor · 24.04.2020, 01:08

Сообщение от Ingeniger

Хэдеры - это же интерфейс, он на С++, естественно.

В случае шаблонов, реализация находится в хедере (с оговорками). А STL - это standart template library. Да и вообще есть достаточно много header only библиотек.

@TheCalligrapher · 24.04.2020, 01:10

Сообщение от avgoor

Но тогда возникает логичный вопрос: если эти хедеры написаны не на языке C++, тогда на каком?

Не понимаю вопроса. На любом! Формально - на любом.

Фактически, как вы сами понимаете, они пишутся на платформенно-зависимом С++-подобном языке. То есть это "какбэ С++", но с полным игнорированием ограничений языка, соображений специфицированности или определенности поведения, с использованием внутренних неязыковых возможностей компилятора и т.п. То есть это не С++ вообще.

Сообщение от avgoor

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

Нет, формально не станут. Стандарт языка ясно говорит, что стандартные хедеры не являются файлами вообще и не обрабатываются так, как обрабатываются обычные хедер-файлы.

Директива #include с именем стандартного хедера в треугольных скобках являются лишь особой специальной директивой, предписывающей реализации неким "магическим" образом сделать доступными соответствующие средства стандартной библиотеки в данной единице трансляции. Ни о каком "включении" и "стать частью исходника" речи не идет в принципе.

На практике, конечно, стандартные хедеры обычно являются просто файлами. Но это не более чем деталь реализации, не более чем простейший способ реализации стандартных хедеров.

@avgoor · 24.04.2020, 01:26

Сообщение от TheCalligrapher

Директива #include с именем стандартного хедера в треугольных скобках являются лишь особой специальной директивой, предписывающей реализации неким "магическим" образом сделать доступными соответствующие средства стандартной библиотеки в данной единице трансляции.

Неа. 15.2 специально посмотрел

A preprocessing directive of the form
# include < h-char-sequence > new-line
searches a sequence of implementation-defined places for a header identified uniquely by the specified sequence
between the < and > delimiters, and causes the replacement of that directive by the entire contents of the
header. How the places are specified or the header identified is implementation-defined.

Кстати, как вы даете ссылки на определенный параграф стандарта?

Сообщение от TheCalligrapher

То есть это "какбэ С++", но с полным игнорированием ограничений языка, соображений специфицированности или определенности поведения

Игнорирования UB и определения specific - ИМХО, вполне хватит.

@TheCalligrapher · 24.04.2020, 02:33

Сообщение от avgoor

Неа. 15.2 специально посмотрел

Вы видите больше, чем там на самом деле есть. Идея стандартных заголовков описана в 16.5.1.2

1 Each element of the C++ standard library is declared or defined (as appropriate) in a header.¹⁶⁴
164) A header is not necessarily a source file, nor are the sequences delimited by < and > in header names necessarily valid source file names

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

Реализации могут смело использовать в реализации компонентов стандартной библиотеки и implementation-defined behavior, и unspecified behavior, и undefined behavior (т.е. расширения компилятора), и нестандартные процессорные intrinsics, и ассемблерные вставки, и код на Фортране, если в данной реализации все это поддерживается. А на ваш замечание о том, что "это же не С++", авторы могут ответить, что это просто не включается по #include <>. И тыкать их носом в результат работы препроцессора, в котором всё-таки всё это "включилось" бесполезно. Они вам скажут что вы суете нос в иррелевантные детали реализации, которые к тому же неправильно интерпретируете. И формально будут правы.

@S_el · 24.04.2020, 09:14

Сообщение от avgoor

Кстати, как вы даете ссылки на определенный параграф стандарта?

текущий черновик - http://eel.is/c++draft/ , есть возможность получить ссылку на любой пункт.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

@avgoor 1550 / 877 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	23.04.2020, 23:58
	Ingeniger, реализаций может быть много. Если написано, что не должны пересекаться - значит не должны. В какой-то реализации прокатит, но при смене компилятора будет фэйл. 0

@avgoor 1550 / 877 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	24.04.2020, 00:10
	Ingeniger, почему ошибка? Он приводит пример реализации. Она соответствует требованиям? Соответствует. А то, что она работает даже с перекрывающимися диапазонами (верю вам на слово, не читал)... ну так замечательно. В другой реализации может быть не так. 0

@S_el 2444 / 1842 / 406 Регистрация: 15.12.2013 Сообщений: 8,243
	24.04.2020, 00:10
	Ingeniger, это не ошибка, итератор beg не находится в диапазоне [++next, end), он установлен левее, на next, так что все в порядке. 0