Не совсем понимаю как работает метод Код (Text): iterator map::insert( iterator _Where, const value_type& _Val ); В MSDN написано: Но при вставке я обнаруживаю вызов оператора сравнения аж 14 раз, хотя, итератор указывает непосредственно на вставляемый элемент. Тут ведь даже дерево балансировать не нужно! Код (Text): class A { private: int x; public: A(int x) : x(x) {} inline bool operator < (A const& a) const { return x < a.x; } }; int test() { std::map<A, char> m; std::map<A, char>::iterator i; for (uint_t i = 0; i < 100; ++ i) { m[i] = 'a' + i % ('z' - 'a'); } i = m.lower_bound(2); // operator < calls 16 onces m.insert(i, std::map<int, char>::value_type(2, 'e')); // operator < calls 14 onces return 0; } Почему так?
И что? Он должен сравнить элемент с двумя соседними вершинами, а не пробегать заново всё дерево.. Если я уже знаю позицию, то вставка будет происходить быстрее, не находите?
cupuyc Это библиотечная реализация. Она считает, что клиентский код написан идиотом. Посему единственный метод вставить без лишних проверок -- это забить на инкапсуляцию и врезать самостоятельно. Что, как правило, не вариант. Есть ещё один способ: написать этот самый map ручками. Это ведь бинарное отсортированное дерево? Ну дык его писать -- двадцать минут вместе с отладкой и тестами.
cupuyc В таком случае, скорее всего, не совсем правильно задается позиция для вставки. Пробегись отладчиком, благо исходники STL имеются. r90 map обычно реализуется красно-черным деревом, это далеко не на 20 минут реализации.
Значит будет значительно дольше, я так предполагаю. Пробежится пио дереву вниз, не найдёт, начнёт с корня. Не совсем. Это красно-чёрное дерево. Вставка/удаление элементов - не так тривиальны. Я пробовал и ++ к позиции делать и --. Разница есть, но не большая.
ещё такой прикол: Код (Text): std::map<int, int> m; std::map<int, int>::iterator i; m.insert(std::map<int, int>::value_type(1, 'a')); i = m.begin(); // i = (1, 'a') -- i; // i = m.end() -- i; // i = (1, 'a') -- i; // i = m.end() -- i; // i = (1, 'a') то есть если на iterator равный end сделать декремент, то iterator указывает на первый элемент.
cupuyc А ты не парься и напиши тривиальную реализацию. Когда (и если) понадобится нетривиальная, потратишь пару суток и напишешь её.
r90 Вообще-то std либа написана нормально, не на все случаи конечно. Для чего вы предлагаете написание велосипеда?
Один как обычно пытается дискредитировать стандартную библиотеку, другой предлагает её выкинуть. Мой вопрос был с подколкой, дискутировать о велосипедах и прочих транспортах в мои планы не входило.
Booster Я ничего не говорил о "нормальности" или "ненормальности" stl. Просто если вставить в универсальную реализацию дерева дольше и сложнее, чем написать узкоспециализированный велосипед, то я голосую за велосипед.
Лол, тоже мне истина в последней инстанции. А про велосипеды и несовершенство STL - пожалуйста, продолжайте. Это так увлекательно ^_^
Как обычно перед тем как катить бочку нужно хорошо почитать мануал. То есть элемент тупо не вставляется и всё, значение конечно не меняется. Если элемент не был до этого вставлен, то данная версия функции работает как и ожидается(кто бы сомневался). Единственно к чему тут можно придраться, так это почему в случае обнаружения совпадения функция не вышла сразу, а запускается поиск с корня. Но вот такая реализация, сэкономили на дополнительных проверках, стандарту это не противоречит. Производить операции над end - запрещено, это ub.
stl надежна и проверена временем, разрабатывалась с упором на эффективность, и при правильном применении как минимум не хуже велосипедов, а зачастую гораздо лучше. Что кстати понимается под "практическим софтом"? В проекте масштаба ~500k строк и ~2 лет разработки тоже не будете использовать stl, boost и прочие библиотеки?
Booster Ну так и я о том же. Если мы собираемся использовать инструмент так, как нельзя использовать map, значит нам нужен другой инструмент.
