Question

Уже существует вектор сортировки указателей , но речь идет не о векторе указателей, а о векторе ссылочных указателей.

3 целых числа помещаются в std::vector<int*>, который затем сортируется в соответствии со значениями за указателями.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int a = 3;
    int b = 2;
    int c = 1;

    std::vector<int*> vec;
    vec.emplace_back(&a);
    vec.emplace_back(&b);
    vec.emplace_back(&c);

    std::sort(vec.begin(), vec.end(), [](const int* a, const int* b) {
        return *a < *b;
    });

    std::cout << "vec = " << *vec[0] << ", " << *vec[1] << ", " << *vec[2] << '\n';
    std::cout << "abc = " << a << ", " << b << ", " << c << '\n';
}

однако, кажется, что только вектор был отсортирован, поскольку выходные данные показывают:

vec = 1, 2, 3 
abc = 3, 2, 1

Я думаю, причина в том, что std::sort(), при правильном сравнении, просто присваивает адреса вместо значений. Что здесь не так? Почему я не могу отсортировать этот вектор указанных значений?

Следующая часть - скорее TL, DR, поскольку она показывает мой подход к решению этой проблемы. Простая задача, которая оказывается довольно сложной. @ Ответ Вирсавии указывает, что это невозможно . Поэтому следующие части, которые первоначально рассматривались как представление моей попытки, теперь могут рассматриваться как причина , почему это невозможно.

Моя идея состоит в том, чтобы создать класс-оболочку указателя для моих собственных конструкторов и операторов присваивания. std::sort() ведет себя по-разному, если размер контейнера невелик (<= 32 в моей системе), но в обоих случаях происходят назначения и перемещения - как показывает этот небольшой фрагмент из функции _Insertion_sort_unchecked (из <algorithm>).

(_BidIt == std::vector<int*>::iterator и _Iter_value_t<_BidIt> == int*)

