Для общего случая любых критериев вы не можете сделать лучше, чем перебирать каждый элемент.
Каждый контейнер имеет специфические c критерии , с которыми он может работать лучше, например,
std::set<std::string> strings = /* something */;
auto first = strings.lower_bound("a"); // O(log(strings)), "a" is the least string that starts with 'a'
auto last = strings.lower_bound("b"); // O(log(strings)), "b" is the first string after those that start with 'a'
strings.erase(first, last); // O(log(strings) + distance(first, last)), all the strings starting with 'a' are removed
Здесь мы удаляем элементы, начинающиеся с 'a', со сложностью of O(log(strings) + distance(first, last)), что является улучшением O(alphabet) по сравнению с повторением всех элементов.
Или более надуманным
std::unordered_set<std::string> strings = /* something */;
auto hashed = strings.hash_function()("Any collision will do"); // O(1)
strings.erase(strings.begin(hashed), strings.end(hashed)); // O(distance(first, last))
Здесь мы удаляем элементы, которые имеют sh такие же, как "Any collision will do" , сложностью O(distance(first, last))