cpp, kuidas võrrelda kaartidega


Vastus 1:

Matemaatiliselt on kaart mudel, mis võtab võtme ja vastab väärtusega. Komplekt on kaardi juhtum, kus võti on identne väärtusega, millega see kaardistatakse. See kontseptsioon laieneb nende kahe objekti C ++ rakendusele.

Millal on std :: map kasulik: kaaluge kasutajakontosid salvestavat andmebaasi, oletame, et need on netflixi kontod. Seda netflixi kasutajate tabelit tähistav kaart võib saada kasutajatunnuse ja tagastada selle ID-numbriga seotud kasutajaobjekti. Seejärel saame kasutada ID-d kasutajakonto hankimiseks O (1) aja jooksul, räsides kontole ainulaadse kasutajatunnuse, ja konto otsimiseks vajate kõigi nende kasutajaandmete hankimiseks vaid ID-d.

Kas me saame seda teha standardiga :: set? Kuidas saaksime seda eelmist näidet komplektiga rakendada? Saame sisestada kasutajakontosid oma standardkomplekti :: set, kuid kui soovime kasutajakontot otsida, vajame oma kasutajakirje otsimiseks kogu kasutajakontot. Oodake hetk, kui meil on juba kasutajakonto teave, siis miks peaksime seda otsima? Mis siis, kui meil on ainult kasutajatunnus, ei saa me kontot enam O (1) aja jooksul kätte saada, peame kogu tabeli kordama, et leida sobiv konto ja see saab olema O (N).

Millal võiksite kasutada std :: map vs, millal võiksite primitiivide jaoks kasutada std :: map? Vaatleme struktuuri, mis on mõeldud kõigi algarvude salvestamiseks mõne suvalise väärtuse N alla. Kui me lihtsalt tahame teada, kas number on algarvude hulga liige, siis on std :: set mõttekas, võiksime lihtsalt kontrollida, kas suvaline täisarv väärtus 'k' on meie komplektis ja me ei pruugi olla mures indeksite või võtmete mõiste üle. Kuid kui meid huvitab algarvude järjestus, võime soovida võtme-väärtuse sidumist. Võib-olla tahaksime modelleerida jada p = {2, 3, 5, 7, 11, ...} ja sooviksime teada, kas p [j] = k mõne suvalise j & k väärtuse korral. Viimasel juhul võiksime kaaluda std :: mapi (kuigi ka std :: vektor võib olla hea valik).

Nii lühidalt:

  1. Häälestatud andmestruktuur on spetsiaalne kaardiandmete struktuuri tüüp, kus võti == väärtus ja C ++ STL-i definitsioonid kajastavad seda mõistet
  2. std :: map kui std :: set on üldiselt kasulikum, kuna std :: map pakub kiiret otsimist võtme abil koondväärtuste (pigem tervete objektide kui primitiivide) jaoks.
  3. std :: set on primitiivide jaoks sageli kasulikum, kuna primitiivse väärtuse k-> k kaardistamine on üsna meelevaldne

Vastus 2:

Paljud vastused ei puuduta kaardi rakenduse muutmist ja C ++ 17 jaoks konteinerite seadistamist, isegi kui see on asjakohane, seega käsitlen seda ainult.

Kuidas saate sõlme ühest konteinerist teise teisaldada?

Kuidas saab muuta kaardisõlme võtit?

Kui olete paigutanud teisaldatavad, kuid mitte kopeeritavad andmed kaardile või seadistanud, kuidas saaksite need uuesti välja tuua?

Nendele kõigile vastab C ++ 17, lisades uue läbipaistmatu andmestruktuuri ... sõlme käepide ... ja kaks uut liikme funktsiooni iga komplekti või kaardikonteineri jaoks, mis töötavad sõlme käepidemetega ... väljavõte, mis võtab sõlme kaardilt või seatud sõlme käepidemesse ja uus ülekoormus, mis võtab sõlme käepidemest ja sisestab selle kaardile või komplekti. Samuti on olemas uus mugavuse meetod, ühendamine, mis teisaldab kõik mittekopeerivad sõlmed ühes kaardis või seavad teise kaarti.

Sõlme käepide (C ++ 17)

Sõlme käepidemel on mitu omadust. See omab ekstraheeritud sõlme täpselt samal viisil, nagu seda teeb std :: unique_ptr, ja on seega ka teisaldatav, kuid mitte kopeeritav. Kui sõlme käepide omab sõlme, kui see on hävinud, siis sõlme hävitatakse ja jagatakse ... see tähendab, et tal peab olema ka jaotaja koopia, mida kasutatakse tehingu tegemiseks konteineris. See tähendab, et kahes konteineris kasutatavad eraldajad peavad ühest konteinerist teise teisaldatava sõlme võrdlema (operaator == tagastab tõene). Kõik vaikealokaatorid on võrdsed, seega pole see tavaliselt probleem.

