2025年QStringList 去除重复项算法赏析

编程汇总 • 2025-08-31 18:30 • 阅读 58

测试用例：

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

2025年QStringList 去除重复项算法赏析

相关推荐