   lookup tables
  I come across this problem a lot. I have 2 huge lists of values (say numbers for simplicity). In each list, the number is associated with some value, say some text. So you got two big lists like this:list 1:32112 blah blah43332 hello this is fun24324 why am i 54234 actually typing89222 words when22222 note that this text ...list 2: 12311 I could just 54322 do this sfd74433 sdfsdfsdaf92432 sdfdsfsdf22222 ... is different from this03223 sdfdsfdThe lists are very long, in the thousands each. My task is always to find every match. Every time a number in list 1 is the same as a number in list 2, i print out both of the associated descriptions. What i always end up doing because its the easiest to code, is just brute force for loops like this:for each item in list 1  for each item in list 2    if they match print them bothI know this is an O(n^2) algorithm and is probably the least clever way to do it. What would be a better (the best) way? Should I sort each list? that would help because it would only require one pass through each list wouldnt it? what if i put both lists into a hash? does that help any?Also, how do the following factors matter? :- there are some numbers not necessarily in both lists- some numbers may appear more than once in one or both liststhanks. 
  My first instinct was to use a self-sorting linked list, but I may have thought up a better solution.  Have you tried trees for one or both of the lists?  Then you could take the value you''re searching for and get to it very quickly.  I don''t know how many branches you''d want the tree to have, but you could do it by halves or something.  All numbers about 65535 would be on one leg, the rest would be on the other, and further subdivide in the next level...   --------------------You are not a real programmer until you end all your sentences with semicolons; (c) 2000 ROAD Programming You are unique.  Just like everybody else."Mechanical engineers design weapons; civil engineers design targets.""Sensitivity is adjustable, so you can set it to detect elephants and other small creatures." -- Product Description for a vibration sensorYanroy@usa.com ;  Look up tables (LUTs) are nice and fast but require all the indexing numbers to be closely packed and without duplicates (typically sequential). Often this is ok since you''re free to use any old numbers due to #defining them to be some more friendly looking variables.As soon as you move away from close packed indices, a hashmap is a much better choice. Just associate your keys with their value and you bearly have to lift a finger. The algorithm is usually pretty good as well, so assuming that you don''t get too many collisions it will be somewhere around O( log(n) ) ;  maybe lookup table was the wrong term to use. Lookup tables are for when you have a key you want to LOOK UP and then you look it up in the table and get the associated value. What im doing is sort of different. I want to find every single match between two tables. Im not looking up a specific value, im matching (or trying to match, because there may not be a match) every value in both tables. Think of matching your socks up after youve done a load of laundry. Do you say "I want to find the sock that goes with this one" ? Well sort of but not really. You sort of want to do that FOR EACH sock, and say something more like "I want to match all of the socks with all of the socks to find each pair". I was wondering if there was an especially clever way to do this, or if i just need to ask "I want to find the sock that goes with this one"  once FOR EACH SOCK.? ;  Sounds uncannily like a JOIN operation on a couple of database tables, but unless you want to start using an existing database, i''d still say the hashmap is a good way of solving this.You could do it in line of Squ, whats it actually for? ;  Depending on how big the entries are(You shouldn''t do this for huge lists of 1 byte values) a binary search tree is best.There''s an excellent article about them available on gamedev, especially handy since you use values in some way to identify the chars, which saves even more cycles, thus increases speed. ;  merge sort them then traverse the resulting list.or even simpler just sort both lists have a pointer into eachthat starts from the begining then just go something like while(ptr1 < end1 && ptr2 < end2){  while(*ptr1 < *ptr2 && ptr1 < end1)   ++ptr1;  if(*ptr1 == *ptr2)    //print both strings  while(*ptr2 <= *ptr1 && ptr2 < end2)    ++ptr2;}you get the idea? sort then start traversing them always stepping the one thats behind then switching until it catches up, rinse and repeat. ;  the complexity of that should endup beingn == combined size of listsO( n log n + n) and that simplifies to O(n log n) if im not mistaking ;  Use hash tables for O(N + M), in which N is the number of items in list1, M in the other. That''s the average case though, worst case is that an asteroid hits earth and you die with your family. ;#include <iostream>#include <string>#include <map>int main() {  // Maps are sorted so searching for stuff in them is fairly fast.  typedef std::map<int, std::string> ourmap;  ourmap list1, list2;  list1[32112] = "blah blah";  list1[43332] = "hello this is fun";  list1[24324] = "why am i";  list1[54234] = "actually typing";  list1[89222] = "words when";  list1[22222] = "note that this text";  list2[12311] = "I could just";  list2[54322] = "do this sfd";  list2[74433] = "sdfsdfsdaf";  list2[92432] = "sdfdsfsdf";  list2[22222] = "... is different from this";  list2[ 3223] = "sdfdsfd";    for(ourmap::const_iterator list1entry = list1.begin(); list1entry != list1.end(); ++list1entry)   {    ourmap::const_iterator list2entry = list2.find(list1entry->first);    if(list2entry != list2.end())std::cout << "#" << list1entry->first << ": " << list1entry->second << " --> " << list2entry->second << std::endl;   } }Output:#22222: note that this text --> ... is different from this