如何从 C++ 中 O(n) 的关联 NxN 矩阵中删除行和列？

Question

我有一个关联的 NxN 矩阵和一个包含所有列的向量：

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

一个元素看起来像这样：A["abc"]["bcd"] = 2

我想在 O(n)

中删除“abc”行（基本上 A["abc"]）和“abc”列（基本上 A[*]["abc"]）

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"); 
}

这有 O(n*log n) 运行时间。是否可以在 O(n) 中完成？

Answer 1

您可以使用 std::map<std::pair<std::string, std::string>, int>，其中字符串对是行值和列值。

然后您可以使用适用于 std::map 的自定义 std::erase_if 算法，该算法在 O(n) 时间内运行：

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

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