найти ключ на карте

Question

У меня есть карта, которую я объявил следующим образом:

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. Я использую карту, чтобы попытаться выяснить, не связаны ли два набора или нет, и для того же самого я использую карту и два вектора для хранения входных данных. Это потертый в любом случае? Какую другую структуру данных я должен использовать?

Answer 1

Вы можете использовать if (index.find(key) == index.end()), чтобы определить, присутствует ли ключ. Используя index[key], вы создаете по умолчанию новое значение (в этом случае вы вызываете bool(), и оно печатается как 0.) Вновь созданное значение также вставляется в карту (т. Е. index[key] равно в это дело до index.insert(std::make_pair(key, bool()).)

Можно использовать две структуры данных для одних и тех же данных. Однако, есть ли необходимость использовать карту, не будет ли набор достаточным в вашем случае использования? То есть если они представляют ключ, значение равно true, и false в противном случае?

Answer 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::set s, вы должны убедиться, чтодиапазоны упорядочены.

Если вы хотите повысить эффективность, вы можете реализовать алгоритм для 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;
}

Answer 3

1. Вы можете использовать index.find(key) != index.end() или index.count(key) > 0
2. В зависимости от диапазона элементов индекса, может быть целесообразно использовать растровое изображение (имеет смысл только для разумно небольшого диапазона возможных элементов индекса. Будет делать проверки на несвязность супер легкими и эффективными) или использовать набор вместо карта (карта хранит дополнительные bools, которые на самом деле не нужны). Набор также предлагает методы count(key) и find(key)

Answer 4

1, используйте index.count(y).Он более лаконичен и эквивалентен index.find(y) != index.end(), за исключением того факта, что это целое число 1 или 0, тогда как, конечно, != дает вам значение bool.

Недостатком является то, что count потенциально меньшеэффективнее для multimap, чем для map, поскольку может потребоваться учитывать более одной записи.Поскольку вы не используете multimap, нет проблем.

2, вы можете отсортировать оба вектора и использовать std::set_intersection, но это не идеально подходит, если все, что вас волнует, это то, что пересечение пустое илине.В зависимости от того, откуда поступает ввод, вы можете избавиться от обоих векторов и просто создать map при переходе от первой загрузки ввода, а затем сравнить каждый элемент второй загрузки ввода с ним.Наконец, используйте set вместо map.

Answer 5

Использовать map :: find .