我可以为最大 10^9 的整数大小创建 unordered_map 吗？

Question

我正在解决一个需要使用散列的问题，我只想将整数存储在容器中并检查容器中是否存在特定整数？

这是我的一段代码-

// 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

Can I create unordered_map for size of integer upto 10^9?

是的。 long long 和 long 都保证能够表示最大为 10⁹ 的所有整数。根据文档，无序地图对此没有影响。

just want to store integers in a container and check whether a particular integer is there in the container or not?

听起来你想要一套而不是地图。

另外，不要这样做：

if(example[another_element])

检查地图是否包含元素。这会不必要地将一个元素插入到地图中，如果它还不存在的话。

Answer 2

您可以使用大小为 2^27 字节 (128mb) 的位集。相应索引中的位 1 将定义 "element within set"，位 0 将定义为 "element not in set"。这样的集合可以简单地写成class，比如：

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
};

我可以为最大 10^9 的整数大小创建 unordered_map 吗？

Can I create unordered_map for size of integer upto 10^9?

c++

algorithm

unordered-map

data-structures

c++14