c++ - 检查大型字符串 vector 中的重复项

Question

我正在尝试查找重复的字符串实例，其中我有一个包含约 250 万个字符串的 vector 。~

目前我使用类似的东西:

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 中包含的字符串数量增加，随着文件大小的增长，显然最终会花费非常长的时间。

在大文件中执行此操作的不那么可怕的方法是什么？

Answer 1

如果您不介意重新排序 vector ，那么这应该在 O(n*log(n)) 时间内完成:

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

为了保留顺序，您可以改为使用 (line-number, string*) 对 vector :按字符串排序，使用比较字符串内容的比较器进行 uniquify，最后按行号排序，如下所示:

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(), vector.end(), StringEquals()), vector.end());
std::sort(vector.begin(), vector.end(), OrderByLine());