понедельник, 23 декабря 2024 г.

[prog.c++] Возвращаясь к теме std::vector-а с назначаемой пользователем политикой роста

Вернусь к теме, поднятой пару месяцев назад: В std::vector не хватает вот какой штуки... Речь там шла о том, что хорошо было бы в std::vector иметь возможность управлять политикой роста объема вектора когда он полностью заполняется.

Часть комментариев к этой заметке (не только в блоггере, но и в других соцсетях) произвела на меня впечатление "ты и сам дурак, и хочешь странного, и вообще в std::vector все сделано зашибись, а если тебе чего-то не хватает, то сделай сам" (наверняка подразумевалось совсем другое, но я, как художник, которого каждый может обидеть, воспринял именно так, прошу понять и простить).

Ну и сделал в итоге, тогда же, в октябре. А вот возможность и время поделится впечатлениям нашлась только сейчас 🙁 Так что дико извиняюсь, что не по горячим следам, но лучше уж поздно, чем никогда.

Итак, был сделан шаблон, который параметризуется несколькими параметрами: исходный тип вектора (например, std::vector или folly::fbvector), типом хранящихся в векторе значений, типом политики роста объема вектора, типом аллокатора (по дефолту std::allocator).

Этот шаблон наследуется от типа исходного вектора. Т.е. если сказали, что нужно за основу брать std::vector, то vector_with_custom_growth_policy будет наследоваться от std::vector. Поэтому большинство методов из исходного типа вектора доступны благодаря наследованию.

Но часть методов реализуется в самом vector_with_custom_growth_policy. Это такие методы как: emplace_back, push_back (две штуки), emplace, insert (две штуки, обе для одиночного элемента). При этом я даже не брался за insert, который получает подпоследовательность в виде [begin, end).

Получилось где-то порядка 180 строк с комментариями. При этом моя реализация предоставляет только базовую, а не строгую, гарантию безопасности исключений. Т.е. если во время insert-а выброшено исключение, то ничего не протечет, но не факт, что вектор вернется в предшествующее состояние. Вероятно, более сильную гарантию можно было бы прикрутить, если покурить бамбук подольше. Но нельзя же постоянно курить бамбук за счет работодателя 😉

Общие впечатления: изначально кажется, что все просто и понятно. Затем внезапно (тм) тратишь время и силы на то, чтобы поддержать вот такую вот простую конструкцию: v.insert(v.end(), v[0]);

Если кто-то не знал, то нормальная реализация std::vector-а должна это поддерживать. Т.е. когда в insert/push_back прилетает ссылка на объект, который уже лежит в векторе, то нужно проявлять осторожность, чтобы при реаллокации вектора не инвалидировать эту ссылку.

Кстати говоря, я слышал, что такой вопрос иногда задают на собеседованиях по C++. Так что если не знали, то можете заучить, вдруг пригодится.

При этом сил на то, чтобы поддержать версию insert(pos, first, last) и версию insert(pos, initializer_list) уже не хватило 🙁

А из того, что было сделано, у меня сложилось впечатление, что прикручивать кастомную политику роста к std::vector снаружи такое себе занятие, т.к. внутри вектора при переаллокации содержимого можно делать все это проще и эффективнее.

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

PS. Показать реализацию не могу, т.к. делалось это все в рамках закрытого заказного проекта.