Kuigi sõlm kuulub sõlme käepidemele nh, saab seda opereerida viisil, mis pole kaardil või komplektis olles võimalik. Näiteks saab eraldatud kaardisõlme võtit muuta, määrates selle nh.key () -le ja lasta kopeerimata kaardistatud väärtus teisaldada std :: move (nh.mapped ()) abil. Ekstraheeritud komplektisõlmel võib olla kopeerimata väärtus, mis viiakse välja, kasutades std :: move (nh.value ()).


Vastus 3:

Praegu pakub C ++ 8 standardit

assotsiatiivsed konteinerid

selles ruumis:

  • std :: komplekt
  • std :: multiset
  • std :: tellimata_hulk
  • std :: tellimata_multiset
  • std :: kaart
  • std :: multimap
  • std :: tellimata_kaart
  • std :: tellimata_multimap

Võite märgata, et siin on 3 variatsioonitelge:

  • seatud vs kaart.
  • tellitud vs tellimata.
  • kordumatu võti mitme võtmega.

Küsisite komplekti vs kaardi kohta; siiski tasub teada, kuidas valida kõigi 8 kombinatsiooni seast.

seatud vs kaart

Komplektis on võtmekomplekt. Võite sisestada ja eemaldada võtmeid komplektist, testida, kas võti on komplektis, ja korrata kõigi võtmete komplekti. Kui võti on komplekti sisestatud, on võti muutumatu. Pärast sisestamist ei saa võtit muuta. Pigem peate selle kustutama ja sisestama uue võtme, kui soovite olemasolevat võtit muuta.

Kaart seostab iga võtmega väärtuse. Väärtused võivad olla võtmest endast erinevat tüüpi. Tavaliselt on väärtused ka muutlikud. Ma saan väärtuse otsida selle võtme järgi ja seda väärtust muuta, kui selle leian.

Soovite kasutada komplekti, kui olete mures ainult olemasolevate võtmekomplektide pärast. Kui soovite jälgida hulga väärtusi, millega on seotud võtmed, soovite kaarti kasutada.

Oletagem näiteks, et tahtsin jälgida kõiki koosolekul osalevaid inimesi. Selleks võib komplekt olla piisav. Iga osaleja on komplekti liige ja saan osalejate loendi loomiseks kõik komplekti liikmed üle korrata.

Oletame, et minu koosolek on kaetud ja ma tahan jälgida kõigi minu koosolekul osalevate inimeste söögieelistusi. Nüüd tahan osalejate kaarti, et nad eelistaksid sööki. Sel juhul on võtmeks osaleja ja väärtuseks on eine eelistus. Saate muuta iga osaleja söögieelistusi, muutmata osalejat ennast. (Nii on vähem ebamugav ...)

tellitud vs tellimata

Assotsiatiivsed konteinerid ilma

tellimata

nimepakkumises

O (\ lg n)

juurdepääsuaeg. Nad nõuavad võtmeid, mis on

Võrreldav

ja

Tellitud rangelt nõrk.

Need on tavaliselt ehitatud tasakaalustatud binaarotsingu puudest. Kui kordate kõiki elemente, külastate võtmeid mitte kahanevas järjekorras. (Või ei suurene järjestus, kui kasutate vastupidiseid iteraatoreid.)

Nimes tellimata assotsiatiivsed konteinerid pakuvad amortiseeritud O (1) juurdepääsuaega tingimusel, et saate oma klahvi jaoks luua O (1) räsimisfunktsiooni. Kõnekeeles on need tuntud kui räsitabelid. Tellimata konteinerite tõhusaks toimimiseks vajate tõhusat räsimisfunktsiooni. Kui kordate kõiki elemente, külastate võtmeid meelevaldses järjekorras.

Millal peaksite kasutama tellitud vs tellimata? See sõltub mõnest asjast:

  • Kas peate kõiki võtmeid sageli deterministlikus järjekorras külastama? Kui jah, võib tellitud konteiner olla mõistlik valik.
  • Kas võrdlus on kiirem või aeglasem kui räsimine? Kui see on palju kiirem, võib tellitud olla parem. Kui see on palju aeglasem, võib tellimata olla kiirem.
  • Kas teate konteineri ligikaudset kogumahtu juba ette? Korrastamata konteineri suuruse muutmine võib olla kallis, samas kui tellitud konteinerisse sisestamine ei kipu metsikult toimima.
  • Millist mälujälge suudate taluda? Tellimata konteinerid kipuvad kiiruse järgi suurust vahetama.

