C ++ 11 объединяет std :: tuple и std :: tie для эффективного упорядочения
Я довольно новичок в std :: tuple и std :: tie. Мне нужен способ эффективного упорядочения структур по порядку сравнений слева направо. По этой причине я решил использовать станд :: make_tuple а также станд :: галстука типы для пользовательского заказа StructA в живой пример предоставлена. Подход кортежа обеспечивает встроенные сравнения эквивалентности, начинающиеся слева направо, что идеально подходит для LessThanComparable упорядочение элементов для std :: sort с сопровождающим лямбда-компаратором (для которого я показываю 3 примера).
Проблема в том, что, насколько я знаю, станд :: make_tuple марки неэффективные копии из элементов кортежа, и мне было интересно, есть ли какой-нибудь способ объединить std :: make_tuple с 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, ""));
}
Решение
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 двигаться, в основном.
Другие решения
Я только что обнаружил, что проблема с 3-й лямбда состояла в том, что я неправильно сравнивал элементы для эквивалентности и лексикографического сравнения. Правильный подход изложен в пуле 3) для сравнение кортежей где это указывает на то, что я должен использовать следующий подход.
3) (bool) (std :: get)<0> (LHS) < станд :: прибудет<0> (rhs)) ||
(! (BOOL) (станд :: получить<0> (RHS) < станд :: прибудет<0> (LHS)) && lhstail < rhstail),
где lhstail — lhs без первого элемента, а rhstail — rhs
без его первого элемента. Для двух пустых кортежей возвращает false.
Исправлен лямбда-компаратор для сортировки первых сортировок по временному имени файла (), а затем использует эффективный 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 для всех элементов моей структуры. Обновленный живой пример Вот