Thread: Set STL

1. Set STL

I have a few questions regarding sets maybe someone can answer them for me. First let me say i am trying to use a set to represent my hash table. First off i would like to know how to make a hash function of a specific size, such at 256. also i would like to know how to insert a number at a specific index. For example i have a hash function to evaluate that is f(k) = 10 and i have to create a program to run that then print the hash table. So if i have numbers like 50 100 120 they would all be entered into index 10 of the set but i don't know how to do that maybe someone can do that.

2. First let me say i am trying to use a set to represent my hash table.
Bad idea. set is typically a binary tree, and it cannot represent a hash table.

If you want to build your own hash table, use a vector as the base for the buckets.

3. CornedBee is correct, it makes little sense to use a set to hold your hash table. That said, you were asking about how to hold multiple numbers at the same index. If you did want/need to use set anyway, you would want to use multimap instead of set. That's because you have a key (in this case 10) and a value (in this case 50, 100 or 120) and you are allowed to have multiple entries with the same key. That's what multiset and multimap allow.

Since it is better to do this with a vector, you still have to handle collisions. One solution is to find the next empty slot after the index you need. So if f(50) is 10 and f(100) is also 10, but 50 is already at the index 10, then you'll have to put 100 at index 11 (assuming 11 is not full).

A common alternative that I like better would be to store a vector of lists (or a vector of vectors). So at index 10 would be a list that contains 50, 100 and 120. You can just walk that list to display them or to find a specific one.

4. its for a project i need to use set

5. Can you use multiset or multimap?

If not, then I guess you'd have to make your own class that stores the values that hash to the specific key (probably in a vector or list inside the class). You'd then have to make that class sortable (by the key only of course) before putting it in the set.

6. Originally Posted by DarkDot
its for a project i need to use set
Then tell your instructor that BY DEFINITION, a hash table cannot be implemented by a binary tree, which is what an STL set is. If your instructor disagrees, somebody should take their degree away.

Popular pages Recent additions