Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Tommy Carlier

Collection with 2 keys

This topic is 5331 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I want to create a sort of collection-class (in C#), where each element is a pair of an integer and a string. The collection should allow you to find an element as fast as possible, based on either the integer or the string. Working with it should look like:
myCollection c = new myCollection();
c.Add(1, "ABC");
c.Add(2, "DEF");
c.Add(3, "GHI");

myElement e1 = c.Find(2); // returns the element with integer 2
myElement e2 = c.Find("GHI"); // returns element with string "GHI"

int i = e1.Integer;
string s = e2.String;
 
I thought of doing this with 2 SortedLists, but that would double the memory usage (I''m talking about a collection with thousands of elements), and constant casting to string and int (boxing is quite expensive). Besides, I also need to find case-insensitive matches and partial matches (find first element of which the string starts with the given string). Not possible with SortedList. --- tommy online: http://users.pandora.be/tommycarlier

Share this post


Link to post
Share on other sites
Advertisement
Why not do:


std::list<pair<int, std::string> > mylist;

// Put in

pair<int, std::string> temp;
tmp.first = 1;
tmp.second = "ABC";

mylist.push_back(tmp);


That should cover your needs well.

Share this post


Link to post
Share on other sites
Thanks for your reply, but your solution is in C++, and I really need a C#-solution.
I could try to create such a list, but I need a really fast search-method for both the integer and the string. A linear search is just too slow.
The collection will contain thousands of these pairs, and I need to search on both the integer and the string, so sorting the list on the integer or the string won''t work.

---
tommy online: http://users.pandora.be/tommycarlier

Share this post


Link to post
Share on other sites
So your problem is to have a very fast lookup for two keys.

This means that hashing would be a better alternative.

1. calculate hash h of the pair (number, string)
2. use a hash table where each entry points to a linear list with the same h

When you need to find an element, you just calculate h the same way. Then you look into your hash table for the correct list. Search the list for the correct pair of (number, string). You can also convert the string to lowercase before calculating the hash, which will make your search caseinsensitive.

Remember that the hash function must be chosen correctly so you get an even distribution of hash values.

Share this post


Link to post
Share on other sites
I need to search with an integer OR a string. There has to be a method to search with integers, and a method to search with strings. I never know both.
Example:

myElement = myCollection.Find(4567);
myElement2 = myCollection.Find("abcde");
string s = myElement.StringValue;
int i = myElement2.IntegerValue;


---
tommy online: http://users.pandora.be/tommycarlier

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!