Несколько переделала сайт (purplesyringa.moe), добавила отдельный раздел с блог постами и прикрутила RSS. Возможно, позже повыкладываю туда что-то интересное из этого канала. Еще выложила черновик; не уверена, что оно пойдет именно так, но почитать можно.

По просьбе выложила статью на сайт. Скажите, так действительно удобнее читать, чем в телеге?

https://purplesyringa.moe/blog/ru/base64-has-a-fixed-point/

Vm0wd2QyUXlVWGxWV0d4V1YwZDRWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVUbGhoTVVwVVZtcEJlRll5U2tWVWJHaG9UVlZ3VlZadGNFSmxSbGw1VTJ0V1ZXSkhhRzlVVmxaM1ZsWmFkR05GU214U2JHdzFWVEowVjFaWFNraGhSemxWVm14YU0xWnNXbUZrUjA1R1UyMTRVMkpIZHpGV1ZFb3dWakZhV0ZOcmFHaFNlbXhXVm0xNFlVMHhXbk5YYlVaclVqQTFSMVV5TVRSVk1rcElaSHBHVjFaRmIzZFdha1poVjBaT2NtRkhhRk5sYlhoWFZtMHhORmxWTUhoWGJrNVlZbFZhY2xWcVFURlNNVlY1VFZSU1ZrMXJjRWxhU0hCSFZqRmFSbUl6WkZkaGExcG9WakJhVDJOdFJraGhSazVzWWxob1dGWnRNSGhPUm14V1RVaG9XR0pyTlZsWmJGWmhZMnhXY1ZGVVJsTk5WbFkxVkZaU1UxWnJNWEpqUld4aFUwaENTRlpxUm1GU2JVbDZXa1prYUdFeGNHOVdha0poVkRKT2RGSnJhR2hTYXpWeldXeG9iMWRHV25STlNHaFBVbTE0VjFSVmFHOVhSMHB5VGxac1dtSkdXbWhaTW5oWFkxWkdWVkpzVGs1V2JGa3hWa1phVTFVeFduSk5XRXBxVWxkNGFGVXdhRU5UUmxweFVtMUdVMkpWYkRaWGExcHJZVWRGZUdOSE9WZGhhMHBvVmtSS1QyUkdTbkpoUjJoVFlYcFdlbGRYZUc5aU1XUkhWMjVTVGxOSGFGQlZiVEUwVmpGU1ZtRkhPVmhTTUhCNVZHeGFjMWR0U2tkWGJXaGFUVzVvV0ZreFdrZFdWa3B6VkdzMVYySkdhM2hXYTFwaFZURlZlRmR1U2s1WFJYQnhWV3hrTkdGR1ZYZGhSVTVVVW14d2VGVnRNVWRWTWtwV1lrUmFXR0V4Y0hKWlZXUkdaVWRPU0U5V1pHaGhNSEJ2Vm10U1MxUXlVa2RUYmtwb1VqSm9WRmxZY0ZkbGJHUllaVWM1YVUxWFVraFdNalZUVkd4T1NHRkdRbFppVkVVd1ZtcEdVMVp0UmtoUFZtaFRUVWhDTlZaSGVHRmpNV1IwVTJ0a1dHSlhhR0ZVVnpWdlYwWnJlRmRyWkZkV2EzQjZWa2R6TVZZeVNrZGhNMmhYWVRGd2FGWlVSbFpsUm1SMVUyczFXRkpZUW5oV1YzaHJUa2RHUjFaWVpHaFNWVFZWVlcxNGQyVkdWblJOVldSV1RXdHdWMWxyVW1GWFIwVjRZMGhLV2xaWFVrZGFWV1JQVTBVNVYxcEhhR2hOU0VKMlZtMTBVMU14VVhsVmEyUlVZbXR3YjFWcVNtOVdSbXhaWTBaa2JHSkhVbGxhVldNMVlWVXhXRlZyYUZkTmFsWlVWa2Q0VDFOSFJrZFJiRnBwVmtWVmQxWnRjRWRWTVZwMFVtdG9VRlp0YUZSVVZXaERUbFphU0dWSFJtcE5WMUl3VlRKMGExZEhTbGhoUjBaVlZucFdkbFl3V25KbFJtUnlXa1prVjJFelFqWldhMlI2VFZaWmVWTnJaR2hOTW1oWVdWUkdkMkZHV2xWU2JGcHNVbTFTTVZVeWN6RlhSa3BaVVc1b1YxWXphSEpVYTJSSFVqRmFXVnBIYUZOV1ZGWldWbGN4TkdReVZrZFdibEpPVmxkU1YxUlhkSGRXTVd4eVZXMUdXRkl3VmpSWk1HaExWMnhhV0ZWclpHRldWMUpRVlRCVk5WWXhjRWhoUjJoT1UwVktNbFp0TVRCVk1VMTRWVmhzVm1FeVVsVlpiWFIzWWpGV2NWTnRPVmRTYlhoYVdUQmFhMkpIU2toVmJHeGhWbGROTVZsV1ZYaFhSbFp5WVVaa1RtRnNXbFZXYTJRMFZERk9TRkpyWkZKaVJuQndWbXRXVm1ReFduUmpSV1JXVFZad01GVnRkRzlWUmxwMFlVWlNWVlpYYUVSVWJGcGhVMGRXU0ZKdGNFNVdNVWwzVmxSS01HRXhaRWhUYkdob1VqQmFWbFp1Y0Zka2JGbDNWMjVLYkZKdFVubFhhMXByVmpKRmVsRnFXbGRoTWxJMlZGWmFXbVZXVG5KYVIyaE9UVzFvV1ZkV1VrZGtNa1pIVjJ4V1UySkdjSE5WYlRGVFRWWlZlV042UmxoU2EzQmFWVmMxYjFZeFdYcGhTRXBWWVRKU1NGVnFSbUZYVm5CSVlVWk9WMVpHV2xkV2JHTjRUa2RSZVZaclpGZGliRXBQVm14a1UxWXhVbGhrU0dSWFRWZDRlVlpYTVVkWFJrbDNWbXBTV2sxSGFFeFdNbmhoVjBaV2NscEhSbGRXTVVwUlZsUkNWazVXV1hoalJXaG9VakpvVDFVd1ZrdE5iRnAwVFZSQ1ZrMVZNVFJXVm1oelZtMUZlVlZzVmxwaVdGSXpXV3BHVjJOV1RuUlBWbVJUWWxob1lWZFVRbUZoTWtwSVUydG9WbUpIZUdoV2JHUk9UVlpzVjFaWWFGaFNiRnA1V1ZWYWExUnRSbk5YYkZaWFlUSlJNRlpFUms5VFJrcHlXa1pLYVZKdVFuZFdiWFJYVm0xUmVGZHVVbXBTVjFKWFZGWmFkMDFHVm5Sa1J6bFdVbXh3TUZsVldsTldWbHBZWVVWU1ZXSkdjR2hWTUdSWFUwWktkR05GTlZkTlZXd3pWbXhTUzAxSFJYaGFSV2hVWWtkb2IxVnFRbUZXYkZwMVkwWmthMkpHYkROV01qVkxZa1pLZEZWdWJGaGhNWEJ5Vm1wS1JtVnNSbkZYYkdSb1RXeEpNbFpHV21GWGJWWlhWRzVLWVZJeWFFOVVWekZ2VjFaa1YxVnJaR3ROYTFwSVZqSjRWMVV5U2tkalNFNVdZbFJHVkZSV1dsWmxWMDQyVW14b1UyRXpRbUZXVm1NeFlqRlplRmRZY0doVFJYQldXVlJLVTFOR1ZuRlNiVVpZVm01Q1NWbFZXazlXTVZwSFYyeGtWMkpIVGpSVWEyUlNaVlphY2xwR1pHbGlSWEJRVm0xNGExVXhXWGhWYkdoclUwZFNXRlJXWkRSbFZscFlUVlZrV0ZKcmJETldiWEJUVjJzeFNHRkZlRmROYm1ob1ZqQmFWMk5zY0VoU2JHUlhUVlZ3VWxac1VrTldhelZYVjFob2FsSlhhRzlWYWtwdlZERlZkMVpyZEU1aVJuQXdWRlpTUTFack1WWk5WRkpYVm0xb2VsWnRNVVpsVmxaelZteHdhVmRHU1hwWFYzQkhWakpPVjFSdVVsQldiVkpVV1d4b2IxbFdaRlZSYlVab1RXdHdTVlV5ZEc5V2JVcElaVWRvVjJKSFVrOVVWbHB6VmpGYVdXRkdhRk5pUm5BMVYxWldZV0V4VW5SU2JrNVlZa1phV0ZsVVNsSk5SbHBGVW1zNVZGSnJjSGxYYTFwTFlWWktkVkZ1WkZkaVdGSllWbTB4VW1WR1pIVlZiWEJUVmpGS1dGWkdXbUZrTURGSFZtNVNhMUo2YkZkVmJYaDNUVVpzVmxkc1RsZFdiSEJaV1ZWV1UxWlhTa2RqUjJoV1RVZFNXRlV3V2t0a1IwNUdUbFprVGxaWGQzcFdiWGhUVXpBeFNGSllhR0ZTVjJoVldXdGtiMkl4Vm5GUmJVWlhZa1p3TVZrd1dtdGhNa3BIWWtST1YwMXFWa3haYTFwTFpFWldkV0pHYUdoTldFSjVWbTF3UzFKdFZuTlNia1pZWWtkU2IxUlhlRXBOYkZwSFYyMUdXR0pXV2xoV1J6VkxXVlpKZVdGRk9WVldla1oyVmpGYWExWXhWbkphUjNST1lURndTVlpxU2pSV01WVjVVMnRrYWxORk5WZFpiRkpIVmtaU1YxZHNXbXhXTURReVZXMTRiMVV5UlhwUmJVWlhWbTFOZUZscVJscGxSbVJaWTBkb1ZGSllRbGRYVmxKTFZURk9SMVp1UmxOaVZWcFpWbTAxUTFOV2JGWlhhemxYVFZad1NGWXllR3RXTWtwSVZHcFNWV0V5VWxOYVZscGhZMnh3UjFwSGJHbFNXR...

