使用高效的容器

通過在正確的時間使用正確的資料結構進行優化可以改變程式碼的時間複雜度。

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