C++11 объединяет std::tuple и std::tie для эффективного упорядочения

Question

Я довольно новичок в std:: tuple и std::tie. Мне нужен способ эффективного упорядочения структур по порядку сравнений слева направо. По этой причине я решил использовать типы std::make_tuple и std:: tie для пользовательского заказа StructA в представленном живом примере. Подход кортежа обеспечивает встроенные сравнения эквивалентности, начинающиеся слева направо, что идеально для упорядочивания элементов LessThanComparable для std:: sort с сопровождающим лямбда-компаратором (для которого я показываю 3 примера).

Проблема в том, что, насколько мне известно, std::make_tuple делает неэффективные копии элементов кортежа, и мне было интересно, есть ли способ объединить std::make_tuple с std:: tie, как я пытался сделать с моим 3-й компаратор - который потерпел неудачу (иначе его вывод был бы похож на первый порядок вывода).

В моем конкретном примере я не могу использовать std:: tie напрямую, так как мне нужно использовать временный элемент как первый элемент в моем кортеже.

Выход выглядит следующим образом

Order[mPath.filename(), elem1, intVal]
======================================
"/zoo/dir1/filename.txt" - nameA1 - 1
"/tmp/dir1/filename.txt" - nameA1 - 3
"/fad/dir1/filename.txt" - nameA1 - 4

Order[mPath, elem1, intVal]
======================================
"/fad/dir1/filename.txt" - nameA1 - 4
"/tmp/dir1/filename.txt" - nameA1 - 3
"/zoo/dir1/filename.txt" - nameA1 - 1

Order[mPath.filename(), elem1, intVal]
======================================
"/fad/dir1/filename.txt" - nameA1 - 4
"/tmp/dir1/filename.txt" - nameA1 - 3
"/zoo/dir1/filename.txt" - nameA1 - 1

Я ожидал, что третий набор выходных данных будет идентичен первому или альтернативно, если кто-нибудь скажет мне, как правильно смешивать неэффективные std:: tuples с эффективными std:: ties

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <boost/filesystem.hpp>

struct StructA {
    boost::filesystem::path mPath;
    std::string elem1;
    int intVal;
};

template<typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& 
operator<<(std::basic_ostream<CharT, Traits>& os, StructA const& sa) {
    return os << sa.mPath << " - " << sa.elem1 << " - " << sa.intVal << std::endl;
}


int main()
{
    std::vector<StructA> aStructs = {
        {"/zoo/dir1/filename.txt", "nameA1", 1}, 
        {"/fad/dir1/filename.txt", "nameA1", 4}, 
        {"/tmp/dir1/filename.txt", "nameA1", 3}
    };    

    std::cout << "Order[mPath.filename(), elem1, intVal]" << std::endl;
    std::cout << "======================================" << std::endl;
    std::sort(aStructs.begin(), aStructs.end(),
        [](const StructA& lhs, const StructA& rhs){
            return std::make_tuple(lhs.mPath.filename(), lhs.elem1, lhs.intVal) < 
                std::make_tuple(rhs.mPath.filename(), rhs.elem1, rhs.intVal);
        });

    // print reordered structs
    std::copy(aStructs.begin(), aStructs.end(),
        std::ostream_iterator<StructA>(std::cout, ""));        

    std::cout << std::endl;

    std::cout << "Order[mPath, elem1, intVal]" << std::endl;
    std::cout << "======================================" << std::endl;
    std::sort(aStructs.begin(), aStructs.end(),
        [](const StructA& lhs, const StructA& rhs){
            return std::tie(lhs.mPath, lhs.elem1, lhs.intVal) < 
                std::tie(rhs.mPath, rhs.elem1, rhs.intVal);
        });

    // print reordered structs
    std::copy(aStructs.begin(), aStructs.end(),
        std::ostream_iterator<StructA>(std::cout, ""));

    std::cout << std::endl;

    std::cout << "Order[mPath.filename(), elem1, intVal]" << std::endl;
    std::cout << "======================================" << std::endl;
    std::sort(aStructs.begin(), aStructs.end(),
        [](const StructA& lhs, const StructA& rhs){
            // attempt at efficiency - but not quite right
            return lhs.mPath.filename() < rhs.mPath.filename() && 
                std::tie(lhs.elem1, lhs.intVal) < std::tie(rhs.elem1, rhs.intVal);
        });

    // print reordered structs
    std::copy(aStructs.begin(), aStructs.end(),
        std::ostream_iterator<StructA>(std::cout, ""));
}

Answer 1

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

3) (bool) (std:: get<0>(lhs) (rhs)) || (! (bool) (std:: get<0>(rhs) (lhs)) && lhstail

Исправлен лямбда-компаратор для сортировки первых сортировок по имени файла () временному, а затем использует эффективный std:: tie для других элементов в кортеже

std::cout << "Order[mPath.filename(), elem1, intVal]" << std::endl;
std::cout << "======================================" << std::endl;
std::sort(aStructs.begin(), aStructs.end(),
    [](const StructA& lhs, const StructA& rhs){
        // attempt at efficiency - but not quite right
        // AHA, I think I figured it out - see tuple operator_cmp
        // return value documentation which states 
        // (bool)(std::get<0>(lhs) < std::get<0>(rhs)) || 
        // (!(bool)(std::get<0>(rhs) < std::get<0>(lhs)) && 
        // lhstail < rhstail), where lhstail is lhs without 
        // its first element, and rhstail is rhs without its 
        // first element. For two empty tuples, returns false.
        // --------------------------------------------------------
        // edit thanks to @Praetorian for suggesting the following:
        // --------------------------------------------------------
        auto f1 = lhs.mPath.filename(); auto f2 = rhs.mPath.filename();            
        return std::tie(f1, lhs.elem1, lhs.intVal) < std::tie(f2, rhs.elem1, rhs.intVal);
    });

Это сделало первый набор результатов идентичным третьему, что не очень эффективно для временного имени файла (), но, по крайней мере, я не принимаю удар std:: make_tuple для всех элементов в моей структуре. Обновленный живой пример здесь

Answer 2

std::tuple<std::string, std::string const&, int>
sort_helper(StructA const& s){
  return{ s.mPath.filename(), s.elem1, s.intVal };
}

затем:

std::sort(aStructs.begin(), aStructs.end(),
  [](const StructA& lhs, const StructA& rhs){
    return sort_helper(lhs)<sort_helper(rhs);
  }
);

что кажется чище нет?

Ценой одного std::string двигаться, в основном.