Kui kirjutate oma koodi hoolikalt, võite proovida tellitud ja tellimata konteinerite vahel vahetada võrdlusaluseks, mis toimib teie konkreetse töökoormuse jaoks paremini.

Ühes minu kirjutatud rakenduses oli huvitav segu tellitud ja tellimata konteineritest, mis põhines just sellisel võrdlusuuringul. Olin veidi üllatunud, millised konteinerid võitsid ja kuidas see muutus, kui muutsin võtmete omadusi. Eelkõige muutis std :: stringist täisarvudega indekseeritud stringitabelisse liikumine räsifunktsioonide maksumust märgatavalt.

kordumatu võti mitme võtmega

Assotsiatiivsed konteinerid, mille nimes ei ole mitut, lubavad konteineris igast võtmest ainult ühe eksemplari. See tähendab, et iga võti peab olema ainulaadne. See pakub sarnast semantikat kui 1-D massiiv, kus igas indeksis on üks element. Juba konteineris oleva võtme lisamine on loogiline viga.

Assotsiatiivsed konteinerid, mille nimes on mitu, võimaldavad iga võtme mitut eksemplari. Iga võtit saate sisestada nii palju kordi kui soovite. Korduvaid võtmeid hoitakse sisestamise järjekorras.

Märkus: See on oluline isegi multiseti puhul, kuna võrdluskriteeriumid eristavad ekvivalenti võrdsest. Kaks võtit on samaväärsed, kui kumbagi ei võrrelda vähem kui teist; võrdlusfunktsioon pole aga vajalik võtmeobjekti kõigi väljade arvestamiseks.

Millise peaksite valima? See sõltub tõesti probleemist, mida proovite lahendada. Anekdootlikult olen vajanud multisette või multimapse harva.

Kui peate jälgima kõiki "võtme" eksemplare, mida näete, olenemata sellest, kas mõned neist on võrdsed või mitte, on multiset või multimap õige valik. Vastasel juhul soovite tõenäoliselt mitte-mitut komplekti või kaarti.

Üks huvitav kasutus std :: multiset või std :: multimap on prioriteetse järjekorrana. Kasutage võtmena prioriteeti. Start () poolt tagastatud element on teie kõrgeima prioriteediga üksus. Üksuste loetelu peetakse järjestuses, nii et kui anda iteraator, mis osutab üksusele, saate kiiresti kindlaks teha, mis on vahetult enne ja vahetult pärast seda. Eriti kui prioriteeti tähistab tegelikult aeg - see tähendab, et see prioriteedijärjekord on tegelikult aja järgi järjestatud sündmuste järjekord -, saate odavalt kindlaks määrata, millised sündmused on kindla aja lähedusse kavandatud.

See töötab siiski ainult tellitud multiset ja tellitud multimapiga.

std: prioriteetsus

võib olla parem valik, kui vajate ainult kiiret juurdepääsu esmatähtsale üksusele ja te ei saa kasu multiseti või multimapide täielikult sorteeritud olemusest. (Vt

std: prioriteetsus

lisateabe saamiseks.)


Vastus 4:

Noh, ma oskan sellele vastata.

Kaardid

Kaardid vajavad võtmeid. Iga võtme jaoks on teil teatud tüüpi väärtus (ed).

Nüüd võib võti olla ükskõik milline, täisarv, string või isegi objekt (varustatud täiendava võrdlusfunktsiooniga). Nii võivad olla ka väärtused.

Vaata seda:

kaart M; // täisarv võti - täisarv väärtusM [3] = 2;kaart S; // string võti - täisarvS ["ahar"] = 26;

See on põnev.

Oletame, et soovite oma sõprade sünnipäevad salvestada. Deklareerite lihtsalt kaardi ning talletage nende nimed ja sünnikuupäevad lihtsalt lihtsat ülesannet tehes. See on nagu Pythonis sõnastik.

Komplektid

Komplektide puhul see nii ei ole. Komplektid ei vaja (võtme, väärtuse) sidumist. Need sisaldavad lihtsalt ükskõik milliseid väärtusi (loomulikult funktsioonide võrdlemise või vajaduse korral operaatori ülekoormusega), mida soovite nende sisaldada. Näiteks:

seatud S;S. sisestada (13);seatud T;S.insert ("ahar");seatud X;S. sisestage (teie objekt);

Esinemise seisukohalt on neil sarnasusi. Otsing, sisestamine, kustutamine jne on järjekorras

O (logn)

