How to delete rows and columns from an associative NxN matrix in O(n) in C++?

Question

I have an associative NxN matrix and a vector containing all columns:

std::map<std::string,std::map<std::string,int>> A;
std::vector<std::string> columns; //this has size n

An element would look like this: A["abc"]["bcd"] = 2

I want to remove the row "abc" (so basically A["abc"]) and the column "abc" (so basically A[*]["abc"]) in O(n)

A.erase("abc"); //this is O(log n)

for (int i = 0; i < words.size(); ++i) //this is O(n*log n)
{
    A[words[i]].erase("abc"); 
}

This has O(n*log n) runtime. Is it possible to do it in O(n)?

Answer 1

You could use a std::map<std::pair<std::string, std::string>, int>, where the pair of strings are the row and column values.

Then you can use the custom std::erase_if algorithm that works on a std::map, which runs in O(n) time:

std::erase_if(A, [](const auto& item) {
    auto const& [key, value] = item;
    return key.first == "abc" or key.second == "abc";
});