А вот так:

В сниппетах 3 и 5 разница только в контейнерах, и согласно стандарту, и там, и там должен быть UB. Но одно дело — UB, а другое — краши. Например, сниппет 3 на практике не крашится, и это в целом понятно: вариантов реализовать итератор вектора мало, это обычно просто обычный указатель T*, а с ним никакой фигни не происходит. А вот сниппет 5 крашится, хотя там тоже должен быть тупо указатель на ноду дерева, а ноды никуда не перемещаются. Почему? Откуда краш?

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

Проблема у этого решения дурацкая: итераторы можно обычно не только инкрементировать, но и декрементировать, а куда идти влево от nullptr — непонятно. Можно добавить в итератор один bool exhausted; и в состоянии end() вместо nullptr хранить пару (last_node, true), но это лишняя памать и логика тратится.

Авторы libstdc++ — люди с альтернативным устройством мозга (просто посмотрите на их форматирование кода и количество копипасты), поэтому они придумали вместо этого гениальное решение: у каждого дерева есть фиктивная нода, которая используется в качестве end(), и эта нода в себе дополнительно хранит указатель на самую правую ноду дерева, чтобы operator\-\- работал быстро.

Так вот. Авторы libstdc++ решили, что делать аллокацию при создании пустого сета плохо. Делать две аллокации при добавлении первого элемента им почему-то тоже не захотелось, поэтому эту самую фиктивную ноду они хранят прямо в структуре std::set. Т.е. переменная end = set\->end() в себе хранила буквально указатель на поле объекта *set, и понятно, что при его релокации все сломается.

Заодно, кстати, разработчики стандартной библиотеки скрестили ежа с ужом: раз уж они в этой ноде вынуждены хранить указатель на самую правую ноду дерева, то его вполне можно хранить в поле right, которое у других нод указывает на правого ребенка. И да, самую левую ноду, которая нужна для эффективной реализации begin(), они хранят в поле left.

Угадаете, в каком поле этой фиктивной вершины они хранят указатель на корневую ноду дерева?

То есть типичное biblically accurate red-black tree согласно авторам libstdc++ выглядит не так:

1. Есть ли в этом коде UB?

auto set = std::make\_unique(std::set<int>{1, 2, 3}); for (int x : *set) { set = std::make\_unique(std::move(*set)); }

Да, есть.