Как же, черт возьми, отсортировать этот список?

    Пусть у нас есть список — содержимое каталога, в котором элементами являются экземпляры классов File и Folder. Задача — отсортировать этот список. Есть два широко известных варианта сортировки структуры каталога — когда сначала идут каталоги, а потом файлы, и когда файлы и каталоги сортируются вперемешку. Нам нужно дать пользователю возможность выбирать любой из этих вариантов.

    Впервые на похожую задачу я наткнулся на прошлой работе. К слову, решена эта задача была методом 3 из данной статьи. «Как неэстетично», — подумал я. — «Дали бы мне эту задачу, я бы точно решил ее в 128 раз лучше. Но… как?»

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

    Метод 1. Числовой приоритет элемента


    Наверно, самая первая идея, которая приходит в голову. Пусть у нас будет базовый класс, в котором помимо обязательного метода getName() будет добавлен метод int getPriority(), который будет отдавать информацию о приоритете элемента в сортировке. В конкретных классах будет реализована статическая переменная типа int, которая и будет определять нужный приоритет.

    Впрочем, в коде все это проще, чем я пытаюсь объяснить:

    class Base {
    public:
    
        virtual int getPriority() const = 0;
    
        virtual const std::string& getName() const = 0;
    
        virtual const std::string getPrintedName() const = 0;
    
        virtual ~Base() = default;
    
    };
    
    class File: public Base {
    public:
    
        static const int PRIORITY;
    
    public:
    
        File(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "File_" + getName();
        }
    
        int getPriority() const override {
            return PRIORITY;
        }
    
    private:
    
        std::string name;
    };
    
    const int File::PRIORITY = 1;
    
    class Folder: public Base {
    public:
    
        static const int PRIORITY;
    
    public:
    
        Folder(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "Folder_" + getName();
        }
    
        int getPriority() const override {
            return PRIORITY;
        }
    
    private:
    
        std::string name;
    };
    
    const int Folder::PRIORITY = 2;
    

    Компаратор для алгоритма сортировки:

    bool comparator(const std::unique_ptr<Base> &first, const std::unique_ptr<Base> &second) {
        const int priorityFirst = first->getPriority();
        const int prioritySecond = second->getPriority();
        if (priorityFirst != prioritySecond) {
            return priorityFirst > prioritySecond;
        } else {
            return first->getName() < second->getName();
        }
    }
    

    Заполняем массив и сортируем:

        std::vector<std::unique_ptr<Base>> files;
        files.emplace_back(std::make_unique<Folder>("1"));
        files.emplace_back(std::make_unique<File>("3"));
        files.emplace_back(std::make_unique<File>("2"));
        files.emplace_back(std::make_unique<Folder>("4"));
    
        std::sort(files.begin(), files.end(), comparator);
    
        for (const std::unique_ptr<Base> &element: files) {
            std::cout << element->getPrintedName() << " ";
        }
            
        std::cout << std::endl;
    

    Полный код

    Все довольно просто и понятно, никаких сверхспособностей для того чтобы писать и читать такой код не требуется. Но есть у этого кода существенные минусы:

    1. Тип приоритета — int. В каком диапазоне должны лежать выбираемые приоритеты для классов? Эти приоритеты, они нумеруются с 0, с 1, могут ли они быть отрицательными?
    2. Если мы планируем ввести новый класс (какой-нибудь Symlink например) так, чтобы в сортировке он располагался между уже существующими классами, то нам придется «смещать» большую часть констант. Это может вызвать проблемы — как гарантированно найти всех наследников класса Base?
    3. Сортировка элементов не обязательно должна быть обязанностью самих элементов. Сами элементы файла, папки вполне могут и не подозревать, что их собираются сортировать.


    В общем, этот метод нам не подходит, двигаемся дальше

    Метод 2. Идентификация класса по текстовому типу класса


    Для каждого класса можно ввести статическую строковую переменную, определяющую тип класса.

    Структура классов
    class Base {
    public:
    
        virtual std::string getType() const = 0;
    
        virtual const std::string& getName() const = 0;
    
        virtual const std::string getPrintedName() const = 0;
    
        virtual ~Base() = default;
    
    };
    
    class File: public Base {
    public:
    
        static const std::string TYPE;
    
    public:
    
        File(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "File_" + getName();
        }
    
        std::string getType() const override {
            return TYPE;
        }
    
    private:
    
        std::string name;
    };
    
    const std::string File::TYPE = "File";
    
    class Folder: public Base {
    public:
    
        static const std::string TYPE;
    
    public:
    
        Folder(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "Folder_" + getName();
        }
    
        std::string getType() const override {
            return TYPE;
        }
    
    private:
    
        std::string name;
    };
    
    const std::string Folder::TYPE = "Folder";
    


    Компаратор:
    bool comparator(const std::unique_ptr<Base> &first, const std::unique_ptr<Base> &second) {
        if (first->getType() == Folder::TYPE && second->getType() == Folder::TYPE) {
            return first->getName() < second->getName();
        } else if (first->getType() == Folder::TYPE && second->getType() == File::TYPE) {
            return true;
        } else if (first->getType() == File::TYPE && second->getType() == Folder::TYPE) {
            return false;
        } else {
            return first->getName() < second->getName();
        }
    }
    

    Заполнение и сортировка ничем не отличаются от предыдущего варианта:

    Заполнение
        std::vector<std::unique_ptr<Base>> files;
        files.emplace_back(std::make_unique<Folder>("1"));
        files.emplace_back(std::make_unique<File>("3"));
        files.emplace_back(std::make_unique<File>("2"));
        files.emplace_back(std::make_unique<Folder>("4"));
    
        std::sort(files.begin(), files.end(), comparator);
    
        for (const std::unique_ptr<Base> &element: files) {
            std::cout << element->getPrintedName() << " ";
        }
    


    Полный код

    В общем, тоже особо ничего сложного. Но также есть и минусы.

    Во-первых, функция для сравнения элементов явно стала сложнее. Представьте, что будет, если сюда потребуется добавить новый элемент (тот же Symlink).

    Во-вторых, создавая новый класс путем копирования предыдущего, можно нечаянно забыть изменить строковый тип класса, что повлечет за собой веселую, но мучительную отладку.

    В принципе, из этого метода почти автоматически следует

    Метод 3. Идентификация класса с помощью rtti


    Давайте воспользуемся (скудными на данный момент) возможностями C++ в области рефлексии и избавимся в предыдущем примере от статической переменной, определяющей тип класса. Ведь это можно сделать, определив тип класса в runtime с помощью механизма rtti.

    Во-первых, структура классов стала проще:

    Структура классов
    class Base {
    public:
    
        virtual const std::string& getName() const = 0;
    
        virtual const std::string getPrintedName() const = 0;
    
        virtual ~Base() = default;
    
    };
    
    class File: public Base {
    public:
    
        File(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "File_" + getName();
        }
    
    private:
    
        std::string name;
    };
    
    class Folder: public Base {
    public:
    
        Folder(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "Folder_" + getName();
        }
    
    private:
    
        std::string name;
    };
    


    Тут уже нет никаких лишних полей, которые не нужны самому классу, но требуются алгоритму сортировки.

    Процедуры заполнения массива и самой сортировки по сравнению с предыдущими методами не изменились.

    Давайте теперь посмотрим на компаратор:

    bool comparator(const std::unique_ptr<Base> &first, const std::unique_ptr<Base> &second) {
        if (dynamic_cast<Folder*>(first.get()) != nullptr && dynamic_cast<Folder*>(second.get()) != nullptr) {
            return first->getName() < second->getName();
        } else if (dynamic_cast<Folder*>(first.get()) != nullptr && dynamic_cast<File*>(second.get()) != nullptr) {
            return true;
        } else if (dynamic_cast<File*>(first.get()) != nullptr && dynamic_cast<Folder*>(second.get()) != nullptr) {
            return false;
        } else {
            return first->getName() < second->getName();
        }
    }
    

    Господи…

    Да, наверно этот кусок кода можно как-то красиво переписать, но…
    Еще один минус данного подхода состоит в том, что нужно обязательно включать rtti при компиляции программы (который, к моему удивлению, оказался включен по умолчанию, по крайней мере в gcc)

    В общем, так себе метод, как по мне.

    Метод 4. Множественная диспетчеризация


    Глядя на предыдущие два метода, у некоторых из вас в голове поселилась мысль, что то, что я пытаюсь сделать, похоже на…

    Хотя кого я тут интригую, вы же уже видели заголовок.

    В общем, да, это похоже на множественную диспетчеризацию. Она возникает тогда, когда требуется вызвать метод (в смысле ООП) не от одного аргумента, а сразу от двух, трех…
    Например, если у нас есть множество геометрических фигур: квадрат, круг, треугольник. И мы хотим найти площадь пересечения любых двух из этих фигур. При этом, нам известны формулы для поиска площади пересечения квадрата и квадрата, квадрата и куба и т.д.

    Решить эту задачу можно с помощью шаблона Visitor, воспользовавшись для этого C++-ными variant-ами.

    Структура классов
    class File {
    public:
    
        File(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const {
            return name;
        }
    
        const std::string getPrintedName() const {
            return "File_" + getName();
        }
    
    private:
    
        std::string name;
    };
    
    class Folder {
    public:
    
        Folder(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const {
            return name;
        }
    
        const std::string getPrintedName() const {
            return "Folder_" + getName();
        }
    
    private:
    
        std::string name;
    };
    
    class Symlink {
    public:
    
        Symlink(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const {
            return name;
        }
    
        const std::string getPrintedName() const {
            return "Symlink_" + getName();
        }
    
    private:
    
        std::string name;
    };
    


    В классах нет ничего лишнего. Отсутствует даже базовый класс, так как мы все равно будем пользоваться variant-ом. Взамен я принес новый класс Symlink, который так долго грозился добавить.

    Введем дополнительный тип, являющийся Variant-ом данного класса:

    using Element = std::variant<Folder, File, Symlink>;
    

    Посмотрим, как можно заполнить и отсортировать элементы:

        std::vector<Element> files = {Folder("1"), File("3"), File("2"), Folder("4"), Symlink("1"), Symlink("5"), Symlink("1")};
    
        std::sort(files.begin(), files.end(), comparator);
    
        for (const Element &element: files) {
            std::visit([](const auto &elem) {
                std::cout << elem.getPrintedName() << " ";
            }, element);
        }
            
        std::cout << std::endl;
    

    В принципе, заполнение даже проще, чем во всех предыдущих вариантах.

    Теперь основная часть данного метода — компаратор:

    bool operator<(const Folder &first, const Folder &second) {
        return first.getName() < second.getName();
    }
    
    bool operator<(const Folder &first, const File &second) {
        return true;
    }
    
    bool operator<(const Folder &first, const Symlink &second) {
        return true;
    }
    
    bool operator<(const File &first, const Folder &second) {
        return false;
    }
    
    bool operator<(const File &first, const File &second) {
        return first.getName() < second.getName();
    }
    
    bool operator<(const File &first, const Symlink &second) {
        return true;
    }
    
    bool operator<(const Symlink &first, const Folder &second) {
        return false;
    }
    
    bool operator<(const Symlink &first, const File &second) {
        return false;
    }
    
    bool operator<(const Symlink &first, const Symlink &second) {
        return first.getName() < second.getName();
    }
    
    bool comparator(const Element &first, const Element &second) {
        const bool result = std::visit([&](const auto &contentFirst){
            return std::visit([&](const auto &contentSecond){
                return contentFirst < contentSecond;
            }, second);
        }, first);
        return result;
    }
    

    Полный код

    Сам компаратор довольно простой — вызывается std::visit сначала для первого элемента, потом для второго. Потом вызывается процедура сравнения. Так как std::visit «сохранит» тип лежащего в variant-е значения, то при сравнении выберется правильная перегрузка функции.

    Вот только сами перегрузки выглядят… громоздко. Напечатать все это и ни разу не ошибиться — задача для терпеливых.

    Конечно, можно с помощью шаблонов и чьей-то матери

    уменьшить количество бойлерпринта
    struct ComparePriority {
        int operator()(const Folder &first, const File &second) const {
            return 1;
        }
    
        int operator()(const Folder &first, const Symlink &second) const {
            return 1;
        }
    
        int operator()(const Symlink &first, const File &second) const {
            return -1;
        }
    };
    
    bool comparator(const Element &first, const Element &second) {
        const bool result = std::visit([&](const auto &contentFirst){
            return std::visit([&](const auto &contentSecond){
                using TypeFirst = std::decay_t<decltype(contentFirst)>;
                using TypeSecond = std::decay_t<decltype(contentSecond)>;
                int compared;
                if constexpr (std::is_invocable_r_v<int, ComparePriority, TypeFirst, TypeSecond>) {
                    compared = ComparePriority()(contentFirst, contentSecond);
                } else if constexpr (std::is_invocable_r_v<int, ComparePriority, TypeSecond, TypeFirst>) {
                    compared = -ComparePriority()(contentSecond, contentFirst);
                } else if constexpr (std::is_same_v<TypeFirst, TypeSecond>){
                    compared = 0;
                } else {
                    static_assert(std::is_same_v<TypeFirst, TypeFirst>, "Error");
                }
                if (compared == 0) {
                    return contentFirst.getName() < contentSecond.getName();
                } else {
                    return compared == 1;
                }
            }, second);
        }, first);
        return result;
    }
    


    Полный код

    но давайте лучше рассмотрим следующий вариант.

    Метод 5. Множественная диспетчеризация с приоритетом


    Структура классов остается той же самой, как и в предыдущем варианте.

    Структура классов
    class File {
    public:
        
        File(const std::string &name)
            : name(name)
        {}
        
        const std::string& getName() const {
            return name;
        }
    
        const std::string getPrintedName() const {
            return "File_" + getName();
        }
    
    private:
        
        std::string name;
    };
    
    class Folder {
    public:
        
        Folder(const std::string &name)
            : name(name)
        {}
        
        const std::string& getName() const {
            return name;
        }
    
        const std::string getPrintedName() const {
            return "Folder_" + getName();
        }
    
    private:
        
        std::string name;
    };
    
    class Symlink {
    public:
    
        Symlink(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const {
            return name;
        }
    
        const std::string getPrintedName() const {
            return "Symlink_" + getName();
        }
    
    private:
    
        std::string name;
    };
    
    using Element = std::variant<Folder, File, Symlink>;
    


    Ключевое отличие — определение числового приоритета для каждого класса:

    int priority(const Folder &) {
        return 3;
    }
    
    int priority(const File &) {
        return 2;
    }
    
    int priority(const Symlink &) {
        return 1;
    }
    

    В результате сам компаратор становится таким:

    bool comparator(const Element &first, const Element &second) {
        const bool result = std::visit([&](const auto &contentFirst){
            return std::visit([&](const auto &contentSecond){
                const int priorityFirst = priority(contentFirst);
                const int prioritySecond = priority(contentSecond);
                if (priorityFirst != prioritySecond) {
                    return priorityFirst > prioritySecond;
                } else {
                    return contentFirst.getName() < contentSecond.getName();
                }
            }, second);
        }, first);
        return result;
    }
    

    Полный код

    Окей, все хорошо. Но если вы помните, в самом начале я обещал дать пользователю возможность конфигурировать приоритеты классов при сортировке элементов. Сейчас же конфигурировать эти самые приоритеты можно только до начала компиляции, внутри кода. Давайте попробуем вынести задание приоритетов в runtime и посмотрим, что из этого получится.

    Метод 6. Числовой приоритет, конфигурируемый извне


    Давайте вспомним структуру классов из первого метода:

    Структура классов
    class Base {
    public:
    
        virtual int getPriority() const = 0;
    
        virtual const std::string& getName() const = 0;
    
        virtual const std::string getPrintedName() const = 0;
    
        virtual ~Base() = default;
    
    };
    
    class File: public Base {
    public:
    
        static int PRIORITY;
    
    public:
    
        File(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "File_" + getName();
        }
    
        int getPriority() const override {
            return PRIORITY;
        }
    
    private:
    
        std::string name;
    };
    
    int File::PRIORITY = 0;
    
    class Folder: public Base {
    public:
    
        static int PRIORITY;
    
    public:
    
        Folder(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "Folder_" + getName();
        }
    
        int getPriority() const override {
            return PRIORITY;
        }
    
    private:
    
        std::string name;
    };
    
    int Folder::PRIORITY = 0;
    
    bool comparator(const std::unique_ptr<Base> &first, const std::unique_ptr<Base> &second) {
        const int priorityFirst = first->getPriority();
        const int prioritySecond = second->getPriority();
        if (priorityFirst != prioritySecond) {
            return priorityFirst > prioritySecond;
        } else {
            return first->getName() < second->getName();
        }
    }
    


    И подумаем, как сконфигурировать приоритеты. Ну тут все просто — давайте возьмем ссылки на статические члены PRIORITY и отдадим их пользователю:

        std::vector<std::pair<std::string, std::reference_wrapper<int>>> priorities{{"Folder", std::ref(Folder::PRIORITY)}, {"File", std::ref(File::PRIORITY)}};
    
        for (const auto &[type, ptr]: priorities) {
            if (type == "Folder") {
                ptr.get() = 2;
            } else if (type == "File") {
                ptr.get() = 1;
            }
        }
    

    Полный код

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

    Метод 7. Идентификация класса по текстовому типу класса и конфигурирование приоритетов извне


    Напомним структуру классов
    class Base {
    public:
    
        virtual std::string getType() const = 0;
    
        virtual const std::string& getName() const = 0;
    
        virtual const std::string getPrintedName() const = 0;
    
        virtual ~Base() = default;
    
    };
    
    class File: public Base {
    public:
    
        static const std::string TYPE;
    
    public:
    
        File(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "File_" + getName();
        }
    
        std::string getType() const override {
            return TYPE;
        }
    
    private:
    
        std::string name;
    };
    
    const std::string File::TYPE = "File";
    
    class Folder: public Base {
    public:
    
        static const std::string TYPE;
    
    public:
    
        Folder(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "Folder_" + getName();
        }
    
        std::string getType() const override {
            return TYPE;
        }
    
    private:
    
        std::string name;
    };
    
    const std::string Folder::TYPE = "Folder";
    


    Здесь поле TYPE будет служить ключем в какой-нибудь мапе, хранящей полученные приоритеты. В результате, в компараторе нужно сначала обратиться в эту map для того, чтобы извлечь приоритет:

    bool comparator(const std::map<std::string, int> &priorities, const std::unique_ptr<Base> &first, const std::unique_ptr<Base> &second) {
        const int priorityFirst = priorities.at(first->getType());
        const int prioritySecond = priorities.at(second->getType());
        if (priorityFirst != prioritySecond) {
            return priorityFirst > prioritySecond;
        } else {
            return first->getName() < second->getName();
        }
    }
    

    Заполнение приоритетов и сортировка:

        std::map<std::string, int> priorities;
        priorities.emplace(Folder::TYPE, 2);
        priorities.emplace(File::TYPE, 1);
    
        std::vector<std::unique_ptr<Base>> files;
        // Заполнение files
    
        std::sort(files.begin(), files.end(), std::bind(comparator, std::ref(priorities), _1, _2));
    

    Полный код

    Метод 8. Идентификация класса с помощью rtti с конфигурировванием приоритетов извне


    Метод похож на предыдущий, только вместо строковых констант используется typeid класса

    Структура классов
    class Base {
    public:
    
        virtual const std::string& getName() const = 0;
    
        virtual const std::string getPrintedName() const = 0;
    
        virtual ~Base() = default;
    
    };
    
    class File: public Base {
    public:
    
        File(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "File_" + getName();
        }
    
    private:
    
        std::string name;
    };
    
    class Folder: public Base {
    public:
    
        Folder(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const override {
            return name;
        }
    
        const std::string getPrintedName() const override {
            return "Folder_" + getName();
        }
    
    private:
    
        std::string name;
    };
    


    Компаратор и заполнение:

    bool comparator(const std::unordered_map<std::type_index, std::pair<std::string, int>> &priorities, const std::unique_ptr<Base> &first, const std::unique_ptr<Base> &second) {
        const int priorityFirst = priorities.at(typeid(*first.get())).second;
        const int prioritySecond = priorities.at(typeid(*second.get())).second;
        if (priorityFirst != prioritySecond) {
            return priorityFirst > prioritySecond;
        } else {
            return first->getName() < second->getName();
        }
    }
    

        std::unordered_map<std::type_index, std::pair<std::string, int>> priorities;
        priorities.emplace(std::piecewise_construct, std::forward_as_tuple(typeid(Folder)), std::forward_as_tuple("Folder", 2));
        priorities.emplace(std::piecewise_construct, std::forward_as_tuple(typeid(File)), std::forward_as_tuple("File", 1));
    
        std::vector<std::unique_ptr<Base>> files;
        // Заполнение массива
    
        std::sort(files.begin(), files.end(), std::bind(comparator, std::ref(priorities), _1, _2));
    

    Полный код

    Здесь для поиска приоритета используется unordered_map, а typeid оборачивается в std::type_index как раз для такого случая.

    В принципе, где-то на последних двух методах можно было бы и остановиться. Конечно, эти методы обладают перечисленными выше недостатками, но, возможно, плата за них не слишком высока. Тем не менее, давайте напоследок попробуем реализовать идею runtime-конфигурирования в методе с двойной диспетчеризацией

    Метод 9. Множественная диспетчеризация с конфигурированием приоритетов извне


    В структуре классов как всегда ничего лишнего:

    Структура классов
    class File {
    public:
    
        File(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const {
            return name;
        }
    
        const std::string getPrintedName() const {
            return "File_" + getName();
        }
    
    private:
    
        std::string name;
    };
    
    class Folder {
    public:
    
        Folder(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const {
            return name;
        }
    
        const std::string getPrintedName() const {
            return "Folder_" + getName();
        }
    
    private:
    
        std::string name;
    };
    
    class Symlink {
    public:
    
        Symlink(const std::string &name)
            : name(name)
        {}
    
        const std::string& getName() const {
            return name;
        }
    
        const std::string getPrintedName() const {
            return "Symlink_" + getName();
        }
    
    private:
    
        std::string name;
    };
    
    using Element = std::variant<Folder, File, Symlink>;
    


    Для того, чтобы хранить где-то приоритеты, мы должны создать еще одну структуру классов. Начнем с базового класса

    struct ElementPriorityBase {
        virtual std::string printedType() const = 0;
    
        virtual void setPriority(int p) = 0;
    };
    

    Это вспомогательный класс, он будет использоваться для заполнения приоритетов.
    А вот его наследники:

    template<class T>
    struct ElementPriority: public ElementPriorityBase {
        int priority = 0;
    
        std::string printedType() const override {
            if constexpr (std::is_same_v<T, File>) {
                return "File";
            } else if constexpr (std::is_same_v<T, Folder>) {
                return "Folder";
            } else if constexpr (std::is_same_v<T, Symlink>) {
                return "Symlink";
            }
        }
    
        void setPriority(int p) override {
            priority = p;
        }
    };
    

    Идея метода в чем: мы создадим std::tuple из элементов этого класса, параметризованных нашими File, Folder и т.п.

    template<typename T>
    struct Empty {};
    
    template<typename... Ts>
    auto makeElementPriorityTupleFromElementVariant(Empty<std::variant<Ts...>>) -> std::tuple<ElementPriority<Ts>...> {
        return std::make_tuple(ElementPriority<Ts>()...);
    }
    
    using ElementPriorityTuple = decltype(makeElementPriorityTupleFromElementVariant(std::declval<Empty<Element>>()));
    

    Функция makeElementPriorityTupleFromElementVariant как раз создает нужный нам tuple из типа Element, который является variant-ом классов File, Folder,…
    Пустой класс Empty нужен здесь для того, чтобы можно было создать tuple, не создавая экземпляр variant-а (увидим ниже).

    Компаратор теперь выглядит так:

    template<class T>
    int priority(const ElementPriorityTuple &array, const T &element) {
        return std::get<ElementPriority<T>>(array).priority;
    }
    
    bool comparator(const ElementPriorityTuple &array, const Element &first, const Element &second) {
        const bool result = std::visit([&](const auto &contentFirst){
            return std::visit([&](const auto &contentSecond){
                const int priorityFirst = priority(array, contentFirst);
                const int prioritySecond = priority(array, contentSecond);
                if (priorityFirst != prioritySecond) {
                    return priorityFirst > prioritySecond;
                } else {
                    return contentFirst.getName() < contentSecond.getName();
                }
            }, second);
        }, first);
        return result;
    }
    

    В самом компараторе нет ничего особенного. А в вспомогательной функции priority происходит получение нужного нам элемента из tuple, так как мы знаем, каким типом этот элемент должен быть параметризован. В результате, не нужно никакого поиска по мапе, поиск приоритета выполняется за константное (и очень быстрое) время.

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

    template<typename tuple_t>
    std::vector<std::pair<std::string, std::reference_wrapper<ElementPriorityBase>>> makeElementPriorityBaseArray(tuple_t& tuple) {
        constexpr auto get_array = [](auto&... e){
            return std::vector<std::pair<std::string, std::reference_wrapper<ElementPriorityBase>>>{std::make_pair(e.printedType(), std::ref(static_cast<ElementPriorityBase&>(e)))...};
        };
        return std::apply(get_array, tuple);
    }
    

    В результате, создание заполнение и сортировка списка выглядит так:

        ElementPriorityTuple tuple = makeElementPriorityTupleFromElementVariant(Empty<Element>());
    
        const std::vector<std::pair<std::string, std::reference_wrapper<ElementPriorityBase>>> arrayToFill = makeElementPriorityBaseArray(tuple);
    
        for (const auto &[typeStr, element]: arrayToFill) {
            if (typeStr == "Folder") {
                element.get().setPriority(3);
            } else if (typeStr == "File") {
                element.get().setPriority(2);
            } else if (typeStr == "Symlink") {
                element.get().setPriority(1);
            }
        }
    
        std::vector<Element> files = {Folder("1"), File("3"), File("2"), Folder("4"), Symlink("1"), Symlink("5"), Symlink("1")};
    
        std::sort(files.begin(), files.end(), std::bind(comparator, std::ref(tuple), _1, _2));
    
        for (const Element &element: files) {
            std::visit([](const auto &elem) {
                std::cout << elem.getPrintedName() << " ";
            }, element);
        }
    

    Полный код

    Сначала мы создаем наш tuple, содержащий приоритеты, потом генерируем из него массив ссылок на базовый класс, заполняем приоритеты и дальше как обычно сортируем.

    Выводы


    К сожалению, не всегда удается найти хорошее решение для простой, казалось бы задачи. Бывает, следует остановиться и выбрать из того, что есть. Это порождает холиварные вопросы «а что есть чистый код», «существует ли идеальный код», «насколько красиво программист должен решать задачи». Глядя на этот пример, хочется переосмыслить ответы на приведенные вопросы.

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

    А какой вариант кода понравился Вам?

    • 21,9%Метод 1. Числовой приоритет элемента7
    • 6,2%Метод 2. Идентификация класса по текстовому типу класса2
    • 6,2%Метод 3. Идентификация класса с помощью rtti2
    • 6,2%Метод 4. Множественная диспетчеризация2
    • 9,4%Метод 5. Множественная диспетчеризация с приоритетом3
    • 6,2%Метод 6. Числовой приоритет, конфигурируемый извне2
    • 9,4%Метод 7. Идентификация класса по текстовому типу класса и конфигурирование приоритетов извне3
    • 6,2%Метод 8. Идентификация класса с помощью rtti с конфигурировванием приоритетов извне2
    • 15,6%Метод 9. Множественная диспетчеризация с конфигурированием приоритетов извне5
    • 25,0%Свой вариант (оставлю в комментариях)8

    Комментарии 17

      0
      Я поясню свой выбор 8 (как наиболее близкий), хотя на мой взгляд там нужен dynamic_cast, a не typeid, и можно ограничиться параметризованным функтором / компаратором
      Приоритет при сортировке на мой взгляд привязан к параметрам сортировки, и элементы об этом ничего знать не должны.
      Это исключает варианты 1 — 6 (6 вообще костыльный с побочными эффектами)
      Вариант 7 и 8 похожи, но смысла возиться со строками нет, тем более писать для этого методы элемента, по сути дублирование встроенного RTTI.
      Вариант 9 на мой взгляд плохо расширяем из-за строгой типизации
        0
        Варианты 4 и 5 как раз отвязывает элементы от деталей реализации сортировки
          0
          Они не привязаны к параметрам сортировки, поскольку она сама не параметризована, а жёстко задана в коде, нету «конфигурирования приоритетов извне» — приоритеты должны задаваться в рантайме, а не на этапе компиляции.
          4й вариант где на 3 типа написано 9 функций сравнения плохо масштабируется при увеличении числа типов.
          5й в принципе можно легко переделать и параметризовать, если очень надо без RTTI, то выбрал бы его.
            0
            Иногда сортировка должна задаваться жестко в коде. То есть, пользователь извне ее менять не может, но по запросу например менеджера может быть нужно что-то быстро подтюнить
          0
          Классы файлов, каталогов и т.д. не обязательно должны быть из стандартной библиотеки. В моем случае задача была даже не в классах и каталогах. Там были другие сущности. Файлы и каталоги я выбрал как наглядный всем понятный пример
          0
          //$dirs
          //$files
          if($config['mix']) {
            $mix=array_megre($dirs, $files);
            sort($mix);
          }else{
            sort($dirs);
            sort($files);
          }
            0
            Тогда получается, что только ради целей сортировки нужно таскать список каталогов и файлов раздельно
              0

              Будет перерасход по памяти?

                0
                Нет, непонятно как это обыграть в плане архитектуры. Куда деть эти dirs, files? Завернуть в структуру? А если нам нужно сделать общее действие над всеми элементами (например, найти по какому-нибудь шаблону), то искать сначала в одном, а потом в другом?
                  0
                  тогда наследование выглядит как оверхед. Типичная задача на сортировку подразумевает массив элементов одного типа с разными свойствами, никакой магии.
            +1

            Первый вариант с приоритетом в виде инта, только вместо int — enum.

              0
              Хороший вариант, как развитие первого варианта. Можно enum вынести в файл, принадлежашей сортировке и тогда уйдет проблема «поиска всех наследников», нужно будет только заглянуть в файл, где описаны все enum-ы. Но минус — структуры зависят от сортировки
                0

                Что значит "структуры зависят от сортировки"? В смысле, я не понял, что имеется в виду. Можете перефразировать?

                  0
                  Ну это значит, что в структурах есть поле priority, которое нужно только для сортировки. Хотя сортировка — не обязательно задача именно этих структур.

                  В статье про это написано

                  Может например быть такая ситуация, что классы File, Folder вам даны извне и вы ничего не можете с ними сделать (добавить доп поле например)
              0
              Оператор dynamic_cast имеет существенные накладные расходы. При сортировке его лучше избегать.
                0
                вот если использовать именно список, то отсортировать надо лишь единожды, далее можно перетасовывать его при смене типа сортировки за O(N).

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое