# Implementing a data structure that is a collection of sets

I'm trying to optimize my code (time optimization) based on this problem:

Let S be a set of strings. Each string in S is associated with a set of elements. Consider, for example, S = {"home", "tree"}. Implement a data structure that is a collection of sets and supports the operations Union, Move and Print. Initially, each string belongs to its own set. In particular, S1 = {'home'}, S2 = {'tree'}.

Allowed operations are:

• u tree house: Combine the house sets containing (S1) and shaft (S2).
• m tree house: Move the string in the set of tree house (S2).
• s house: Print the number of items in the home and the amount of length of the strings present.

The reading must be done by standard inputs. For each test, the first line contains the character and the two integers a and b (a, b > 0), where a represents the number of elements in S and b represents the number of operations to be performed. The second line begins with the character and followed by the list of strings in S. The remaining lines b contain the operations to be performed.

N.B.: The last line contains the string "<END>"

Here's my attempt:

int main() {

map<string, unsigned int> myMap;
map<unsigned int, pair<unsigned int, set<string> > > mapSet;

std::ios_base::sync_with_stdio(false);
string line;
string line1;
string line2;

int value = 0;
while (line.compare("<END>") != 0) {
cin >> line;
if (line.compare("i") == 0) {
cin >> line1 >> line2;

value = atoi(line1.c_str());
myMap.clear();
mapSet.clear();

}

if (line.compare("e") == 0) {

for (unsigned int i = 0; i < value; i++) {
cin >> line1;

myMap[line1] = i;
set<string> set;
set.insert(line1);
mapSet[i] = make_pair(line1.length(), set);

}
} else {
if (line.compare("m") == 0) {

cin >> line1 >> line2;

int index = myMap[line1];
int index2 = myMap[line2];

if (index != index2) {
if (mapSet[index].first > line1.length()) {
int newLength = mapSet[index].first;
mapSet[index].first = newLength - line1.length();
mapSet[index].second.erase(line1);
}
mapSet[index2].first += line1.length();
mapSet[index2].second.insert(line1);

myMap[line1] = index2;

}
}

else {
if (line.compare("u") == 0) {
cin >> line1 >> line2;

int index = myMap[line1];
int index2 = myMap[line2];

if (index != index2) {
if (mapSet[index].second.size()
< mapSet[index2].second.size()) {
set<string>::iterator it =
mapSet[index].second.begin();
string value;
int sum = mapSet[index].first
+ mapSet[index2].first;
mapSet[index2].first = sum;

while (it != mapSet[index].second.end()) {

value = (*it);
myMap[value] = index2;
mapSet[index2].second.insert(value);
it++;
}
mapSet.erase(index);
} else {
set<string>::iterator it =
mapSet[index2].second.begin();
string value;
int sum = mapSet[index].first
+ mapSet[index2].first;
mapSet[index].first = sum;

while (it != mapSet[index2].second.end()) {

value = (*it);
myMap[value] = index;
mapSet[index].second.insert(value);
it++;
}
mapSet.erase(index2);
}

}
} else {
if (line.compare("s") == 0) {

cin >> line1;

cout<<mapSet[myMap[line1]].second.size()<<" "<<mapSet[myMap[line1]].first;

}

}
}

}
}

return 0;
}

• Each time you call [] on the map, it performs an expensive search. Store the result in a reference. Jun 21, 2014 at 23:10

Before you attempt to optimize this, I would recommend refactoring it to be easier to follow. It may seem easier to just put everything into main() and not have to worry about functions, but that's actually worse. Just by looking at this, I wouldn't be able to tell what the code is doing nor how many different operations are being performed. There is a lot of nesting here, which can greatly complicate the code and even suggest longer runtime (especially nested loops and conditions in loops, which bring branch prediction into the equation).
Essentially, you can have three functions: one for each of the stated operations. They can all just be called in main() (unless one needs to call another), after initialing the data structures.