C++ Optimization in C++ Using efficient containers
Example
Optimizing by using the right data structures at the right time can change the time-complexity of the code.
// This variant of stableUnique contains a complexity of N log(N)
// N > number of elements in v
// log(N) > insert complexity of std::set
std::vector<std::string> stableUnique(const std::vector<std::string> &v) {
std::vector<std::string> result;
std::set<std::string> checkUnique;
for (const auto &s : v) {
// See Optimizing by executing less code
if (checkUnique.insert(s).second)
result.push_back(s);
}
return result;
}
By using a container which uses a different implementation for storing its elements (hash container instead of tree), we can transform our implementation to complexity N. As a side effect, we will call the comparison operator for std::string less, as it only has to be called when the inserted string should end up in the same bucket.
// This variant of stableUnique contains a complexity of N
// N > number of elements in v
// 1 > insert complexity of std::unordered_set
std::vector<std::string> stableUnique(const std::vector<std::string> &v) {
std::vector<std::string> result;
std::unordered_set<std::string> checkUnique;
for (const auto &s : v) {
// See Optimizing by executing less code
if (checkUnique.insert(s).second)
result.push_back(s);
}
return result;
}
