Здравствуйте, Nuzhny, Вы писали:

NB>>у мапы? зачем оно нужно?

N>Чтобы писать цикл, в условии которого будет: it < M.end()

Сравнение на больше/меньше появляются только на уровне категории RandomAccessIterator, к которой итераторы мапы не относятся. Итераторы мапы относятся категории BidirectionalIterator, для которой обязательными являются только операции сравнения на равенство/неравенство. И этих операций достаточно, чтобы написать цикл.

Здравствуйте, Videoman, Вы писали:

V>Нашел очень неприятную особенность STL в текущем стандарте с которой провозился пол дня, поэтому может быть кому-то будет интересно.

Откапали в C++ залежи костылей? В С++ их просто запредельно много, как ни в каком другом ЯП. Просто не удивляйтесь, для С++ это норма.

Здравствуйте, Videoman, Вы писали:

V>Теперь вопрос, что это — диверсия?

Есть объяснение этому на StackOverflow: https://stackoverflow.com/questions/57299324/why-is-stdmaps-move-constructor-not-noexcept

Здравствуйте, Nuzhny, Вы писали:

NB>>у мапы? зачем оно нужно?

N>Чтобы писать цикл, в условии которого будет: it < M.end()

и зачем такое условие нужно? для итераторов такие сравнения в принципе редко встречаются...
как ты в оцениваешь сложность этой операции для мапы?

Здравствуйте, Коваленко Дмитрий, Вы писали:
КД>В итераторе можно хранить указать на контейнер.

И удвоить размер каждого итератора, чтобы они в регистры не помещались? Нет спасибо.

КД>Это решит все перечисленные проблемы.

КД>Ну усложнит реализацию операторов сравнения (нужно учитывать указатель на родительский контейнер), зато не нужно выделять dummy-элемент.

КД>Так что по мне — лучше бы end() всегда ссылался на NULL-ноду.

Лучше располагать dummy ноду непосредственно внутри тела объекта std::map, не требуя alloc-а.
Это усложнит процедуры swap и перемещения, но на константное время, что явно дешевле работы с динамической памятью.

Здравствуйте, удусекшл, Вы писали:

У>Если в мапе ничего нет, то и begin и end вполне могут быть нулевыми, не?

Если есть требование, чтобы итераторы не менялись при добавлении новых данных, то не всё так просто: сначала взяли end(), потом добавили данные, снова взяли end() и он должен быть равен первому end():

 std::map<char,int> mymap;
 auto it = mymap.end();
 mymap.insert ( std::pair<char,int>('a',100) );
 mymap.insert ( std::pair<char,int>('z',200) );
 assert(mymap.end() == it);

Нашел очень неприятную особенность STL в текущем стандарте с которой провозился пол дня, поэтому может быть кому-то будет интересно.

Проблема:
Есть обыкновенный класс, назовем его "агрегатор" — класс, в нем несколько членов данных других классов, в которых, в свою очередь, другие члены и т.д. Код классов был под VS 2013 студию, где, в силу специфики реализации, все конструкторы перемещения были написаны явно с перемещение членов вручную и не было noexcept спецификатора. Переползли на VS 2017 с С++17. Появилась возможность писать = default для конструкторов перемещения и выкинуть избыточный код.

Теперь внимание:
Для самого корневого класса, меняю реализацию конструктора перемещения на = default и все перестает компилироваться со странными ошибками что класс не может быть скопирован (не перемещен, а именно скопирован). Уж сколько я боролся пытаясь выяснить что не так, пока не понял что дело в noexcept и не начал последовательно выкидывать члены классов, пока не дошел до std::map и std::unorderedmap и не выяснил что по стандарту у них конструкторы не noexcept .

Теперь вопрос, что это — диверсия?

Получается что если я захочу использовать в качестве члена класса std::map или std::unorderedmap, то я обязан пометить конструктор перемещения класса как "не noexcept", а заодно и во всей, возможно очень длинной, как у меня, цепочке классов которые используют этот класс в качестве члена?

std::vector, содержащий внутри std::map, всегда использует копирование при расширении?

Получается, что с одной стороны STL контейнеры требуют от меня указывать noexcept, иначе внутри них будет происходить копирование вместо перемещения, а с другой стороны, я не могу это сделать, так как внутри, внутри, внутри какого-то класса вдруг может понадобится std::map или std::unorderedmap.

Кто что думает по этому поводу?

Здравствуйте, Videoman, Вы писали:
V>Кто что думает по этому поводу?

за полный контроль самописных контейнеров

Здравствуйте, so5team, Вы писали:

