使用高效的容器

通过在正确的时间使用正确的数据结构进行优化可以改变代码的时间复杂度。

// 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;
}

通过使用一个使用不同实现来存储其元素的容器（散列容器而不是树），我们可以将我们的实现转换为复杂度 N.作为副作用，我们将调用 std::string 的比较运算符，因为它只有在插入的字符串最终应该在同一个存储桶中时才需要调用它。

// 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;
}