通过调用 transform 方法对齐持有不同类型的两个容器

Question

我有两个 STL 容器（目前是矢量），其中包含不同类型的对象。这两种类型都有一个返回标识符的方法，该标识符可用于 "compare" 不同的类型。两个容器中的元素都没有排序，比较两个标识符可能是 "expensive"（例如字符串比较）。两个容器的大小应该相似，每个容器可能包含 << 100 个元素。

我现在想做以下事情：

情况一：如果容器 A 和容器 B 都包含标识符比较相等的元素，我想调用容器 A 的元素的方法。
情况2：如果容器B包含一个元素，其标识符在A中没有对应的元素，我想创建这样一个元素并将其插入到A中。
情况 3：如果容器 A 包含一个元素，其标识符在 B 中没有包含相应的元素，我想对该元素调用一个方法并将其从 A 中删除。

所以毕竟它应该持有

两个容器中的元素数量应该相等
容器 B 未修改
对于容器 A 中的每个元素，容器 B 中应该有一个元素，其标识符比较相等，反之亦然

有没有有效的方法来做到这一点？我只能想到一个运行时复杂度为 O(2*n*m) 的算法，这听起来太多了。

std::vector<T1> containerA;
std::vector<T2> containerB;

for(auto &elementA : containerA)
{
  std::vector<T2>::iterator bIter = std::find_if(containerB.begin(), containerB.end(), [elementA](const T2 &elementB){ return (elementA.getId() == elementB.getId()); })
  if(bIter == containerB.end())
  {
    // case 3
    elementA.foo();
    // remove elementA from containerA
  }

  // case 1
  elementA.bar((*bIter));
}

for(const auto &elementB : containerB)
{
  std::vector<T1>::iterator aIter = std::find_if(containerA.begin(), containerA.end(), [elementB](const T1 &elementA){ return (elementA.getId() == elementB.getId()); })
  if(aIter == containerA.end())
  {
    // case 2
    T1 newElement(elementB);
    containerA.push_back(newElement);
  }
}

Answer 1

假设 A sum B 上存在总订单，您可以尝试以下操作：

设A'=sorted A
设B'=sorted B
对于 B' 中的每个 b 从 A' 中找到 a（因为 A' 已排序，我们可以使用二进制搜索）使得 b = a.如果不存在这样的元素，则向 A 添加新元素，否则对 (b, a)
对于 A' 中的每个 a 从 B' 中找到 b（因为 B' 已排序，我们可以使用二进制搜索）这样 a = b.如果不存在这样的元素，则在 A 中删除标记 a 否则对 (a, b)
从 A

时间复杂度为O(nlogn)

通过调用 transform 方法对齐持有不同类型的两个容器

Align two containers holding different types by calling transform methods

c++

algorithm

stl

time-complexity