The C++ isn't so efficient as we think when it comes to STL?


  • 4
    Q

    I found that using the STL to solve some problem can be easy and elegant, however not so efficient. As this problem, it can be solved by C++ or python just in one line. The C++ in 52ms, python in 68ms. But, when I use C, just 12ms. (Note: I wrote the C by myself, the python and C++ is writen by others)

    python:

    class Solution:
    # @param {integer[]} nums
    # @return {boolean}
    def containsDuplicate(self, nums):
        return len(nums) > len(set(nums))
    

    C++:

    class Solution {
    public:
    bool containsDuplicate(vector<int>& nums) {
       return nums.size() > set<int>(nums.begin(), nums.end()).size();
        }
    };
    

    C:

    int cmp(const void* num1, const void* num2) {
    return *(int*)num1 - *(int*)num2;
    }
    
    bool containsDuplicate(int* nums, int numsSize) {
    int index = 0;
    
    qsort(nums, numsSize, sizeof(int), cmp);
    while (index < numsSize-1) {
        if (nums[index] == nums[index+1])
            return true;
        else
            index++;
        }
    
    return false;
    }

  • 0
    S

    isnt it asymptotically worse in C as you're using n*log(n) time for quick sort compared to the n time for the other languages . Also can you explain the use of the cmp function and why you are passing cmp and sizeof int in qsort.


  • 2

    You should probably use unordered_set in C++. Also, don't trust language comparisons here.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.