元素的大小对 std::sort 的速度有影响吗？

Question

假设它们具有相同的大小，那么大小为 4 字节的元素的向量会比大小为 128 字节的元素排序得更快吗？我是否必须为它们编制索引并手动对索引进行排序，还是 std::sort 为我在幕后完成？

Answer 1

Given that they have the same size, would a vector of an element of size 4 byte sort faster than an element of say 128 bytes?

这取决于 CPU 体系结构，但是随着 std::sort 移动整个对象，较大的对象排序速度较慢（假设其他所有内容都相同）是完全可能且合理的。

Do I have to index them and sort the indicies manually or does std::sort does it under the hood for me?

如果你想对索引而不是对象进行排序，你需要明确地这样做 - 在索引容器上应用 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 容器将保持不变。

元素的大小对 std::sort 的速度有影响吗？

Does the size of the element matter to the speed of std::sort?

c++

std