C set slower than Java TreeSet?-CodePudding

I was working on leetcode problem 792. Number of Matching Subsequences, and one of the initial solutions I came up with was to create a list of ordered sets. Then we can determine if a word is a subsequence of string s by trying to find the ceiling of the next available character of string word using the current index we are in of s. If we can reach the end of word, it is then a subsequence, otherwise, it is not.

I know this is not the optimal solution, but what I found surprising was the solution was able to pass in Java, but not with C (which is significantly slower). I'm still relatively new to C and in the process of learning it, so I'm not sure if there is some copying going on, or some other reason why my C solution would be much slower?

I have tried to change the way I was passing variables, and even tried to remove the isSub() function completely and write the logic in numMatchingSubseq(), however, it was still significantly slower than the Java implementation. Would anyone know why this is?

Java Solution

class Solution {
    public int isSub(List<TreeSet<Integer>> alpha, String word) {
        int N = word.length();
        int i = 0, j = 0;
        
        while (i < N) {
            TreeSet<Integer> st = alpha.get(word.charAt(i  ) - 'a');
            Integer e = st.ceiling(j);
            if (e == null) return 0;
            j = e   1;
        }
        return 1;
    }
    public int numMatchingSubseq(String s, String[] words) {
        List<TreeSet<Integer>> alpha = new ArrayList<TreeSet<Integer>>();
        
        for (int i = 0; i < 26; i  ) 
            alpha.add(new TreeSet<Integer>());
        for (int i = 0; i < s.length(); i  ) 
            alpha.get(s.charAt(i) - 'a').add(i);
        
        int ans = 0;
        for (String word : words) 
            ans  = isSub(alpha, word);
        return ans;
    }
}

C Solution

class Solution {
public:
    int isSub(vector<set<int>>& alpha, const string& word) {
        int i = 0, j = 0, N = word.size();
        while (i < N) {
            set<int> st = alpha[word[i  ] - 'a'];
            auto it = st.lower_bound(j);
            if (it == st.end()) return false;
            j = *it   1;
        }
        return true;
    }
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<set<int>> alpha(26);
        int M = s.size(), ans = 0;
        
        for (int i = 0; i < M; i  ) 
            alpha[s[i] - 'a'].insert(i);
        for (const auto& word: words) 
            ans  = isSub(alpha, word);
        
        return ans;
    }
};

CodePudding user response：

There is definitely some copying happening in the C version that isn't happening in the Java version. For instance st could be a reference

set<int>& st = alpha[word[i  ] - 'a'];