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.

Edited by therobot: n/a

8 Years
Discussion Span
Last Post by therobot

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 topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.