Kada norite naudoti std :: list <T> vietoj std :: vector <T>?

Aš niekada nesinaudojau std::list<T> . Man buvo įdomu, kada žmonės jį naudoja, kai jau turime std::vector<T> , kuris yra panašus į nuolatinių atminties matricų. std::vector atrodo kaip puikus pasirinkimas, kai mums reikia serijinio konteinerio!

Taigi, mano klausimas yra toks:

  • Kada pageidaujate std::list std::vector ? ir kodėl tiksliai?
  • Kada norite std::vector virš std::list ? ir kodėl?

Jei yra veiklos aspektų, prašome išvardyti juos ir išsamų paaiškinimą / informaciją.

Jei įmanoma, pateikite keletą nuorodų, kad galėtumėte atsakyti.

26
20 февр. nustatė Nawazas vasario 20 d 2011-02-20 15:18 '11 prie 15:18 2011-02-20 15:18
@ 11 atsakymų

Geriau įterpti ar ištrinti sąrašus bet kur viduryje, geriau įterpti vektorius į pabaigą.

Vektoriai taip pat geriau tinka prieigai prie elementų.

Tai yra artefaktas, kaip jie įgyvendinami.

Taigi, jei kolekcija labai mažai keičiasi (palyginti su prieiga) arba pasikeitimai sutelkti pabaigoje, aš naudoju vektorių.

Jei pokyčių skaičius yra reikšmingas (palyginti su prieiga) ir jie nebėra, naudoju sąrašą.

Pavyzdžiui, skaitymas rinkinyje programos paleidimo metu ir beveik niekada nekeičiant jo (arba, jei pakeitimai pridedami prie galo), tai būtų geras kandidatas vektoriui.

Kita vertus, telefonų knygelės paraiška, skirta ypač populiariai ir nepatogiai roko žvaigždei, pažvelgtų į sąrašą. Iš tikrųjų norėčiau pažvelgti į prisijungimą prie duomenų bazės, bet tai buvo geriausias pavyzdys, kurį galėčiau rasti per trumpiausią įmanomą laiką: -)

Kalbant apie nuorodas, naujausiame projekte C ++ 0x yra dalis (23.3.4, sąrašai):

Šis sąrašas yra sekos konteineris, palaikantis dvikrypčius iteratorius, ir leidžia jums atlikti laiko įrašymą ir ištrinimą bet kurioje sekos dalyje, o saugojimo valdymas automatiškai apdorojamas. Skirtingai nuo vektorių ir reikalavimų, greita atsitiktinė prieiga prie sąrašo elementų nepalaikoma.

23.3.5 skirsnis (pagal vektorius):

Vektorius yra sekos talpykla, palaikanti atsitiktinių prieigos iteratorių. Be to, jis palaiko (nuvertina) pastovią operacijų įterpimo ir ištrynimo laiką pabaigoje; įterpti ir ištrinti viduryje, imtis tiesinių laiko.

15
20 февр. atsakymas pateikiamas paxdiablo 20 vasario mėn. 2011-02-20 15:21 '11 at 15:21 2011-02-20 15:21

Taigi, mano klausimas yra toks: kada norėtumėte std::list std::vector ?

Kai man reikia serijos konteinerio veikimo jautrioje zonoje, ir profiliavimas rodo std::list greičiau.

Kol kas tai niekada neįvyko.

(Gali būti linkęs bandyti std::list pirmą kartą išbandyti labai didelius objektus, kuriuose viduryje yra daug įterpimo / ištrynimo. Tačiau praktikoje aš niekada susidūriau su tokiu precedentu.)

29
20 февр. atsakymą sbi pateikė vasario 20 d. 2011-02-20 15:23 '11 prie 15:23 2011-02-20 15:23

Renkantis tarp std :: list ir std :: vector, reikia atsižvelgti į keletą kompromisų. Be to, std :: sąrašas nesusijęs su greta esančia atmintimi, tai gali būti labai naudinga, jei negalite sau leisti panaikinti iteratoriaus arba jei reikia nusistovėti pastovaus laiko pradžioje / viduryje / pabaigoje.

