STL containers. Search performance

[luirro777]

Hello

I'd like to know which STL container has the best performance in doing searching of elements.

Thanks

[aquaz]

std::unordered_set of you don't care of the order. std::set otherwise

[Gaminic]

Depends on what kind of searches you're talking about. Exact key matches? Order-measure searches? Min/max extraction? Be more specific!

[luirro777]

OK

I'm try¡ng to implement a routing table. I'm using a list. Every node has 3 fields:

+ net_address (unsigned int)
+ net_mask (unsigned int)
+ port (int)

the lookup function takes an IP address (ip_address, unsigned int) as an argument and does a bitwise AND between ip_address and net_mask. If the result is equal to net_address, the function returns the port value. Otherwise ¡, it continues the lookup (by incrementing an iterator).

Thanks

[luirro777]

Oh... I forgot to mention that the list is ordered from highest to lowest value of net_mask.

[bartoli]

Do you know wether the input IP_address is always in the list, or never? If yes, do you already have the iterator to this one? It could give you a good starting position for your search. Then browse the list in both directions starting from there until you find an element that has a different net_mask.
If not, find a first element of a corresponding net_mask and do the same from this position

[luirro777]

The IP_address is not in the list. This is an attemp to implement a prefix-match lookup. In doing so:

1 . I take de IP_address (actually, it's a destination address)
2 . In every node, I do a bitwise AND between IP_address and net_mask.
3 . If the result is equal to net_address, there's a match!!
4 . IF not, I continue to the next node (by means of an iterator)

Regards!!

[JLBorges]

The BSD 4.3 implementation of the ARP cache (reduced radix tree) is what is normally used for ip routing tables.

Keith Sklower's original paper on BSD 4.3
http://ece.ut.ac.ir/classpages/F83/Advanced%20Computer%20Networks/PAPERS/LOOKUP/routing.pdf
Several improvements have been made over the years, but the basic ideas are still what it was in BSD 4.3.

If you are seriously into this, The University of Tehran has a repository of some classic papers on ip lookup:
http://ece.ut.ac.ir/classpages/F83/Advanced%20Computer%20Networks/Lookup_Papers.htm