1

私は std::tuple と std::tie にかなり慣れていません。左から右への比較順序に従って効率的に構造体を順序付ける方法が必要です。このため、提供されているライブの例では、StructA のカスタム順序付けにstd::make_tupleおよびstd::tie型を使用することにしました。タプル アプローチは、左から右への組み込みの等価比較を提供します。これは、付随するラムダ コンパレータを使用した std::sort の LessThanComparable要素の順序付けに最適です (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

私は、出力の 3 番目のセットが最初の出力と同じになることを期待していました。

#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, ""));
}
4

2 に答える 2

1

3番目のラムダの問題は、等価性と辞書式比較のために要素を正しく比較していないことであることがわかりました。正しいアプローチは、次のアプローチを使用する必要があることを示すタプル比較の箇条書き 3) で概説されています。

3) (bool)(std::get<0>(lhs) < std::get<0>(rhs)) || (!(bool)(std::get<0>(rhs) < std::get<0>(lhs)) && lhstail < rhstail) ここで、lhstail は最初の要素のない lhs であり、rhstail は最初の要素のない rhs です。エレメント。空のタプルが 2 つある場合は、false を返します。

filename() 一時に従って最初に並べ替えを行うための修正されたラムダ コンパレータは、タプル内の他の要素に対して効率的な 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);
    });

そうすることで、結果の最初のセットが3番目と同じになりました. filename() 一時的には非常に効率的ではありませんが、少なくとも構造体のすべての要素に対して std::make_tuple ヒットを取りません. 更新されたライブの例はこちら

于 2014-05-13T23:49:51.977 に答える