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.

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.

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.

This article has been dead for over six months. Start a new discussion instead.