QStringList 去除重复项算法赏析

大家好，又见面了，我是你们的朋友全栈君。

测试用例：

    QStringList list;
    list<<"2222"<<"xxx"<<"1111"<<"2222"<<"xxxx"<<"1111";
    int n=list.removeDuplicates();

源代码：

/*!
    \fn int QStringList::removeDuplicates()

    \since  4.5

    This function removes duplicate entries from a list.
    The entries do not have to be sorted. They will retain their
    original order.

    Returns the number of removed entries.
*/
int QtPrivate::QStringList_removeDuplicates(QStringList *that)
{
    int n = that->size();
    int j = 0;
    QSet<QString> seen;
    seen.reserve(n);
    int setSize = 0;
    for (int i = 0; i < n; ++i) {
        const QString &s = that->at(i);
        seen.insert(s);
        if (setSize == seen.size()) // unchanged size => was already seen
            continue;
        ++setSize;
        if (j != i)
            that->swap(i, j);    //将不重复项与重复项交换
        ++j;
    }
    if (n != j)
        that->erase(that->begin() + j, that->end());
    return n - j;
}

以上述list为例：

list<<"2222"<<"xxx"<<"1111"<<"2222"<<"xxxx"<<"1111";

循环执行：

第一次：不存在重复项。2222 插入seen.    setSize=1  j=1

第二次：不存在重复项。xxx   插入seen.    setSize=2  j=2

第三次：不存在重复项。1111 插入seen.    setSize=3  j=3

第四次： 存在重复项。  continue;            setSize=3  j=3

第五次：不存在重复项。xxxx插入seen.     setSize=4  j=3  此时i不等于j。that->swap()执行 xxxx将与后一个2222交换位置；setSize=4  j=4 

第六次：存在重复项。  continue;             setSize=4  j=4 

循环完毕：

执行：

that->erase(that->begin() + j, that->end());

删掉最后的两项。

剩余列表：

list<<"2222"<<"xxx"<<"1111"<<"xxxx";