容器Set使用和查找的效率比较

无论是STL还是QT中都是使用不同的数据结构，其中常用的有vector、map、list、set等，今天要说的极是set。

set作为一个容器可以保存多种类型的数据，而且里面的每一个元素都是唯一的，并且可以根据元素自行排序，这使得它在查找元素的时候效率很高。

一、 插入元素

和QVector比较

void testCountSet() {

QSet strSet;

strSet.insert("aaa");

strSet.insert("aaa");

strSet.insert("aaa");

strSet.insert("aaa");

strSet.insert("aaa");

strSet.insert("aaa");

qDebug() << QStringLiteral("数据集的数量：") << strSet.size();

QVector strVector;

strVector.push_back("bbb");

strVector.push_back("bbb");

strVector.push_back("bbb");

strVector.push_back("bbb");

strVector.push_back("bbb");

strVector.push_back("bbb");

qDebug() << QStringLiteral("数据向量的数量：") << strVector.size();

}

输出结果：

可以看出Set中存储的元素数据是唯一的，不重复的。Vector中存储的数据是可以重复的。

二、查找效率

和Map、Vector比较

void testFindTime() {

//数据集

QSet strSet;

for (int i = 0; i < 1000000; i++) {

strSet.insert(QString::number(i));

}

QTime time;

time.start();

strSet.find("999990");

qDebug() << QStringLiteral("Set查找：") << time.elapsed() << "ms";

//数据向量

QVector strVector;

for (int i = 0; i < 1000000; i++) {

strVector.push_back(QString::number(i));

}

QTime time2;

time2.start();

qFind(strVector.begin(), strVector.end(), "999990");

qDebug() << QStringLiteral("Vector查找：") << time2.elapsed() << "ms";

//映射结构

QMap mapStr;

for (int i = 0; i < 1000000; i++) {

mapStr.insert(QString::number(i), QString::number(i));

}

QTime time3;

time3.start();

mapStr.find("999990");

qDebug() << QStringLiteral("Map查找：") << time3.elapsed() << "ms";

}

输出结果：

可以看出Set和Map的查找效率明显要比Vector要高很多。因为Set和Map在存储数据的时候进行了排序，其实就是对二叉树进行了封装，再进一步就是对平衡二叉树（红黑树）进行了封装，所以在查找效率上有了很大的提升。

三、stl中的map和Qt中的QMap比较

Qt中的QMap

QSet intSet;

intSet.insert(21);

intSet.insert(2);

intSet.insert(51);

intSet.insert(11);

intSet.insert(26);

intSet.insert(121);

intSet.insert(0);

intSet.insert(1);

QSet::Iterator it;

for (it = intSet.begin();it!=intSet.end();it++){

qDebug() << *it;

}

输出结果：

STL中的set

std::set intSet;

intSet.insert(21);

intSet.insert(2);

intSet.insert(51);

intSet.insert(11);

intSet.insert(26);

intSet.insert(121);

intSet.insert(0);

intSet.insert(1);

std::set::iterator it;

for (it = intSet.begin(); it != intSet.end(); it++) {

qDebug() << *it;

}

输出结果：

通过以上两个代码示例可以看出：stl中的set在插入数据元素的时候，对数据元素进行了排序！而QT中的QSet并没有进行显示的排序。

aaa