为什么C++向量排序效率不高？

Question

我在 CPP 上玩一些东西，遇到了一个向量运算，我想对向量进行排序。令我惊讶的是！我发现 sort() 函数没有按预期工作，或者可能是我做错了什么！？

我知道你们中的许多人可能会认为这是一个封闭的主题，但如果有人可以提供更多细节，那就太好了。

我有一个整数类型的向量，我将其传递给一个函数，然后在该函数内，我尝试对向量进行排序。

这是我的主要功能：

int main(int argc, char const *argv[]){
    vector<int> nums = {1,1,1,2,3,1,2};
    cout<<sortAndthenRemoveDuplicates(nums);
    return 0;
}

这是我调用 sort() 方法的函数

int sortAndthenRemoveDuplicates(vector<int>& nums){
    sort(nums.begin(), nums.end());
    for(int k : nums){
        cout<<k<<"\t";
    }
    return 1;
}

我正在从

#include<bits/stdc++.h>

导入排序。

Answer 1

sort 不会删除重复项，您可以使用 std::set 来做到这一点。

#include <vector>
#include <set>
#include <iostream>

// using namespace std; <== no don't do this

std::size_t sortAndthenRemoveDuplicates(std::vector<int>& nums) 
{
    // std::set will be sorted and will only contain unique values
    //https://en.cppreference.com/w/cpp/container/set
    std::set<int> unique_nums{nums.begin(),nums.end()}; // O(log n)
    nums = std::vector<int>{unique_nums.begin(),unique_nums.end()}; // O(n)
    return nums.size();
}

int main()
{
    std::vector nums{1,1,2,3,4,5,5,6,7,4,4,3,2,1};
    sortAndthenRemoveDuplicates(nums);
    for(const auto& num : nums)
    {
        std::cout << num << " ";
    }
}