Avoiding O(n^2)

[therobot]

I'm working with some objects given to me by the API for an architectural modeling program. When navigating the model, I get a set of Component objects. One of the data members of these Component objects is a set of Interface objects.

I'm looking to search for a specific Interface object within these, but am constrained by the fact that I have to search on the Interface object's name, not on the object itself. I'm trying to figure a good way to do this not in O(n^2). This is an example snippet.

for each(Component comp in componentSet)
{
	interfaceSet = comp.getInterfaces();
	for each(Interface inter in interfaceSet)
	{
		if (inter.getName().compare("FOO") == 0)
			... do something
	}
}

I keep trying different methods like throwing things into maps, etc, but keep coming back to the fact that I always need to keep interfaces coupled with their respective components, and for every component in the set, I need to search every interface in their respective sets.

[mrnutty]

The data structure you need is hashmap or hashtable. Like always, boost got you covered. Look into their hashtable if you want. In a typical hashtable implementation, searching is O(1), that is, its constant.

If you want to stay with stl, you can use std::map. Their search operation is usually logarithmic in size.

[therobot]

The data structure you need is hashmap or hashtable.

I was looking at that, and wondering though, since I'd have to move everything from a set to the hash_map, because the functions I'm calling return only sets, wouldn't I just incur the O(n^2) there? For each component, for each interface, add to map.