元素的大小与std：：排序的速度有关吗？

Question

如果它们具有相同的大小，那么大小为4字节的元素的向量排序速度会比128个字节的元素更快吗？我是否必须对它们进行索引并手动对这些指标进行排序，还是使用std::sort为我在引擎盖下面排序？

Answer 1

考虑到它们的大小相同，那么大小为4字节的元素的向量会比128个字节的元素更快地排序吗？

这取决于CPU体系结构，但是当std::sort移动整个对象时，很有可能和合理地期望更大的对象被排序得更慢(假设其他一切都是相等的)。

，我是否必须对它们进行索引，并手动对这些指标进行排序，还是使用std::sort为我在引擎盖下面排序？

如果要排序索引而不是对象，则需要显式地对索引容器(而不是实际对象)应用std::sort，而是使用比较器(它使用实际的索引指向的对象)。同样，std::sort移动实际对象，在本例中，对象将是索引。

例如：

struct BigObject {
    int value;
    // some other data that makes this object big
};

std::vector<BigObject> objects;
// objects is populated with data somehow


std::vector<std::size_t> indexes( objects.size() );

// fill indexes with values from 0 to N-1
std::iota( indexes.begin(), indexes.end(), 0 ); 
// sort indexes
std::sort( indexes.begin(), indexes.end(), [&objects]( size_t i1, size_t i2 )
    {
        return objects[i1].value < objects[i2].value;
    } );

现在，您的索引将按value的升序排序，但objects容器将保持不变。