S>Есть объяснение этому на StackOverflow: https://stackoverflow.com/questions/57299324/why-is-stdmaps-move-constructor-not-noexcept

Я конечно видел это объяснение, но не понял ничего. Если вас не затруднит, вы не могли бы объяснить своими словами в чем проблема?

Здравствуйте, so5team, Вы писали:

S>Суть в том, что в std::map, даже пустом, должна быть некая нода дерева поиска, на которую будет ссылаться итератор, возвращаемый методом end(). Стандарт разрешает реализациям std::map размещать эту ноду в динамической памяти (но не обязывает это делать).

Почему для std::map стандарт разрешает реализациям размещать end() в динамической памяти, а для std::vector — нет?

Здравствуйте, Nuzhny, Вы писали:

N>Ну и условие должно выполняться begin() < end(), поэтому он не может быть NULL.

у мапы? зачем оно нужно?

Здравствуйте, удусекшл, Вы писали:

SVZ>>end() может указывать куда угодно, но из него ты должен иметь возможность перепрыгнуть на последний живой объект.

У>Если в мапе ничего нет, то и begin и end вполне могут быть нулевыми, не?

Конечно могут.
В пустом контейнере end()-1 эквивалентно begin()-1, что является UB.
Если получится увязать нулевые итераторы и валидное поведение итератора end() при непустом контейнере, то почему бы и нет.
На первый взгляд выглядит вполне реализуемо.

Здравствуйте, Videoman, Вы писали:

V>Кто что думает по этому поводу?

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

vector(vector&&) noexcept;

но

map(map&& x);

а в реализации gcc

      map(map&&) = default;

Здравствуйте, Videoman, Вы писали:

S>>Есть объяснение этому на StackOverflow: https://stackoverflow.com/questions/57299324/why-is-stdmaps-move-constructor-not-noexcept

V>Я конечно видел это объяснение, но не понял ничего. Если вас не затруднит, вы не могли бы объяснить своими словами в чем проблема?

Суть в том, что в std::map, даже пустом, должна быть некая нода дерева поиска, на которую будет ссылаться итератор, возвращаемый методом end(). Стандарт разрешает реализациям std::map размещать эту ноду в динамической памяти (но не обязывает это делать). Поэтому в каких-то реализациях STL, в частности от MS, эта нода в std::map как раз в динамической памяти и размещается.

Когда происходит перемещение содержимого из одного std::map (пусть это будет A) в другой (пусть это будет B), то std::map A должен остаться в корректном состоянии. Т.е. метод end() для A должен возвращать итератор, ссылающийся на какую-то ноду. Но что это за нода, ведь все содержимое A перехало в B?

Эту новую ноду после переезда нужно создать для A заново. И как раз при создании может быть брошено исключение. Поэтому move constructor для такого std::map не может быть noexcept.

Здравствуйте, B0FEE664, Вы писали:

BFE>Почему для std::map стандарт разрешает реализациям размещать end() в динамической памяти, а для std::vector — нет?

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

Либо я вопрос не понял.

Здравствуйте, Stanislav V. Zudin, Вы писали:

BFE>>Почему для std::map стандарт разрешает реализациям размещать end() в динамической памяти, а для std::vector — нет?
SVZ>Ну вообще-то у вектора end() указует за последний элемент в блоке памяти, выделенной как раз в динамической памяти.
Что мешает std::map поступать так же?

SVZ>Его не надо как-то специально размещать.

А если вектор пустой, то куда указывает std::vector::end?

Здравствуйте, B0FEE664, Вы писали:

SVZ>>Ну вообще-то у вектора end() указует за последний элемент в блоке памяти, выделенной как раз в динамической памяти.
BFE>Что мешает std::map поступать так же?

Эээ... спецификация.
Добавление нового узла не должно портить остальные итераторы. На непрерывном блоке памяти такое гарантировать невозможно.


BFE>А если вектор пустой, то куда указывает std::vector::end?

Например туда же, куда и begin(). Из этого можно вывести, что массив пуст. Или на NULL, тоже легко проверяется.

Здравствуйте, so5team, Вы писали:

S>Здравствуйте, Videoman, Вы писали:

V>>Теперь вопрос, что это — диверсия?

S>Есть объяснение этому на StackOverflow: https://stackoverflow.com/questions/57299324/why-is-stdmaps-move-constructor-not-noexcept

It is because I couldn't talk all of the implementors into a resource-less state that the map could be put into.

