Блог

Мне интересно, почему этот код печатает одни и те же адреса элементов по-разному :

 template <typename FI>
void sorta(FI begin, FI end){
    using T = typename std::iterator_traits<FI>::value_type;
    std::sort(begin, end, [](const Tamp; lhs,const Tamp; rhs){
         std::cout << lhs<<"**"<<amp;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=[amp;begin,amp;f](intamp; lhs,intamp; rhs){
            std::cout<<amp;(*begin)<<"n"<<amp;lhs<<"  "<<amp;rhs;
            f(lhs,rhs);
        };

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

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

    foo(a.begin(),a.end(),[](intamp; lhs,intamp; rhs){
        std::cout<<"n"<<amp;lhs<<"  "<<amp;rhs<<"nnn";
    });
}
 

ЖИВЫЕ КОНЦЕРТЫ

возможные результаты:

 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, [amp;comp_proc,amp;begin,amp;indexs](const Tamp; l_item,const Tamp; r_item){

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

        bool res = comp_proc(l_item, r_item);
        if (const_cast<T*>(amp;l_item) > amp;(*begin) amp;amp; const_cast<T*>(amp;r_item) > amp;(*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 intamp; a,const intamp; b){return a<b;});

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

ЖИВЫЕ КОНЦЕРТЫ

Также приветствуются другие решения для написания такой функции (без создания и сортировки std::pair)

std::sort использует сортировку со O(n*log(n)) сложностью. Это может быть, например, (оптимизированная версия) quicksort . Он выбирает pivot, перемещает меньшие элементы перед pivot, более крупные элементы после pivot и повторяет его рекурсивно в первой и второй половине.

Это также означает, что std::sort разрешено (и должно быть быстрым) перемещать элементы vector несколько раз во время сортировки. Функция сравнения увидит их в их текущем местоположении.

Нечетные адреса вне вектора показывают, что std::sort элементы также перемещаются во время сортировки в стек. Чтобы быть конкретным: (g 4.8.2), например __unguarded_linear_insert , bits/std_algo.h перемещает свой аргумент в стек.

Исходные позиции элементов теряются во время сортировки. Вы должны использовать std::pair или какой-либо другой метод для сохранения исходных позиций, если вы хотите их использовать.

Из ответа Angew: Также важное замечание о том, что ваш компаратор не является согласованным. Это неопределенное поведение и может приводить к ошибкам с разными входными данными.

Во-первых, у вас неопределенное поведение, потому что передаваемый вами предикат std::sort не является внутренне согласованным — возможно, он будет сообщать a < b и b < a одновременно.

Даже без этого цель std::sort состоит в том, чтобы отсортировать элементы обмена диапазонами внутри него, чтобы они были в правильном порядке (в соответствии с предикатом). Поэтому, конечно, элементы будут перемещаться по диапазону.

Он выводит разные адреса, потому что некоторые элементы хранятся во временных переменных в стеке, в то время как другие перемещаются.

 5**0x25e5014    // This is in the original array
3**0x25e5018    // This too
3**0x7fff93d5d3e0   // This is on the stack
 

«Меньшие» адреса памяти обычно соответствуют значениям в изображениях файла (адреса функций, глобальные переменные и т. Д.), В то время как более высокие обычно являются адресами, выделенными из кучи или стека. 0x7fff ******** обычно находится в стеке в 64-битных программах, но это только из моего личного опыта отладки, а не высечено на камне.