3

I have to insert K numbers which may range from 0 to 10^9. Later i want to know whether i have inserted a particular number or not. Here K ranges from 0 to 10^5.

Both the insertion and deletion have to be in constant time. I have looked at the C++ STL unordered_map. But unordered_map requires two parameters. I just want to insert a number not a key-value pair.

I could simply use an array of bools like

bool numberExists[1000000000];

But initialising this to false will take a lot of time. As is said i wanted constant time insertion and lookup.

What data structure should i use...?

Rohith R
  • 1,309
  • 2
  • 17
  • 36
  • why don't you use `std::vector` – Ankur Jan 06 '15 at 10:07
  • @Shan i believe vector supports only constant time insertion not lookups.... – Rohith R Jan 06 '15 at 10:08
  • @PRP it's constant time lookup by index. And as your key will be the index, that's constant time lookup. Pretty hefty on memory though. – BoBTFish Jan 06 '15 at 10:11
  • who said my key will be my index....? – Rohith R Jan 06 '15 at 10:12
  • Uhm, you did? Insert the number 999: `vals[999] = true;`. Check if you have inserted number 999: `if(vals[999]) ...`. But again, probably not ideal from a memory point of view for your large numbers. – BoBTFish Jan 06 '15 at 10:13
  • yea...butmemory complexity will be too high right...? – Rohith R Jan 06 '15 at 10:14
  • What is "memory complexity"? (I'm not necessarily supporting `std::vector` as a solution to your specific problem, just correcting your original misapprehension about it) – BoBTFish Jan 06 '15 at 10:14
  • @BoBTFish the limiting behaviour of how the number of words used grows with, in this case, items inserted – harold Jan 06 '15 at 10:15
  • @harold The number of elements is fixed: 10^9. So I don't think that can be what he(?) means. – BoBTFish Jan 06 '15 at 10:17
  • You could look at it that way. Time complexity is also O(1) then, no matter what you do. Any discussion about what's better or worse becomes meaningless. That's not a very useful analysis, so for that purpose we should probably assume that the fixed limit does not exist. – harold Jan 06 '15 at 10:20

3 Answers3

6

But unordered_map requires two parameters. I just want to insert a number not a key-value pair.

Then you should use std::unordered_set<int>: it offers constant-time lookup, and amortized constant time insertion and deletion.

If you are looking for worst-case constant time insertion and lookup, you need std::vector<bool> or even std::bitset<N>. Note, however, that the time it takes to iterate over all its elements is O(MAX), not O(N), which could be significantly worse.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
0

You need hashset and in c++ it is implemented as : unordered_set. (manual)

Note that if you keep adding elements each add is not guaranteed to be constant, because if threshold is reached then rehash of all elements is done. However for simplicity sake it is very close to that goal.

Margus
  • 19,694
  • 14
  • 55
  • 103
  • In addition take a look at: http://stackoverflow.com/questions/200384/constant-amortized-time – Margus Jan 06 '15 at 10:17
0

You can use the memory and not have to zero-initialize it.

This question is essentially a dupe of Data structure that supports the following in O(1) time: initialization, insertion, deletion, finding an element, deleting all elements

Community
  • 1
  • 1
privatedynamicjunk
  • 1
  • If you think it's a duplicate, you should probably post a comment under the question, not make an answer out of it. – Reti43 Jan 06 '15 at 13:46