В переводе на русский: "так сделано в угоду дебилам, реализующим STL".
Слава Богу, меня это всё не касается.
Я достаточно долго живу, чтобы понять, что Майкрософт не способна написать С++ компилятор, поэтому я не пользуюсь VC.
Я достаточно долго живу, чтобы понять, что разработчики стандарта и стандартной библиотеки не способны сделать хороший продукт.
Поэтому я сделал CCore.

А вам всем -- счастливого траха.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>>>Ну вообще-то у вектора end() указует за последний элемент в блоке памяти, выделенной как раз в динамической памяти.
BFE>>Что мешает std::map поступать так же?
SVZ>Эээ... спецификация.
SVZ>Добавление нового узла не должно портить остальные итераторы. На непрерывном блоке памяти такое гарантировать невозможно.
Ээээ....
Я немного о другом.
Вот такой псевдокод чем не устраивает?:

class map
{
  tree_node* root;

  map()
  {
    root = nullptr;
  }

  iterator begin() 
  {
    return nullptr == root ? root + 1 : root;
  }

  iterator end() 
  {
    return root + 1;
  }
};

BFE>>А если вектор пустой, то куда указывает std::vector::end?
SVZ>Например туда же, куда и begin(). Из этого можно вывести, что массив пуст.
SVZ>Или на NULL, тоже легко проверяется.

А разве нет требования, чтобы end() итераторы различались у разных объектов?

Здравствуйте, B0FEE664, Вы писали:

BFE>>>Что мешает std::map поступать так же?
SVZ>>Эээ... спецификация.
SVZ>>Добавление нового узла не должно портить остальные итераторы. На непрерывном блоке памяти такое гарантировать невозможно.
BFE>Ээээ....
BFE>Я немного о другом.
BFE>Вот такой псевдокод чем не устраивает?:

В принципе значения из специального диапазона, в котором точно не окажется валидных объектов, вполне имеет право на существование.
Правда я не готов сказать, применим ли такой подход на всех платформах.
Может где-то нет такой "запрещенной зоны", например, в ДОСе.

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

iterator last_hero = m_map.end() - 1;

А по стандарту должна. Т.е. итератор end должен быть не просто фуфельным, но хранить указатель на последний валидный объект.

BFE>>>А если вектор пустой, то куда указывает std::vector::end?
SVZ>>Например туда же, куда и begin(). Из этого можно вывести, что массив пуст.
SVZ>>Или на NULL, тоже легко проверяется.

BFE>А разве нет требования, чтобы end() итераторы различались у разных объектов?

Ну у непустых контейнеров они и будут различаться. Так сказать, естественным образом.

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>А по стандарту должна. Т.е. итератор end должен быть не просто фуфельным, но хранить указатель на последний валидный объект.

Только не на последний, а на следующий за последним. На последний end() — 1 указывает.
Ну и условие должно выполняться begin() < end(), поэтому он не может быть NULL.

Здравствуйте, night beast, Вы писали:

NB>у мапы? зачем оно нужно?

Чтобы писать цикл, в условии которого будет: it < M.end()

Здравствуйте, so5team, Вы писали:

S>>>Есть объяснение этому на StackOverflow: https://stackoverflow.com/questions/57299324/why-is-stdmaps-move-constructor-not-noexcept

V>>Я конечно видел это объяснение, но не понял ничего. Если вас не затруднит, вы не могли бы объяснить своими словами в чем проблема?

S>Суть в том, что в std::map, даже пустом, должна быть некая нода дерева поиска, на которую будет ссылаться итератор, возвращаемый методом end().

А зачем она там нужна, эта dummy-нода?

Чтобы end() одного пустого map отличался от end() другого пустого map?

Здравствуйте, so5team, Вы писали:

S>Суть в том, что в std::map, даже пустом, должна быть некая нода дерева поиска, на которую будет ссылаться итератор, возвращаемый методом end(). Стандарт разрешает реализациям std::map размещать эту ноду в динамической памяти (но не обязывает это делать). Поэтому в каких-то реализациях STL, в частности от MS, эта нода в std::map как раз в динамической памяти и размещается.

S>Когда происходит перемещение содержимого из одного std::map (пусть это будет A) в другой (пусть это будет B), то std::map A должен остаться в корректном состоянии. Т.е. метод end() для A должен возвращать итератор, ссылающийся на какую-то ноду. Но что это за нода, ведь все содержимое A перехало в B?

S>Эту новую ноду после переезда нужно создать для A заново. И как раз при создании может быть брошено исключение. Поэтому move constructor для такого std::map не может быть noexcept.

