Thread: Set STL

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    109

    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. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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. #4
    Registered User
    Join Date
    Mar 2007
    Posts
    109
    its for a project i need to use set

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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. #6
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by DarkDot View Post
    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 subscribe to a feed

Similar Threads

  1. optimising program
    By SONU in forum C Programming
    Replies: 1
    Last Post: 05-18-2008, 10:28 AM
  2. STL Set erase()
    By R.Stiltskin in forum C++ Programming
    Replies: 11
    Last Post: 03-27-2007, 08:09 AM
  3. 6 measly errors
    By beene in forum Game Programming
    Replies: 11
    Last Post: 11-14-2006, 11:06 AM
  4. The new FAQ
    By Hammer in forum A Brief History of Cprogramming.com
    Replies: 34
    Last Post: 08-30-2006, 10:05 AM
  5. OpenGL Window
    By Morgul in forum Game Programming
    Replies: 1
    Last Post: 05-15-2005, 12:34 PM