我试图找到重复的字符串实例,其中我有一个~250万字符串的向量.~
目前我使用的东西如下：@H_403_3@
std::vector<string> concatVec; // Holds all of the concatenated strings containing columns C,D,E,J and U.
std::vector<string> dupecheckVec; // Holds all of the unique instances of concatenated columns
std::vector<unsigned int> linenoVec; // Holds the line numbers of the unique instances only
// Copy first element across,it cannot be a duplicate yet
dupecheckVec.push_back(concatVec[0]);
linenoVec.push_back(0);
// Copy across and do the dupecheck
for (unsigned int i = 1; i < concatVec.size(); i++)
{
bool exists = false;
for (unsigned int x = 0; x < dupecheckVec.size(); x++)
{
if (concatVec[i] == dupecheckVec[x])
{
exists = true;
}
}
if (exists == false)
{
dupecheckVec.push_back(concatVec[i]);
linenoVec.push_back(i);
}
else
{
exists = false;
}
}
这对于小文件来说很好,但是由于嵌套的for循环和dupecheckVec中包含的字符串数量的增加,文件大小显然会花费很长时间.@H_403_3@
解决方法
如果你不介意重新排序向量,那么这应该在O(n * log(n))时间内完成：
std::sort(vector.begin(),vector.end()); vector.erase(std::unique(vector.begin(),vector.end()),vector.end());
为了保留顺序,您可以改为使用(行号,字符串*)对的向量：按字符串排序,使用比较字符串内容的比较器进行单一化,最后按行号排序,沿着以下行：@H_403_3@
struct pair {int line,std::string const * string};
struct OrderByLine {
bool operator()(pair const & x,pair const & y) {
return x.line < y.line;
}
};
struct OrderByString {
bool operator()(pair const & x,pair const & y) {
return *x.string < *y.string;
}
};
struct StringEquals {
bool operator()(pair const & x,pair const & y) {
return *x.string == *y.string;
}
};
std::sort(vector.begin(),vector.end(),OrderByString());
vector.erase(std::unique(vector.begin(),StringEquals()),vector.end());
std::sort(vector.begin(),OrderByLine());