Такое ощущение, что кто-то в комитете стандартизации просто запилил требования под свои хотелки или просто не подумал. В общем случае, после move объект может быть корректно удален или переприсвоен — его состояние не определено. Вот так и надо было оставить для всех классов, иначе вся концепция просто не работает. Я описал выше почему. Мы же понимаем что если в одних версиях STL, map будет иметь конструктор noexcept, а в других не noexcept, то мы ломаем переносимость кода полностью, он просто не будет компилироваться. И я не уверен что так только с map и unorderedmap, может быть есть где-то еще.
Допустим, был у меня код использующий = default разрабатываемый под GCC. Я его перенес на MS или еще куда, и все сломалось.
А как же не платить за то, что не используешь? Если все контейнеры вдруг начинаю копировать std::map вместо перемещения, а по окончанию пепемещения еще и new дергается ???

P.S. Прошу заметить я критикую только STL. В своем коде я могу поступать и так и так, и все всегда будет работать, на любой платформе, но стандарт я не могу игнорировать.

Здравствуйте, Коваленко Дмитрий, Вы писали:

КД>Здравствуйте, so5team, Вы писали:

S>>>>Есть объяснение этому на StackOverflow: https://stackoverflow.com/questions/57299324/why-is-stdmaps-move-constructor-not-noexcept

V>>>Я конечно видел это объяснение, но не понял ничего. Если вас не затруднит, вы не могли бы объяснить своими словами в чем проблема?

S>>Суть в том, что в std::map, даже пустом, должна быть некая нода дерева поиска, на которую будет ссылаться итератор, возвращаемый методом end().

КД>А зачем она там нужна, эта dummy-нода?

КД>Чтобы end() одного пустого map отличался от end() другого пустого map?

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

Здравствуйте, Chorkov, Вы писали:

S>>>Суть в том, что в std::map, даже пустом, должна быть некая нода дерева поиска, на которую будет ссылаться итератор, возвращаемый методом end().

КД>>А зачем она там нужна, эта dummy-нода?

КД>>Чтобы end() одного пустого map отличался от end() другого пустого map?

C>При добавлении новых элементов итераторы не должны инвалидироваться, в том числе итератор указывающий на end.
C>После добавления элементов, нужно поддерживать операцию --i, которая будет приводить к разным элементам для разных контейнеров.
C>Т.е. end разных map-ов должны быть различимы, даже если это end пустого контейнера.

В итераторе можно хранить указать на контейнер.

Это решит все перечисленные проблемы.

Ну усложнит реализацию операторов сравнения (нужно учитывать указатель на родительский контейнер), зато не нужно выделять dummy-элемент.

Так что по мне — лучше бы end() всегда ссылался на NULL-ноду.

Вот еще полезная презентация на эту (и не только эту) тему вокруг move semantics и noexcept:

https://www.slideshare.net/arvidn/c-nothrow-movable-types

Здравствуйте, so5team, Вы писали:

S>Эту новую ноду после переезда нужно создать для A заново. И как раз при создании может быть брошено исключение. Поэтому move constructor для такого std::map не может быть noexcept.

Вот это непонятно. По идее, переезд должен осуществляться простым перемещением указателя, не? Зачем там заново что-то создавать?

Здравствуйте, удусекшл, Вы писали:

S>>Эту новую ноду после переезда нужно создать для A заново. И как раз при создании может быть брошено исключение. Поэтому move constructor для такого std::map не может быть noexcept.

У>Вот это непонятно. По идее, переезд должен осуществляться простым перемещением указателя, не? Зачем там заново что-то создавать?

Грубо говоря, у вас есть нечто вида:

class map {
  node * root_;
  node * end_;
  ...
public:
  map() : root_{nullptr}, end_{new node{}} {...}
  ...
}

С оператором перемещения нет никаких проблем, т.к. у обоих сторон есть все сущности, поэтому вы можете сделать так:

map & map::operator=(map && o) {
  swap(root_, o.root_);
  swap(end_, o.end_);
  o.clear();
}

Но вот в конструкторе перемещения у вас еще нет собственного объекта для end_. И поэтому у вас конструктор перемещения превращается во что-то вида:

map::map(map && o) : root_{nullptr}, end_{new node{}} {
  swap(root_, o.root_);
  swap(end_, o.end_);
}

Ведь если вы не создадите новый объект для end_, то вам будет нечем инициализировать o.end_ после перемещения.

Отсюда и получается new, который может бросать.

PS. Сам реализацией map-а никогда не занимался и в реализацию штатных std::map никогда не погружался. Вышеизложенное является лишь фиксацией соображений из собственного здравого смысла.

Здравствуйте, Videoman

