0

我有一张我声明如下的地图：

map<int, bool> index;

我将值插入到地图中：

int x; cin>>x;
index[x]=true;

然而，

cout<<index[y]; // for any number y not in指数gives me 0

  1. 当我在检查地图中不存在的键时获得值0时，如何可靠地找出地图中是否存在键？
  2. 我正在使用地图来尝试找出两个集合是否不相交，同样我正在使用地图和两个向量来存储输入。这有什么破旧的吗？我应该使用其他一些数据结构？
4

5 回答 5

8

您可以使用if (index.find(key) == index.end())来确定是否存在密钥。使用index[key]你默认构造一个新值（在这种情况下，你调用bool()，它被打印为0。）新构造的值也被插入到地图中（即index[key]在这种情况下等于index.insert(std::make_pair(key, bool())。）

对相同的数据使用两个数据结构是可以的。但是，是否需要使用地图，在您的用例中设置是否足够？即，如果它们的键是存在的，则值为真，否则为假？

于 2011-07-27T17:50:14.580 回答
2

要确定两个集合（给定为std::set）是否不相交，您可以简单地计算它们的交集：

std::set<T> X, Y; // populate
std::set<T> I;

std::set_difference(X.begin(), X.end(), y.begin(), y.end(), std::back_inserter(I));

const bool disjoint = I.empty();

如果你的容器不是std::sets，你必须确保范围是有序的。

如果你想提高效率，你可以实现算法，set_intersection一旦你有一个共同的元素就停止：

template <typename Iter1, typename Iter2>
bool disjoint(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2)
{
  while (first1 != last1 && first2 != last2)
  {
    if (*first1 < *first2) ++first1;
    else if (*first2 < *first1) ++first2;
    else { return false; }
  }
  return true;
}
于 2011-07-27T17:58:31.680 回答
1

使用map::find。

于 2011-07-27T17:49:22.830 回答
1

1、使用index.count(y)。它比 更简洁且等效于index.find(y) != index.end()，除了它是整数 1 或 0 之外，当然!=给你一个布尔值。

缺点是它的count效率可能低于，因为它可能需要计算多个条目。由于您没有使用 a ，所以没问题。multimapmapmultimap

2，您可以对向量和使用进行排序std::set_intersection，但如果您只关心交集是否为空，则它不是一个完美的选择。根据输入的来源，您可能能够摆脱这两个向量，并在map您从输入的第一个负载开始时构建 a，然后检查第二个输入负载的每个元素。最后，使用 aset而不是 a map。

于 2011-07-27T17:55:52.813 回答
1
  1. 你可以使用index.find(key) != index.end()或index.count(key) > 0
  2. 根据索引项的范围，使用位图可能会更好（仅对合理的小范围可能的索引项有意义。将使检查不相交超级容易和有效）或使用 a set 而不是 map ( map 存储不需要的其他布尔值）。一组还提供方法count(key)和find(key)
于 2011-07-27T17:56:06.770 回答