C ++ / JAVA: efficiently finding a collection in a collection containing a given value

Question

Suppose we have a collection of mutually exclusive sets
{A, B, C, D}, where A = {1,2,3}, B = {4,5,6}, C = {7,8,9}, D = {10,11,12}
And given the value of Z , for example, 3, I expect it to return the index of the set A, because A has 3 as a member.

The question is how could I use C ++ or JAVA effectively.

My current solution: Store A, B, C, D as a HashSet (or unordered_set in C ++) in the container and skip each set until the set containing Z.
The problem is that the complexity is O (n) for the number of sets stored in the container.

Is there a way (or any data structure for storing these sets) to do this faster than O (n)?

Answer 1

You can create a map that displays the value for setting id (for example, it should display 1, 2, 3 in A, 4, 5, and 6 to B, etc.). With a hash map, it can work on average O (1).

Answer 2

As a quick heuristic that can help try to use the most commonly used settings in the list. It is likely that most of the time there will be one or two sets that will be returned to 80-90% of requests.

int getSetIndex(Object elem) { Set first = sets.get(0); if (first.contains(elem)) // if "index of the set" has some special meaning in your question, // you should save it along with the set return first.index(); for (int i = 1; i < sets.size(); i++) { Set cur = sets.get(i); if (cur.contains(elem)) { sets.set(i, sets.get(i - 1)); sets.set(i - 1, cur); return cur.index(); } } return -1; // not found }