11
20 февр. Leandro TC Melo atsakymas, pateiktas vasario 20 d. 2011-02-20 15:23 '11 prie 15:23 2011-02-20 15:23

Vieninteliai (keli) kartus, kuriuos aš norėčiau std::list yra susiję su funkcijų nario list::splice . Jei naršote po sąrašus ar sąrašus, ši operacija gali būti daug greičiau nei naudojant std::vector .

7
20 февр. Atsakymą pateikė „ Blastfurnace “ vasario 20 d. 2011-02-20 19:19 '11, 19:19, 2011-02-20 19:19

Nereikia pakartoti pagrindų, bet tai, ką aš sužinojau, yra tai, kad jei įterpimo našumas yra aktualus, ir jūs turite „didelių“ objektų, tuomet jūs iš tikrųjų turėtumėte apsvarstyti std :: list, vėl tik įterpti pabaigoje. (Na, sąrašas ar galbūt protingas žymeklis / ptr _vector vektorius.)

Mes turėjome tam tikrų naudojimo atvejų, kai turėjome sukurti kolekcijas iš a priori nežinomo struktūros dydžio iš kelių mažų std :: string ir naudojant visiškai nužudytą std :: vektoriaus įterpimo našumą ir pridedant neapkrautą atmintį.

Std :: vektoriaus problema scenarijuje su nežinomu skaitikliu :

  • Kadangi vektorius visuomet bus paskirstytas, 50% sumažinsite tipiškų diegimų tipą (vieno eilutės vektorius, kuriame, pavyzdžiui, 24 baitai (MSVC), įskaitant mažą 100 000 elementų), gali turėti 2 MB viršutinę erdvę , ir jis bus dauginamas didesniems objektams, turintiems griežtesnių ar kitų didžiųjų elementų.)
  • Kiekvieną kartą, kai vektorius turi būti perskirstytas, jis turi nukopijuoti visus objektus, o tai nėra pigu, jei turite kažką sudėtingo. Akivaizdu, kad judėjimo semantika padės, bet jei patys objektai yra dideli, gali būti svarbi kopija. Nesvarbu, ar aritmetinis vidutinis įterpimo laikas (pabaigoje) teoriškai yra pastovus, jei kopijavę visus savo objektus kelis kartus kurdami vektorių. Galite pastebėti šią sėkmę.
  • Objektai tampa labai greitai: tik dviejų tuščių std :: string struktūra jau turi fiksuotą 48 baitų MSVC.

Tai ne bash std :: vektoriui, vis tiek naudoju jį pagal nutylėjimą, bet žinau, ko tikėtis iš jūsų duomenų!

4
10 апр. Martin Ba atsakymas, pateiktas balandžio 10 d 2014-04-10 01:20 '14 ne 1:20 2014-04-10 01:20

Be kitų atsakymų, node-base konteineriai ( list / asociatyvūs konteineriai) gali suteikti išimties garantiją.
Net jei konteinerio perkėlimo operacija (pavyzdžiui, įterpimas) išmeta išimtį, visi elementai / nuorodos / iteratoriai lieka galioti.
Tačiau linijinės atminties talpyklos (dalimis gretimos atminties ląstelės) gali suteikti tik pagrindinę garantiją. Kai įterpiamas įterpimas, net jei įterpimas nėra faktiškai įvykdytas, rodyklės / nuorodos / iteratoriai gali būti panaikinti (nors pati talpykla gali būti saugiai sunaikinta).

2
20 февр. Atsakymas pateikiamas Ise Wisteria 20 vasario mėn. 2011-02-20 20:37 '11 prie 20:37 2011-02-20 20:37

Kai kurie pasakys, kad turbūt niekada neturėsite naudoti savo kode esančios nuorodos ;; )

Viena iš problemų yra ta, kad vektoriai turi daug geresnę nuorodų lokalę, ir dėl to atsirandantys dideli našumo padidėjimai nusveria daugiau (algoritminiai) efektyvių operacijų naudą, pavyzdžiui, ištrinti ir įterpti į susietą sąrašą.