mõlemas (tänu kuulub

Punane must puu

, asi, mida te oma andmestruktuuri kursusel kartsite: P). Kuid rakendamise ja kasutamise erinevuste tõttu võivad olla teatud üldkulud.

Täiendav märkus:

Kui teete vaatluse, leiate, et põhistruktuurilisest vaatenurgast on komplektid ja kaardid erinevad. Nii et teie esitatud küsimus võib olla natuke huvitavam, kui mõelda sellele viisil, kus saate komplekte kasutada kaartide vaheldumisi ja vastupidi.

See võib viia meid huvitava küsimuseni: mis vahe on komplektil > ja kaart ? See on üsna õige küsimus, sest selle stsenaariumi korral võite mõelda paari esimesele elemendile komplektis, mis on samaväärne kaardi võtmega!

Näiteks:

kaart M;M.insert ({"motta", 13});seatud > S;S.insert ({"motta", 13});

Näete, et ülaltoodud komplekt võib olla potentsiaalne asenduskaart kaardile.

Kas nad on samaväärsed? Noh, ei.

Esiteks ei tohi kaart sisaldada sama klahvi jaoks erinevat täisarvu, nagu oleme eespool deklareerinud. Aga komplekt saab.

Niisiis,

M.insert ({"ahar", 13)};S.insert ({"ahar", 13});M.insert ({"ahar", 26});S. sisestada ({"ahar", 26});

muudab hulga suuruseks 2, kuid kaardi jaoks on see 1.

Teiseks peaksite juba teadma, et need C ++ konteinerid kasutavad iteraatoreid, mida kasutatakse nende konteinerite elementide suunamiseks. Lihtsalt mõeldes on nendes konteinerites olevatele andmetele juurdepääsemiseks vaja kordajaid.

Nüüd vaadake seda:

seatud > S;S. sisestada ({"ahar", 26});auto see = S. algus (); // see on nüüd iteraator ("ahar", 26)

Millegipärast kavatsete sellega korratud vastava paari väärtuse muuta väärtuseks 26 kuni 13. Proovite järgmist:

see-> teine ​​= 13;

Umm ... nah. Sa ei saa seda teha.

Põhjus on mõnevõrra keeruline. Lihtsamalt öeldes on C ++ komplekti iteraatorid nagu pidevad iteraatorid. Seega ei saa te vastavat andmeväärtust lihtsalt kohapeal muuta. Peate selle komplektist kustutama ja seejärel lisama oma uue väärtuse järgmiselt:

S.erase (see);paar p = {"ahar", 13};S. sisestada (p);

: |

Kaartide puhul kehtib see täielikult:

kaart M;M.insert ({"motta", 13});auto see = M. algus ();see-> teine ​​= 26;

Loodan, et mul on kõik korras. : P

Täname lugemast.


Vastus 5:

Kaart on andmestruktuur, mida kasutatakse väärtuste otsimiseks võtmete abil, komplekt on aga vaid väärtuste kogu.

Rakendamise mõttes ei rakendata neid tavaliselt nii erinevalt ja mõlemad kasutavad tavaliselt punase-musta puid kapoti all, et saada logaritmiline ajaline keerukus enamiku toimingute jaoks. Üks erinevus olenevalt teostustest on see, et komplekt oleks elementide punane-must puu, samal ajal kui kaart oleks (võti, väärtus) kahekordse elemendi punane-must puu, mis on sorteeritud esimese elemendi (võtme) järgi kahekordne.


Vastus 6:

Kaart kaardistab ühe objekti teise objektiga. Hulk on järjestatud objektide kogum. Kaarti kasutatakse sageli objektide juurde pääsemiseks indeksi abil nii, et objectMap [i] sisaldab objekti indeksiga i. Komplekti saab kasutada objektide salvestamiseks, mille lisakasu on see, et komplekt tuvastab, kas objekt sisaldab seda juba, ja salvestab objektidest ainult ühe üksuse. Komplekti objektidele pääsete juurde aga ainult selle üle itereerides või komplekti esimese või viimase elemendi hankimisel.


Vastus 7:

std :: map on assotsiatiivne, järjestatud massiiv. See tähendab, et see salvestab paari ja võtme abil võite jõuda väärtuseni. Samuti võite kordada paarid ja iteratsioon järgneb võtmete heale järjestusele.

std :: set on ainult väärtuste kogu. Jällegi võite selle üle korrata ja jällegi järgneb iteratsioon väärtuste korralikule järjestusele. Kuid ülaltoodud seost ei ole, võite esitada ainult selliseid küsimusi nagu "kas see väärtus on komplektis?" Ja selleks peab teil juba olema kõnealune väärtus.