Карта существования в C ++

Question

Я хочу что-то вроде std :: map , но я только хочу увидеть, существует элемент или нет, мне на самом деле не нужен ключ И значение. Что я должен использовать?

Answer 1

Похоже, вам нужен std :: set .

Answer 2

Если вы хотите того же типа поведения, что и std::map, тогда вы хотите std::set.

Если вы смешиваете операции вставки / удаления и запроса, то std::set, вероятно, является лучшим выбором. Однако, если вы можете сначала заполнить набор, а затем следовать за ним с запросами, возможно, стоит посмотреть std::vector, отсортировать его, а затем использовать двоичный поиск для проверки существования в векторе.

Answer 3

Если вам действительно нужен только существование, а не приказ, вам нужен unordered_set. Он доступен у вашего любимого поставщика C ++ 0x или boost.org .

Answer 4

Вам, вероятно, стоит взглянуть на stl::set, что вам нужно. A stl::bitset является еще одним вариантом.

Это будет зависеть от того, как вам нужно использовать информацию, которая определит, какой из них лучше. A set - это отсортированная структура данных, время вставки, поиска и удаления занимает O (LOG N). Но если вам нужно перебрать по всем значениям, которые вы пометили как "существование", тогда set - путь.

Если вам нужно только отметить и найти факт , что что-то является членом набора, тогда bitset может быть лучше для вас. Для вставки, поиска и удаления требуется только O (1), но вы можете собирать только int значений. Итерирование по всем отмеченным значениям потребует O (N), так как вам нужно пройти весь набор, чтобы найти элементы, которые установлены в true. Вы можете использовать его совместно с stl :: map для сопоставления значений, которые у вас есть, с числовыми значениями, необходимыми bitset.

Посмотрите на операции, которые вам нужно выполнить со значениями в вашем наборе, и вы сможете выбрать соответствующую структуру данных

Answer 5

Если ваши данные являются числовыми, вы можете использовать std :: vector, оптимизированный для пробела:

D:\Temp>type vectorbool.cpp
#include <iostream>
#include <vector>

using namespace std;

int main() {
        vector<bool> vb(10);
        vb[5] = true;

        for (vector<bool>::const_iterator ci = vb.begin(); ci != vb.end(); ++ci) {
                cout << *ci << endl;
        }
}

D:\Temp>cl /nologo /W4 /EHsc vectorbool.cpp
vectorbool.cpp

D:\Temp>vectorbool.exe
0
0
0
0
0
1
0
0
0
0

Answer 6

Если ключом является значение, то вы также можете рассмотреть «фильтр Блума», а не набор.

Answer 7

Вы можете продолжать использовать std :: map для желаемой цели.

Чтобы проверить, существует ли определенный элемент (типа ключа) на карте или нет, вы можете использовать следующий код:

if (mapObj.count(item) != 0)
{
   // item exists
}

Как уже было сказано ранее, std :: set также сделает эту работу. Интересно, что и сет, и карта внутренне представлены как деревья.