C++ set slower than Java TreeSet?

Question

我正在研究leetcode问题792。匹配子序列的数量，我想到的一个最初的解决方案是创建一个有序集合的列表。然后我们可以确定一个词是否是字符串s的子序列，通过使用s的当前索引来尝试找到字符串word的下一个可用字符的上限。如果我们能到达word的末尾，那么它就是子序列，否则，它不是子序列。

我知道这不是最优的解决方案，但我发现令人惊讶的是解决方案能够在Java中传递，但不能在c++中传递(这要慢得多)。我对c++还是个新手，在学习的过程中，所以我不确定是否有一些复制，或者其他原因导致我的c++解决方案会慢得多?

我试图改变我传递变量的方式，甚至试图完全删除isSub()函数并在numMatchingSubseq()中编写逻辑，然而，它仍然比Java实现慢得多。有人知道这是为什么吗?

Java解决方案

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 + +解决方案

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

Answer 1

在c++版本中肯定会发生一些在Java版本中没有发生的复制。例如，st可以是一个引用

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