Boshqa ro'yxatga qarab ro'yxatni buyurtma qiling

Berilgan:

struct Object {
    int id;
    ...
};

list objectList;
list idList; 

objectList idList buyurtma tartibiga ko'ra buyurtma berishning eng yaxshi usuli qanday?

Misol (yolg'on kod):

INPUT
    objectList = {o1, o2, o3};
    idList = {2, 3, 1};

ACTION
    sort(objectList, idList);

OUTPUT
    objectList = {o2, o3, o1};

Hujjatlarni qidirdim, lekin men faqat o'zlari bilan taqqoslaydigan elementlarni tartibga solish usullarini topdim.

2
Agar taqqoslash funksiyasidan std :: sort <// a>?
qo'shib qo'ydi muallif Some programmer dude, manba
@Someprogrammerdude: std :: sort tasodifiy foydalanishni yineltiruvchilarni talab qiladi, lekin std :: list o'z sort a'zo funktsiyasiga ega.
qo'shib qo'ydi muallif Christian Hackl, manba
Olib tashlash uchun faqat ikkita izoh mavjud: hozirgi kundagi idListning mazmuni (chet ellarni taqqoslash uchun kebsning javoblari): Agar u1, o2 va o3 idlari 10, 12, 7 bo'lsa, idListning tarkibi 12, 7, 10 (chet elda) - yoki hali 2, 3, 1 (kebs) (ikkinchi "indexList" nomini keltirib chiqaruvchi)?
qo'shib qo'ydi muallif Aconcagua, manba
@basslo multimap, agar id boshqa bo'lmasa ...
qo'shib qo'ydi muallif Aconcagua, manba
Id bo'yicha bitta ob'ekt bormi? va siz noyobsizmi? Aks holda, xaritani ishlatish eng yaxshi usuli bo'ladi
qo'shib qo'ydi muallif basslo, manba

6 javoblar

Ob'ektlarni std :: map da saqlash uchun id kalit sifatida saqlashingiz mumkin. Keyin idList ni harakatlantiring, ob'ektni xarita </​​code> dan id bilan oling.

std::map objectMap;
for (auto itr = objectList.begin(); itr != objectList.end(); itr++)
{
    objectMap.insert(std::make_pair(itr->id, *itr));
}

std::list newObjectList;
for (auto itr = idList.begin(); itr != idList.end(); itr++)
{
   //here may fail if your idList contains ids which does not appear in objectList
    newObjectList.push_back(objectMap[*itr]);
}

// now newObjectList is sorted as order in idList
2
qo'shib qo'ydi
@Aconcagua for itr , barcha identifikatorlarni saqlaydigan idList yineleyicisidir. Shuning uchun * itr objectMap kalitini tashkil qiluvchi id dir.
qo'shib qo'ydi muallif Martin Zhai, manba
@Aconcagua Sen haqsan. Men bu istisnolar haqida o'ylamagan edim.
qo'shib qo'ydi muallif Martin Zhai, manba
@overseas Xo'sh, biz bu erda soddalikka qarshi samarali savdo qilamiz. Agar biz katta ma'lumotlar to'plamini kutsak yoki ma'lumot hajmi ma'lum bo'lmasa (masalan, umumiy foydalanish uchun mo'ljallangan kutubxonalarda), faqat kichik ma'lumotlar bilan ishlaymiz (yaxshiroq kodni qayta tiklash mumkin!), Lekin samaradorlik aniq ekanligiga amin bo'lamiz.
qo'shib qo'ydi muallif Aconcagua, manba
Men faqatgina savolni noto'g'ri talqin qilganim - bu "indexList" emas emas "idList" , shuning uchun ushbu ro'yxatning mazmuni, ehtimol ob'ektlarning identifikatorlari bo'lishi kerakligini aniqladi ro'yxat ... muammo uchun uzr.
qo'shib qo'ydi muallif Aconcagua, manba
Id ro'yxatini tasavvur qiling: {1, 2, 3} (identifikator), ob'ekt idlari {12, 7, 10}. Natija nima bo'ladi?
qo'shib qo'ydi muallif Aconcagua, manba
Ob'ekt ro'yxatidagi idlar tartiblash tartibiga mutlaqo aloqasi yo'q, bu esa umuman ololmaydi. Ob'ektning identifikatori bo'yicha hech narsa qilmang, to'g'ridan-to'g'ri indeks bo'yicha tartiblang. Afzallik: Siz buyurtmani to'g'ri qabul qilish uchun siz oddiygina xarita ustida oddiy iteratorni ishlatishingiz mumkin!
qo'shib qo'ydi muallif Aconcagua, manba
Idea yaxshi, lekin kichik tuzatish kerak: har ikkala ro'yxatda bir vaqtning o'zida (yani for (...; ...; + it it_id, ++ it_obj) ( std :: make_pair (* it_id, * it_obj); ) (navbatdagi tartibda ikkinchi ro'yxatda berilgan!).
qo'shib qo'ydi muallif Aconcagua, manba
Usecase noma'lum ekan, hech narsa afzal emas. Shuning uchun har ikkala vaziyatda ham muhim bo'lishi mumkin bo'lgan ikkala soddalikni va ishlashni ham qayd etgan edim. Shuning uchun ham yondashuvlarning hech biri umuman yaxshiroq emas.
qo'shib qo'ydi muallif overseas, manba
Quyidagi lavozimda men ushbu kodni vektor asosida yondashishni ishlatishdan ko'ra ancha sekin bo'lgan oddiy o'lchovlarni qo'shdim.
qo'shib qo'ydi muallif overseas, manba
Bu, albatta, pastga nisbatan osonroq yondashuvdir, lekin ro'yxat katta bo'lsa, xaritani ishlatish juda sekinroq bo'ladi. Xullas, ishlashni hisobga olganda, bu yondashuv rebalans (juda asimptotik jihatdan optimal bo'lsa ham) uchun juda yomon bo'ladi, soddalik esa, bu yondashuv juda yaxshi. Umuman olganda, agar siz elementni faqat bir marta joylashtirsangiz, xaritani foydali deb bo'lmaydi.
qo'shib qo'ydi muallif overseas, manba

Bu erda O (n log n) da ishlaydigan yana bir variant bor. Bu asimptotik jihatdan maqbuldir.

#include 
#include 
#include 
#include 
#include 

int main() {
  struct O {
    int id;
  };
  std::list object_list{{1}, {2}, {3}, {4}};
  std::list index_list{4, 2, 3, 1};
  assert(object_list.size() == index_list.size());

 //this vector is optional. It is needed if sizeof(O) is quite large.
  std::vector> tmp_vector(object_list.size());
 //this is O(n)
  std::transform(begin(object_list), end(object_list), begin(tmp_vector),
                 [](auto& o) { return std::make_pair(o.id, &o); });
 //this is O(n log n)
  std::sort(begin(tmp_vector), end(tmp_vector), 
            [](const auto& o1, const auto& o2) {
            return o1.first < o2.first;
            });
 //at this point, tmp_vector holds pairs in increasing index order. 
 //Note that this may not be a contiguous list.

  std::list tmp_list(object_list.size());
 //this is again O (n log n), because lower_bound is O (n)
 //we then insert the objects into a new list (you may also use some 
 //move semantics here).
  std::transform(begin(index_list), end(index_list), begin(tmp_list),
                 [&tmp_vector](const auto& i) {
                   return *std::lower_bound(begin(tmp_vector), end(tmp_vector),
                                            std::make_pair(i, nullptr),
                                            [](const auto& o1, const auto& o2) {
                                              return o1.first < o2.first;
                                            })->second;
                 });

 //As we just created a new list, we swap the new list with the old one.
  std::swap(object_list, tmp_list);

  for (const auto& o : object_list)
    std::cout << o.id << std::endl;

}

U juda katta va osongina harakatlanuvchi emas deb o'ylardim. Shuning uchun avval, faqat juftlarni o'z ichiga olgan tmp_vector ni yarataman. So'ngra men bu vektorni ajrataman.

So'ngra, index_list orqali o'tishingiz mumkin va ikkilik qidiruv yordamida mos ko'rsatkichlarni topishim mumkin.


Menga juda kichik kod bo'lsin, nima uchun xaritada eng yaxshi echim bo'lmasligi haqida gapirib beray. Xaritani ishlatsangiz, har bir kiritilganidan so'ng daraxtingizni muvozanatlashingiz kerak. Bu asympatotik tarzda qimmatga tushmaydi (chunki n marta rebalancing xarajatlarni siz bir marta tartiblash bilan bir xil), lekin doimiy kattalashadigan yo'l. "Doimiy xarita" bu ma'no bermaydi (unga kirish osonroq bo'lishi mumkin).

Keyin men "oddiy" vektor-yondoshuvimga qarshi "oddiy" xarita-yondashuvni belgilab qo'ydim. N yozuvlari bilan tasodifiy tartiblangan index_list yaratdim. Va mana bu (menda):

N         map         vector
1000      90          75
10000     1400        940
100000    24500       15000
1000000   660000      250000   

QAYD: Ushbu test eng yomon vaziyatni ko'rsatib turibdi, shuning uchun faqatgina index_list tasodifiy tartibda tartiblangan, ob'ektga obuna (xaritaga joylashtirilgan) tartiblangan. Shunday qilib, rebalancing barcha ta'sir ko'rsatadi. Object_list tasodifiy bo'lsa, ishlash yanada o'xshash bo'lib qoladi, natijada har doim ham yomon bo'ladi. Ob'ekt ro'yxati butunlay tasodifiy bo'lsa, vektor ro'yxati ham yaxshi bo'ladi.

Shunday qilib, allaqachon 1000 ta yozuv bilan farq juda katta. Shuning uchun vektorli yondashuv uchun ovoz beraman.

2
qo'shib qo'ydi
std :: make_pair (o.id, & o) Siz bu yerda ob'ekt identifikatorlari bo'yicha tartiblashasiz! Ular berilgan muammoga mutlaqo aloqasi yo'q! Idlar ro'yxatini tasavvur qiling: {1, 2, 3} (identifikator), ob'ekt identifikatorlari {12, 7, 10}.
qo'shib qo'ydi muallif Aconcagua, manba
Men faqatgina savolni noto'g'ri talqin qilganim - bu "indexList" emas emas "idList" , shuning uchun ushbu ro'yxatning mazmuni, ehtimol ob'ektlarning identifikatorlari bo'lishi kerakligini aniqladi ro'yxat ... muammo uchun uzr.
qo'shib qo'ydi muallif Aconcagua, manba
Masalan, haqiqatan ham shundaydir - 2, 3, 1 (bitta asosli) indekslar deb ham talqin qilinishi mumkin (xuddi kebs o'z javobida va men boshida qilgan kabi). Agar O1, O2, O3, masalan, 10, 12, 7 va idList 7, 10, 12 - va bo'lsa, bu misol haqiqatdan ham aniq bo'lar edi ...
qo'shib qo'ydi muallif Aconcagua, manba
Tezlik fikrlaringizdan tashqari: vektor qo'shni xotiraning afzalliklariga ham ega ...
qo'shib qo'ydi muallif Aconcagua, manba
Siz noto'g'ri va uni sinash kerak. Ha, u erda ob'ekt idlari bo'yicha tartiblashtiriladi, bundan keyin ikkilik qidiruv bilan qo'ng'iroq qilishingiz mumkin.
qo'shib qo'ydi muallif overseas, manba
Ha, savolning mazmuni foydali emas, bu qanday tartiblash kerakligini ko'rsatadigan misol.
qo'shib qo'ydi muallif overseas, manba

Ma'lumotlarning tashqi ko'rinishdagina qabul qilingani va konteynerlarning tanlovi yo'q.

assert( objectList.size() == idList.size() );
std::vector> wrapper( idList.size() );
auto idList_it     = std::begin( idList );
auto objectList_it = std::begin( objectList );
for( auto& e: wrapper )
    e = std::make_pair( *idList_it++, *objectList_it++ );
std::sort(
    std::begin(wrapper),
    std::end(wrapper),
    []
    (const std::pair& a, const std::pair& b) -> bool
    { return a.first

Keyin, asl konteynerga qayta nusxa oling.

{
   auto objectList_it = std::begin( objectList );
   for( const auto& e: wrapper )
      *objectList_it++ = e;
}

Ammo bu yechim optimallash emas, ishonchim komilki, kimdir yaxshi echimga ega bo'ladi.

Edit: The default comparison operator for pairs requires that it is defined both for first and second members. Thus the easiest way is to provide a lambda.

Edit2: for some reason, this doesn't build if using a std::list for the wrapper. But it's ok if you use a std::vector (see here).

1
qo'shib qo'ydi
@Aconcagua Ha, bu bilan bog'liq ekanligiga amin bo'ldim, ammo bu juda mashaqqatli edi.
qo'shib qo'ydi muallif kebs, manba
Bu ro'yxat bilan ishlamaydi, lekin vektor bilan, chunki std :: sort rastgele foydalanishni taqiqlovchi belgilarni talab qiladi, bu ro'yxatning iteratorlari emas, balki ...
qo'shib qo'ydi muallif Aconcagua, manba
objectList.sort([&idList] (const Object& o1, const Object& o2) -> bool
   { return std::find(++std::find(idList.begin(), idList.end(), o1.id),
       idList.end(), o2.id)
       != idList.end();
   });

The idea is to check if we find o1.id before o2.id in the idList. We search o1.id, increment the found position then we search o2.id: if found, that implies o1 < o2.

viktorina

#include 
#include 
#include 
#include 

struct Object {
    int id;
    string name;
};

int main()
{
  list objectList {{1, "one_1"}, {2, "two_1"}, {3, "three_1"}, {2, "two_2"}, {1, "one_2"}, {4, "four_1"}, {3, "Three_2"}, {4, "four_2"}};
  list idList {3, 2, 4, 1}; objectList.sort([&idList] (const Object& o1, const Object& o2) -> bool { return std::find(++std::find(idList.begin(), idList.end(), o1.id), idList.end(), o2.id) != idList.end(); }); for(const auto& o: objectList) cout << o.id << " " << o.name << "\n"; } /* OUTPUT: 3 three_1 3 Three_2 2 two_1 2 two_2 4 four_1 4 four_2 1 one_1 1 one_2 */ 
0
qo'shib qo'ydi

std::list has a sort member function you can use with a custom comparison functor.

Ushbu funktsiya funktsiyasi idList ichida id ob'ektini izlashi kerak va keyin std :: distance dan foydalanishi mumkin. idList . Ikkala ob'ekt uchun ham solishtiriladi va birinchi pozitsiya ikkinchi darajadan kichik bo'lsa, u to'g'ri bo'ladi.

Mana bir misol:

#include 
#include 
#include 
#include 

struct Object
{
    int id;
};

int main()
{
    Object o1 = { 1 };
    Object o2 = { 2 };
    Object o3 = { 3 };
    std::list objectList = { o1, o2, o3 };
    std::list const idList = { 2, 3, 1 }; objectList.sort([&](Object const& first, Object const& second) { auto const id_find_iter1 = std::find(begin(idList), end(idList), first.id); auto const id_find_iter2 = std::find(begin(idList), end(idList), second.id); if (id_find_iter1 == end(idList) || id_find_iter2 == end(idList)) { throw std::runtime_error("ID not found"); } auto const pos1 = std::distance(begin(idList), id_find_iter1); auto const pos2 = std::distance(begin(idList), id_find_iter2); return pos1 < pos2; }); for (auto const& object : objectList) { std::cout << object.id << '\n'; } } 

Ehtimol, bu juda ta'sirli emas, lekin imkoningizni hech qachon ko'rmaysiz. Agar siz hali ham sizni bezovta qilmasa, std :: vector dan farqli ravishda std :: list ga o'xshash echimlarni izlashingiz mumkin. Bu std :: masofa ni O (n) dan O (1) ga aylantiradi.

0
qo'shib qo'ydi
@kebs: Ha, men OP (taxminan "ehtimol" va "ehtimolliklar") deb taxmin qilaman, shuning uchun OPning " std :: list Odatda sekinroq ma'lumotlar tuzilmalari. Agar siz tezkor bo'lishingiz kerak bo'lsa, odatda std :: vector va std :: list dan foydalaning.
qo'shib qo'ydi muallif Christian Hackl, manba
@Aconcagua: Reallashtirish bo'lsa, to'g'ri. Xo'sh, men o'shimcha, OSh yanada batafsil talablarga ega bo'lganligini aytdim :)
qo'shib qo'ydi muallif Christian Hackl, manba
@Aconcagua: agar iteratorlar haqiqiy holatda bo'lishi kerak va std :: list ning tezligi qabul qilinmasa, unda ba'zi std :: unordered_map ga asoslangan echim yaxshi bo'lishi mumkin.
qo'shib qo'ydi muallif Christian Hackl, manba
@kebs: std :: list , yanada yaxshi hisoblash murakkabligi ta'minlovchi operatsiyalar uchun ham std :: list ga nisbatan std :: vector keshni joylashuvi tufayli. std :: list dan foydalanishning sababi ro'yxatning qolgan qismi o'zgartirilganda, iteratorlar bekor bo'lmaydilar.
qo'shib qo'ydi muallif Christian Hackl, manba
ehtimolini hech qachon ko'rmaysiz: : Mmmh, siz OP ma'lumotlar kattaligini taxmin qilyapsiz. Ehtimol, bularning dazillionlari bormi?
qo'shib qo'ydi muallif kebs, manba
Qabul qilaman, lekin ehtimol, o'shanda u juda katta miqdorda vektor ro'yxatga qaraganda sekinroq kiritilganligi sababli, uning aniq ro'yxatini tanlashi mumkinmi? Har doimgidek, "eng yaxshi" konteyner sizning "asosan" u bilan bog'liq bo'lgan masala.
qo'shib qo'ydi muallif kebs, manba
@ChristianHackl std :: unordered_map kafolat bermaydi!
qo'shib qo'ydi muallif Aconcagua, manba
Agar shart e bo'lsa. g. takrorlash/o'chirishda bekor qilinmagan yineleyicilar? Vektorlar bu shartni kafolatlay olmaydi, shuning uchun katta ma'lumotlarda ham ro'yxatni ishlatishga majbur bo'lasiz ...
qo'shib qo'ydi muallif Aconcagua, manba

Bunday vaziyatda men o'zimning identifikatorlari o'rniga ko'rsatgichlardan foydalanadigan bo'lsam, ajabtovur bo'lardim. Garchi; Buning uchun uskazlar bo'lishi mumkin.

Quyida keltirilgan barcha misollarda, identifikatorlarning identifikatorlari to'liq identifikatorlarni o'z ichiga olgan deb hisoblayman.

O'zingizni yozing

O'zingiz ma'qullaydigan masala - boshqa ro'yxatdagi identifikatorlarning tartibiga qarab ob'ektlar ro'yxatini tuzish/tartiblash.

The naive way of doing this, is simply O'zingizni yozing:

void sortByIdVector(std::list &list, const std::list &ids) { auto oldList = std::move(list); list = std::list{}; for (auto id : ids) { auto itElement = std::find_if(oldList.begin(), oldList.end(), [id](const Object &obj) { return id == obj.id; }); list.emplace_back(std::move(*itElement)); oldList.erase(itElement); } } 

Agar siz kiritilgan vektorni kiritishda foydalansangiz, u eng yaxshi ishlashi uchun ushbu kodni optimallashtirishingiz mumkin. Men uni tark etmoqchiman.

Tartib yordamida

Buni amalga oshirish uchun men std :: list o'rniga std :: vector emas, deb hisoblayman, chunki bu elementning indeksini so'rash uchun eng yaxshi konteyner. (Siz yana bir nechta kod bilan bir xil qilishingiz mumkin)

size_t getIntendedIndex(const std::vector &ids, const Object &obj)
{
    auto itElement = std::find_if(ids.begin(), ids.end(), [obj](int id) { return id == obj.id; });
    return itElement - ids.begin();
}

void sortByIdVector(std::list &list, const std::vector &ids) { list.sort([&ids](const Object &lhs, const Object &rhs){ return getIntendedIndex(ids, lhs) < getIntendedIndex(ids, rhs); }); } 

Qo'shish

Std :: vektor uchun ham mos keluvchi yana bir yondashuv elementlarni to'g'ri joyga joylashtirish va std :: sortiga nisbatan ancha samarali bo'ladi.

void sortByIdVector(std::vector &list, const std::vector &ids) { auto oldList = std::move(list); list = std::vector{}; list.resize(oldList.size()); for (Object &obj : oldList) { auto &newLocation = list[getIntendedIndex(ids, obj)]; newLocation = std::move(obj); } } 
0
qo'shib qo'ydi