c++11结合了std::tuple和std::tie来实现高效排序

Question

我对std::tuple和std::tie相当陌生。我需要一种方法来根据从左到右的比较顺序有效地对结构进行排序。出于这个原因，在提供的实际示例中，我选择使用std::make_tuple和std::tie类型对StructA进行自定义排序。元组方法提供了从左到右的内建等价比较，这对于带有lambda比较器的std::sort的LessThanComparable元素排序非常理想(我将展示3个示例)。

问题在于，据我所知，std::make_tuple对元组元素进行了低效的复制，我想知道是否有某种方法可以将std::make_tuple与std::tie结合起来，就像我尝试对第三个比较器所做的那样——失败了(否则它的输出将看起来像第一个输出顺序)。

在我的具体示例中，我不能直接使用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::元组与高效的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

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移动为代价，基本上。

Answer 2

我刚刚发现第3个lambda的问题是我没有正确地比较元素的等价性和字典顺序比较。元组比较的正确方法在项目3中列出，它表明我应该使用以下方法。

3) (bool)(std::get<0>(lhs) (rhs) | |(! (bool) (std:: get<0> (rhs) & lt;std:: get<0> (lh)),,lhstail & lt;rhstail),其中lstail是没有第一个元素的LHS, rhstail是RHS没有第一个元素。对于两个空元组，返回false。

用于排序的固定lambda比较器首先根据临时文件名()进行排序，然后对元组

中的其他元素使用高效的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);
    });

这样做使得第一组结果与第三组结果相同-对于filename()临时来说不是非常有效，但至少我没有对我的结构体中的所有元素使用std::make_tuple命中。更新后的实时示例在这里