c – 检查大型字符串向量中的重复项

我试图找到重复的字符串实例,其中我有一个~250万字符串的向量.~

目前我使用的东西如下：

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中包含的字符串数量的增加,文件大小显然会花费很长时间.

在大文件中执行此操作可能不那么可怕？

解决方法

如果你不介意重新排序向量,那么这应该在O(n * log(n))时间内完成：

std::sort(vector.begin(),vector.end());
vector.erase(std::unique(vector.begin(),vector.end()),vector.end());

为了保留顺序,您可以改为使用(行号,字符串*)对的向量：按字符串排序,使用比较字符串内容的比较器进行单一化,最后按行号排序,沿着以下行：

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());

c – 检查大型字符串向量中的重复项

解决方法

猜你在找的C&C++相关文章