为什么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());
}

生活

可能的输出:

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

生活

可能的输出:

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

生活

编写这样的函数的其他解决方案也很受欢迎(没有制作和排序std :: pair)

Answer 1

std::sort使用O(n*log(n))复杂的排序.它可以是例如(快速排序的优化版本).它选择一个枢轴,在枢轴之前移动较小的元素,在枢轴之后移动较大的元素,并在第一个和第二个半部分递归地重复它.

这也意味着std::sort允许(并且需要快速)vector在排序期间多次移动元素.比较功能将在当前位置看到它们.

奇怪的向量外地址表示std::sort在排序期间移动元素到堆栈.具体而言:(克++ 4.8.2)例如__unguarded_linear_insert在bits/std_algo.h它的参数移动到堆栈.

在排序过程中,元素的原始位置会丢失.如果要使用std::pair原始位置,则必须使用或使用其他方法存储原始位置.

从Angew的回答:也是一个重要的注意事项,你的比较器不一致.这是不确定的行为,可以给段错误与不同的输入.