_BidIt _Insertion_sort_unchecked(_BidIt _First, const _BidIt _Last, _Pr _Pred)
    {   // insertion sort [_First, _Last), using _Pred
    if (_First != _Last)
        {
        for (_BidIt _Next = _First; ++_Next != _Last; )
            {   // order next element
            _BidIt _Next1 = _Next;
            _Iter_value_t<_BidIt> _Val = _STD move(*_Next);

            if (_DEBUG_LT_PRED(_Pred, _Val, *_First))
                {   // found new earliest element, move to front
                _Move_backward_unchecked(_First, _Next, ++_Next1);
                *_First = _STD move(_Val);

Давайте создадим класс assignement_pointer, который ведет себя как указатель, за исключением того, что он присваивает значения вместо адресов.

template<typename T>
class assignement_pointer {
public:
    assignement_pointer(T& value) {
        this->m_ptr = &value;
        std::cout << "<T>& constructor\n";
    }
    assignement_pointer(const assignement_pointer& other) {
        this->m_ptr = other.m_ptr;
        std::cout << "copy constructor\n";
    }
    assignement_pointer(assignement_pointer&& other) {
        std::cout << "move assignement constructor >> into >> ";
        *this = std::move(other);
    }
    assignement_pointer& operator=(const assignement_pointer& other) {
        *this->m_ptr = *other.m_ptr;
        std::cout << "copy assignement operator\n";
        return *this;
    }
    assignement_pointer& operator=(assignement_pointer&& other) {
        std::swap(this->m_ptr, other.m_ptr);
        std::cout << "move assignement operator\n";
        return *this;
    }
    T& operator*() {
        return *this->m_ptr;
    }
    const T& operator*() const {
        return *this->m_ptr;
    }
private:
    T* m_ptr;
};

Как вы можете видеть, существуют также временные std::cout, чтобы увидеть, какие конструкторы / операторы присваивания были вызваны при прохождении std::sort() в основном:

    ///...
    std::vector<assignement_pointer<int>> vec;
    vec.reserve(3);
    vec.emplace_back(assignement_pointer(a));
    vec.emplace_back(assignement_pointer(b));
    vec.emplace_back(assignement_pointer(c));

    std::cout << "\nsort()\n";
    std::sort(vec.begin(), vec.end(), [](const assignement_pointer<int>& a, const assignement_pointer<int>& b) {
        return *a < *b;
    });

    std::cout << "\nvec = " << *vec[0] << ", " << *vec[1] << ", " << *vec[2] << '\n';
    std::cout << "abc = " << a << ", " << b << ", " << c << '\n';

дает вывод:

<T>& constructor
move assignement constructor >> into >> move assignement operator
<T>& constructor
move assignement constructor >> into >> move assignement operator
<T>& constructor
move assignement constructor >> into >> move assignement operator

sort()
move assignement constructor >> into >> move assignement operator
move assignement operator
move assignement operator
move assignement constructor >> into >> move assignement operator
move assignement operator
move assignement operator
move assignement operator

vec = 1, 2, 3
abc = 3, 2, 1

std::sort() вызывает только функции перемещения.
снова, vec отсортировано, но не a, b, c

последний пункт имеет смысл, поскольку, поскольку только функции перемещения называются, оператор присваивания копирования assignement_pointer& operator=(const assignement_pointer& other); (который выполняет присваивание значения) никогда не вызывается. Ненужный конструктор копирования и оператор присваивания могут быть удалены:

template<typename T>
class assignement_pointer {
public:
    assignement_pointer(T& value) {
        this->m_ptr = &value;
    }
    assignement_pointer(const assignement_pointer& other) = delete;
    assignement_pointer& operator=(const assignement_pointer& other) = delete;
    assignement_pointer(assignement_pointer&& other) {
        std::cout << "move assignement constructor >> into >> ";
        *this = std::move(other);
    }
    assignement_pointer& operator=(assignement_pointer&& other) {
        std::swap(this->m_ptr, other.m_ptr);
        std::cout << "move assignement operator\n";
        return *this;
    }
    T& operator*() {
        return *this->m_ptr;
    }
    const T& operator*() const {
        return *this->m_ptr;
    }
private:
    T* m_ptr;
};

Теперь std::sort() внутренние процессы довольно сложны, но в итоге все сводится к сбою при выполнении такой операции, как std::swap():

 int main() {
    int a = 3;
    int b = 2;

    std::vector<assignement_pointer<int>> vec;
    vec.reserve(2); //to avoid re-allocations
    vec.emplace_back(assignement_pointer(a));
    vec.emplace_back(assignement_pointer(b));

    std::cout << "swap()\n";

    assignement_pointer<int> ptr_a{ a };
    assignement_pointer<int> ptr_b{ b };

    std::swap(ptr_a, ptr_b);

    std::cout << "\nptrs = " << *ptr_a << ", " << *ptr_b << '\n';
    std::cout << "a, b = " << a << ", " << b << '\n';
}

и как этот вывод показывает:

move assignement constructor >> into >> move assignement operator
move assignement constructor >> into >> move assignement operator
swap()
move assignement constructor >> into >> move assignement operator
move assignement operator
move assignement operator

ptrs = 2, 3
a, b = 3, 2

Дело в том, что переключаются только указатели, но не исходные переменные. std::swap в основном

_Ty _Tmp = _STD move(_Left);
_Left = _STD move(_Right);
_Right = _STD move(_Tmp);

объяснение

move assignement constructor >> into >> move assignement operator
move assignement operator
move assignement operator

оператор присваивания перемещения просто меняет указатели, поэтому создание временной переменной ничего не делает. Я вижу два возможных решения этой проблемы:

заставляет оператор присваивания перемещать не указатели обмена, а значения.
реализовать свой собственный swap() для класса

но оба не работают.

оператор присваивания перемещения не может поменять значения, потому что начальный m_ptr из this-> класса всегда nullptr, и я бы не стал разыменовывать это.
std::sort() никогда не использует std::swap(), а вместо этого просто std::move() с повсюду. (как уже частично замечено _Insertion_sort_unchecked).

Bathsheba · Answer 1 · 09 апреля 2019

Для этого вам нужно будет выполнить собственную функцию сортировки.

Лямбда обратного вызова используется для оценки порядка, но вам нужно настроить часть, которая выполняет фактический обмен элементами: иСтандартная библиотека C ++ sort не поддерживает ваши действия.

К счастью, быстрая сортировка без каких-либо наворотов (таких как предварительная рандомизация) выходит в несколько десятков строк,так что это не особенно обременительная задача.

quamrana · Answer 2 · 09 апреля 2019

Просто сохраните копию исходного вектора указателей и скопируйте отсортированные значения по:

            std::vector<int*> original = vec;  // Do this before the std::sort

Затем после печати a, b, c:

            std::vector<int> xfer;
            for (auto ptr : vec) {
                xfer.push_back(*ptr);
            }
            auto it = std::begin(xfer);
            for (auto ptr : original) {
                *ptr = *it++;
            }
            std::cout << "abc = " << a << ", " << b << ", " << c << '\n';

Вывод:

abc = 1, 2, 3

Как я могу отсортировать вектор значений, на которые указывают, используя std :: sort ()?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Как я могу отсортировать вектор значений, на которые указывают, используя std :: sort ()?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Нет похожих вопросов