How to use a substring as key for unordered_set::erase

Question

The cplusplus.com page about unordered_set member function "erase" has this sample code that removes the set element "France" when an exact matching string is supplied.

[EDIT: I cite this code for its brevity and clarity. My actual project uses unordered_set for reasons not necessarily present in this example. However a solution that works on this sample code would work in my project.]

How would I modify this to remove all the elements that have matches to a smaller string?

For example, removing all the elements with an "F" as the first character. [EDIT: targeting the first character is merely an example. ]

Is there some way to access an iterator value to do something like...

myset.erase( myset[member currently being evaluated].substr(0,1)=="F") ?

// unordered_set::erase
#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset =
  {"USA","Canada","France","UK","Japan","Germany","Italy"};

  myset.erase ( myset.begin() );                    // erasing by iterator
  myset.erase ( "France" );                         // erasing by key
  myset.erase ( myset.find("Japan"), myset.end() ); // erasing by range

  std::cout << "myset contains:";
  for ( const std::string& x: myset ) std::cout << " " << x;
  std::cout << std::endl;

  return 0;
}

Answer 1

Is there some way to access an iterator value to do something like...

myset.erase( myset[member currently being evaluated].substr(0,1)=="F") ?

The short answer is: no. Especially with an unordered set/map which, by definition, does not order its contents in any particular way. That's what makes it an unordered set/map, after all.

Your only option is to manually iterate over all keys in the set or map. The iteration will not be in any particular order. Check each key, and if it meets the prescribed condition the key and its value gets removed from the set/map. This logic must be implemented manually.

In C++20 unordered map/sets have an erase_if() method that will, somewhat, help with this task. You provide the appropriate predicate and it does all the work. But, underneath the scene, it still does exactly that: iterate over the map/set, one key at a time.

There are no alternatives. There are no shortcuts. And no way around it. It all goes down how unordered containers work on a fundamental level. So, when it comes to unordered container the only way to do it is to do it yourself, manually, one key at a time.

One part of learning C++ is knowing and understanding what each container does, and how it works. You don't want to use an unordered set or map if it's important for you to have a container where this operation can be done in a reasonably optimal manner. Maybe you want to use a different container, that will do this better. The other container might do other things worse, that are important to you, so you have to pick the lesser of two evils, and make an intelligent decision.

This is why the C++ library has several different kinds of containers. They all are structured differently, and work in fundamentally different ways. An unordered container does not work in a way that makes it possible to implement the described operation in an optimal way.

Answer 2

As of C++20 there was an algorithm called std::erase_if() added to the standard library that is specialized for each of the data structures in the standard library. This is able to call the containers .erase() method on any elements in the container given a certain predicate is true.

The efficiency of the algorithm is dependent on which data structure you're erasing from (more details on the cppreference page linked below).

As for checking the first letter of the string and erasing based on that, your predicate can be a lambda that uses the C++20 std::basic_string (aka, std::string) string method .starts_with() which returns a boolean if the string starts with the substring provided. I made a godbolt instance derived from the example you provided that utilizes these utilities.

Links:

• std::unordered_map
• std::erase_if (for std::unordered_map)
• std::basic_string()
• std::basic_string::starts_with()
• lambda expressions

Answer 3

For that to work you need your strings to be sorted ie use std::set instead of std::unordered_set. For example if you want to remove all countries, that start with "F" you can do this:

  std::set<std::string> myset =
  {"USA","Canada","France","UK","Japan","Germany","Italy", "Finland"};
 
  myset.erase ( myset.lower_bound( "F" ), myset.lower_bound( "G" ) );
 

Live example

If you need to access your data both ways, you may use Boost.MultiIndex but that has some learning curve.