Могу ли я создать unordered_map для размера целого числа до 10 ^ 9?

Question

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

вот часть моего code-

// Creating an unordered map-
unordered_map<long long int, long long int> example;

// increasing the counter of particular element-
example[element]++;

// checking wheather count of another element is zero or not, basically it is there or not
if(example[another_element]){
    // do something;
}

Я просто хочу знать, сработает ли оно для целого размера 10 ^ 9 или нет? Может кто-нибудь, пожалуйста, помогите.

Answer 1

Могу ли я создать unordered_map для размера целого числа до 10 ^ 9?

Да. И long long, и long гарантированно могут представлять все целые числа до 10 ⁹ . Неупорядоченная карта не влияет на это, согласно документации.

просто хочет хранить целые числа в контейнере и проверять, есть ли конкретное целое число в контейнере или нет?

Звучит так, будто вы хотите набор, а не карту.

---

Кроме того, не делайте этого:

if(example[another_element])

, чтобы проверить, является ли карта содержит элемент Это излишне вставляет элемент в карту, если он еще не существовал.

Answer 2

Вы можете использовать битовый набор размером 2 ^ 27 байт (128 МБ). Бит 1 в соответствующем индексе будет определять «элемент в наборе», а бит 0 будет «элемент не в наборе». Такой набор может быть легко написан как класс:

class bitset1G {
  public:
  bitset1G() { bzero(_data, sizeof(_data)); }
  void set(uint32_t x) { _data[x >> 5] |= (1 << (x & 0x1f)); }
  void clr(uint32_t x) { _data[x >> 5] &= ~(1 << (x & 0x1f)); }
  bool tst(uint32_t x) { return _data[x >> 5] & (1 << (x & 0x1f)); }
  private:
  int32_t _data[1 << 25]; // 1G bits
};