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

  associative, c++, matrix, runtime

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)?

Source: Windows Questions C++

LEAVE A COMMENT