Ваши жалобы можно понять, но они ничего не изменят.

А 11-й стандарт, в котором noexcept появился, принимался с учетом уже имеющихся реализаций std::map/multimap/set/multiset/list. И если тот же MS настаивал на том, что их реализация имеет право на жизнь, то комитет вряд ли мог что-то этому противопоставить.

Поэтому имеем то, что имеем.

Здравствуйте, so5team, Вы писали:

S>Ваши жалобы можно понять, но они ничего не изменят.

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

Здравствуйте, so5team, Вы писали:

S>Но вот в конструкторе перемещения у вас еще нет собственного объекта для end_. И поэтому у вас конструктор перемещения превращается во что-то вида:
S>

S>map::map(map && o) : root_{nullptr}, end_{new node{}} {
S>  swap(root_, o.root_);
S>  swap(end_, o.end_);
S>}

S>Ведь если вы не создадите новый объект для end_, то вам будет нечем инициализировать o.end_ после перемещения.

S>Отсюда и получается new, который может бросать.

S>PS. Сам реализацией map-а никогда не занимался и в реализацию штатных std::map никогда не погружался. Вышеизложенное является лишь фиксацией соображений из собственного здравого смысла.

А почему нельзя

map::map(map && o) : root_{nullptr}, end_{nullptr} ...

сделать?

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>В принципе значения из специального диапазона, в котором точно не окажется валидных объектов, вполне имеет право на существование.
SVZ>Правда я не готов сказать, применим ли такой подход на всех платформах.
SVZ>Может где-то нет такой "запрещенной зоны", например, в ДОСе.
past-the-end указатель должен обеспечиваться на всех платформах и этим можно воспользоваться так или иначе. Согласен, что в моём псевдокоде мне этого не удалось, так как иметь значение указателя nullptr + 1 — это UB.

SVZ>Но вот вопрос: а сможет ли твоя реализация обеспечить корректность такого кода:
SVZ>

SVZ>iterator last_hero = m_map.end() - 1;
SVZ>

SVZ>А по стандарту должна.
Конечно реализация должна это обеспечивать, но прямо сейчас я корректный код не напишу.

SVZ>Т.е. итератор end должен быть не просто фуфельным, но хранить указатель на последний валидный объект.
Нет, именно что end может указывать туда, куда нам угодно.

Здравствуйте, B0FEE664, Вы писали:

SVZ>>Т.е. итератор end должен быть не просто фуфельным, но хранить указатель на последний валидный объект.
BFE>Нет, именно что end может указывать туда, куда нам угодно.

end() может указывать куда угодно, но из него ты должен иметь возможность перепрыгнуть на последний живой объект.

Мне по душе вариант с фуфельным узлом в теле контейнера, об этом варианте наш коллега написал выше

Автор: Chorkov
Дата: 22.11.19

.

Если меня склероз не подводит, то во времена оно, когда была популярна STLPort (год эдак 2003), требования к map::end() были попроще.
И в микрософтовской версии stl end() реализовывался в виде статического dummy объекта.
Мы на это напоролись при работе с контейнером, созданном не в своей dll
В то же самое время у STLPort каждый контейнер имел свой экземпляр end().

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>>>Т.е. итератор end должен быть не просто фуфельным, но хранить указатель на последний валидный объект.
BFE>>Нет, именно что end может указывать туда, куда нам угодно.

SVZ>end() может указывать куда угодно, но из него ты должен иметь возможность перепрыгнуть на последний живой объект.

Если в мапе ничего нет, то и begin и end вполне могут быть нулевыми, не?

Здравствуйте, удусекшл, Вы писали:

У>А почему нельзя
У>

map::map(map && o) : root_{nullptr}, end_{nullptr} ...

У>сделать?

Полагаю потому, что в iterator нужно засовывать указатель на реальный node, а не nullptr.

Здравствуйте, B0FEE664, Вы писали:

У>>Если в мапе ничего нет, то и begin и end вполне могут быть нулевыми, не?

BFE>Если есть требование, чтобы итераторы не менялись при добавлении новых данных, то не всё так просто: сначала взяли end(), потом добавили данные, снова взяли end() и он должен быть равен первому end():

Мысль верная, но эту проблему можно разрулить на уровне оператора сравнения.
Т.е. не адреса сравнивать, а внутреннее состояние.

У>А почему нельзя
У>

map::map(map && o) : root_{nullptr}, end_{nullptr} ...

У>сделать?

При вставке первого элемента в map будет создание *end() ноды, для этого будет if и он будет отрабатывать при КАЖДОЙ вставке...