Здравствуйте! Я думаю, что почти все программисты, пишущие на C++, регулярно используют и STL. Библиотека, безусловно, замечательная, но в ней сокрыто немало тонкостей, которые могут неожиданно вылезти на контесте.
Например, совсем недавно я узнал, что vector<bool> хранит элементы в виде байтов, в каждом из которых содержится по 8 bool'ов, из-за чего не очень быстро (очень не быстро?) работает. Или, например, что вектор в Visual Studio расширяется в 1.5 раза, а вектор в g++ - в 2 раза. Поправьте меня, если я не прав.
Я думаю, что опытные кодеры знают куда больше трюков, и предлагаю в этой теме обменяться опытом использования STL. Интересуют как общие для обоих компиляторов вещи, так и специфичные, потому что контесты приходится зачастую писать в разных средах.
Для начала мне хотелось бы узнать две вещи:
1) За сколько работают методы begin, end, size у сложных структур типо set, map.
2) Как писать лучше и быстрее: set.find(elem) != set.end() или set.count(elem) == 0
3) Правда ли, что stack, queue и deque очень медленно работают?
Надо быть аккуратнее с count когда юзаешь multiset, точнее лучше вообще в таком случае не использовать count. Для меня было когда-то очень неожиданным, что count в multiset работает за log(n) + количество считаемых элементов. Можно тут лицезреть это: http://ideone.com/SPYAh
2)Про count уже сказали - от multiset'а не использовать. Так что с multi- лучше find, и в остальных случаях, думаю, без разницы.
3)Да. Когда их константа - это еще более-менее, но помимо этого они жрут очень много памяти. Например, 105 деков интов в ML не влезут. Лучше использовать либо ручками, либо list
По поводу deque - правда. Есть очень сильное подозрение (поправьте, если не прав), что deque - это обычный вектор с задефайненой операцией #define push_front(val) insert(d.begin(), val). Подозрение появилось после того как сдавая задачу на 0-1 обход заметил что работают вектор и дек одинаково.
Может это и не имеет отношения к STL, но все же спрошу:
1) Разницу не замечал, но точно утверждать что ее нет не могу.