c++ - 为什么 std::vector 的相同成员的地址在 std::sort 的比较函数中不同？

Question

我想知道为什么这段代码以不同的方式打印相同的成员地址:

template <typename FI>
void sorta(FI begin, FI end){
    using T = typename std::iterator_traits<FI>::value_type;
    std::sort(begin, end, [](const T& lhs,const T& rhs){
         std::cout << lhs<<"**"<<&lhs  << '\n';
         return std::rand()%2;
    });
}

int main()
{
    std::vector<int> a{1,5,3,4,7};
    sorta(a.begin(),a.end());
}

live

可能的输出:

5**0x25e5014
3**0x25e5018
3**0x7fff93d5d3e0
...

如您所见，变量 3 的地址在每个函数调用中都是不同的!

看起来很奇怪我尝试了一个简单的函数，它做一些类似于 std::sort 的事情:

using Iterator=std::vector<int>::iterator;
template<class Func>
void foo(Iterator begin,Iterator end,Func f)
{
    for(Iterator it=begin; it != end-1;++it)
    {
         auto f2=[&begin,&f](int& lhs,int& rhs){
            std::cout<<&(*begin)<<"\n"<<&lhs<<"  "<<&rhs;
            f(lhs,rhs);
        };

         f2(*it,*(it+1));
    }
}

int main()
{
    std::vector<int> a{1,5,3,4,7};

    foo(a.begin(),a.end(),[](int& lhs,int& rhs){
        std::cout<<"\n"<<&lhs<<"  "<<&rhs<<"\n\n\n";
    });
}

live

可能的输出:

0x837a008
0x837a008  0x837a00c
0x837a008  0x837a00c

0x837a008
0x837a00c  0x837a010
0x837a00c  0x837a010

...

惊喜!

在这种情况下地址相同，所以我希望 std::sort 做同样的事情!!

第一个代码有什么问题？ std::sort 是否多次复制变量？!

用例:

我正在尝试编写一个也返回源索引的排序函数，但由于我解释的问题它不起作用

template <typename FI ,class L >
std::vector<int> sorta(FI begin, FI end, L comp_proc){
    size_t size = std::distance(begin, end);
    using T = typename std::iterator_traits<FI>::value_type;

    std::vector <int> indexs(size);
    for (size_t i = 0; i < indexs.size(); i++)
        indexs[i] = i;

    std::sort(begin, end, [&comp_proc,&begin,&indexs](const T& l_item,const T& r_item){

        size_t l_dis = std::distance(&(*begin),const_cast<T*>(&l_item));//not working correctly
        size_t r_dis = std::distance(&(*begin),const_cast<T*>(&r_item));//not working correctly
        std::cout << l_item<<"**"<<&l_item <<"**"<<l_dis << "**" << r_dis << std::endl;

        bool res = comp_proc(l_item, r_item);
        if (const_cast<T*>(&l_item) > &(*begin) && const_cast<T*>(&r_item) > &(*begin)){
            if (res){
                std::swap(indexs[l_dis], indexs[r_dis]);//not working
            }
        }

        return res;
    });
    return indexs;

}

int main()
{
    std::vector<int> a{1,5,3,4,7};
    std::vector<int> indexes=sorta(a.begin(),a.end(),[](const int& a,const int& b){return a<b;});

    std::cout<<"\n";
    for(auto i:indexes)
    {
        std::cout<<i<<"\n";
    }
}

live

编写此类函数的其他解决方案也很受欢迎(无需制作和排序 std::pair)

Answer 1

std::sort使用具有 O(n*log(n)) 复杂度的排序。它可以是例如(的优化版本)quicksort .它选择一个枢轴，将较小的元素移动到枢轴之前，将较大的元素移动到枢轴之后，并在前半部分和后半部分递归重复。

这也意味着 std::sort 被允许(并且为了快速)在排序过程中多次移动 vector 的元素。比较功能将在当前位置看到它们。

奇怪的 vector 外地址表明 std::sort 也在排序期间将元素移动到堆栈中。具体来说:(g++ 4.8.2) 例如 bits/std_algo.h 中的 __unguarded_linear_insert 将其参数移动到堆栈。

---

元素的原始位置在排序过程中丢失了。如果您想使用它们，您必须使用 std::pair 或其他一些方法来存储原始位置。

---

来自 Angew 的回答:还有一个重要的注意事项，即您的比较器不一致。这是未定义的行为，可以给出 segfaults具有不同的输入。