Check for duplicates in large vector of strings

Question

I'm attempting to find duplicate instances of strings where I have a vector of ~2.5 million strings.~

At the moment I use something like:

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

Which is fine for small files, but obviously ends up taking an extremely long time as filesize grows due to the nested for loop and increasing number of strings contained in dupecheckVec.

What might be a less horrific way to do this in a large file?

Answer 1

If you don't mind reordering the vector, then this should do it in O(n*log(n)) time:

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

To preserve the order, you could instead use a vector of (line-number, string*) pairs: sort by string, uniquify using a comparator that compares string contents, and finally sort by line number, along the lines of:

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