В моей программе чаще встречается вычитание ~ из 10млн элементов 10тыс - 8млн элементов. Если 10 млн на 10 млн случится, то будет долго искать. Думаю, что пробег ради 1 элемента - скромная плата за скорость на больших множествах.
Ну как сказать, если удаляется 1/1000, то простецкое удаление find/erase окажется намного быстрее. Но обычно в подобных задачах важнее другое - а стоит ли вообще заводить ассоциативный контейнер который выжрет немало памяти? Напр если только в целях "быстрого вычитания", то может и нет
Вашего примера я не понял.
Что в своем примере Вы делаете первым в главном цикле? Находите вычитаемый эл-т с которым надо сравнивать (кстати в общем случае lower_bound). Для массивов все то же самое, только вместо erase - сдвиг (поэлементный)