(Daugiau informacijos apie šią konkrečią problemą, su nuorodomis ir pan.

Taigi, dažnai std :: vektorius viršija std :: sąrašą, net jei atliekate tam tikrą skaičių operacijų, kurioms sąrašas yra natūralesnis (pvz., Pašalinant savavališką elementą, įterpiant jį į savavališką poziciją arba splaissavimą).

Tačiau atkreipkite dėmesį, kad net jei atliksite daugelį tokių operacijų, gali būti geriau „įdėti“ savo sąrašą į gretimą std :: vektoriaus buferį.

Kalbėsiu apie tai išsamiau šiame tinklaraštyje su kai kuriomis diagramomis ir kodų pavyzdžiais: http://upcoder.com/12/vector-hosted-lists/

Konkrečiu atveju, kai jums reikia ištrinti savavališkus elementus, tačiau nereikia įterpti jų į savavališkas pozicijas ar splazavimą, gera alternatyva susiaurintam sąrašui gali būti paprasčiausiai pažymėti įrašus kaip „negyvas“ ir praleisti šiuos mirusius įrašus iteracijos metu.

1
02 марта '15 в 13:24 2015-03-02 13:24 Thomas Young atsakymą pateikė kovo 2 d. 15 d. 13:24 2015-03-02 13:24

Naudokite sąrašą, kai jo invalidumo ir veiklos charakteristikų semantika atitinka jūsų reikalavimus.

Sąrašas gali įterpti / ištrinti / suskaidyti bet kur O (1), ir tai nepanaikina jokių iteratorių. Vektorius - O (n) įterpti / ištrinti, išskyrus galą, ir net tada įterpti, jei dydis <talpa; vektorius negali būti sujungtas. Veikimas yra dar subtilesnis nei tai, pavyzdžiui, kitame atsakyme minėta talpyklos vieta.

1
20 февр. Atsakyti Thomas Edleson vasario 20 d 2011-02-20 15:33 '11 prie 15:33 2011-02-20 15:33

std::list yra mano pranašumas beveik vieninteliam turtui, kurio vector nesutinka, ir kad žinios apie mano list visada bus tinkamos. Dėl šios priežasties aš galiu naudoti, kad turėčiau visus bet kokio turto, kurį man reikia atskiroje srityje, atvejus, taip pat pateikiu nuorodas į kitus naudojamus objektus. Geriausias pavyzdys, kurį galėčiau galvoti, yra vaizdų krautuvas, kuriame atmintyje saugoma tik viena pikselių kopija, tuo pačiu metu nurodant keletą objektų, kad jie galėtų ištraukti iš jo.

Visi vector nustatomi į O (1) prieigos laiką. Nors tai skamba kaip didžiulis turtas, praktiškai retai kada nors turiu prieiti prie duomenų struktūros elementų po žingsnio nuo „pirmojo“ iki „paskutinio“

1
31 авг. atsakymas, kurį pateikė Anne Quinn 2011-08-31 08:18 '11 at 8:18 2011-08-31 08:18

Naudodami std :: sąrašą, kai reikia keisti seką dažnai kitose vietose nei priekyje ar atgal. Šių operacijų pridėtinės vertės yra didelės std :: vektoriuje, palyginti su std :: list.

1
20 февр. Atsakymą pateikė ronagas 20 vasaris. 2011-02-20 15:20 '11, 15:20, 2011-02-20 15:20

Turėtumėte naudoti sąrašą, kai darote daug ištrynimų / įterpimų.

Vektorius galima naudoti, jei bendras elementų dydis nesikeičia, ir jei atliekate tam tikrą pakeitimą.

0
20 февр. Atsakymas pateikiamas Intrepidd 20 vas. 2011-02-20 15:24 '11 at 15:24 2011-02-20 15:24

Peržiūrėkite kitus klausimus apie žymes arba Užduokite klausimą

"192.102.6.96 - 192.102.6.96"