c++11 combining std::tuple and std::tie for efficient ordering

Question

I am fairly new to std::tuple and std::tie. I need a way to efficiently order structs according to a left to right ordering of comparisons. For this reason, I chose to use the std::make_tuple and std::tie types for custom ordering a StructA in the live example provided. The tuple approach provides built in equivalence comparisons starting from left to right which is ideal for LessThanComparable element ordering for a std::sort with an accompanying lambda comparator (for which I show 3 examples).

The problem is that as far as I am aware, std::make_tuple makes inefficient copies of the tuple elements, and I was wondering if there was some way to combine std::make_tuple with std::tie as I tried to do with my 3rd comparator - which failed (otherwise its output would look like the first output ordering).

In my specific example I cannot use std::tie directly as I need to use a temporary as the 1st element in my tuple.

The output is as follows

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

I was expecting that the 3rd set of outputs would be identical to the first or alternatively if someone could tell me how to correctly mix inefficient std::tuples with efficient 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

I just discovered that the problem with the 3rd lambda was that I was not correctly comparing the elements correctly for equivalence and lexicographical comparison. The correct approach is outlined in bullet 3) for tuple comparison where it indicates that I should use the following approach.

3) (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.

The fixed up lambda comparator for sorting firsty sorts according to the filename() temporary and then uses the efficient std::tie for the other elements in the tuple

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

Doing so made the first set of results identical to the 3rd - not incredibly efficient for the filename() temporary but at least I don't take the std::make_tuple hit for all elements in my struct. The updated live example is here

Answer 2

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

then:

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

which seems much cleaner no?

At the cost of one std::string move, basically.