Keskustelu: Ohjelmointikysymykset: C++: Tehokkain STL-säiliö iteraatioon?

Mikähän STL:n säiliöistä on tehokkain vaihtoehto, kun tarkoituksena on säilöä muuttumattomia olioita, ja sen jälkeen iteroida sen läpi alusta loppuun? Tässä esimerkki, jossa olen käyttänyt std::vector-säiliötä:

const std::vector < Point < DataType > > sphrerePoints = {
    Point < DataType > ( circle.center ().x (), circle.center ().y () - circle.radius () ),
    Point < DataType > ( circle.center ().x () + circle.radius (), circle.center ().y () ),
    Point < DataType > ( circle.center ().x (), circle.center ().y () + circle.radius () ),
    Point < DataType > ( circle.center ().x () - circle.radius (), circle.center ().y () )
};

for ( auto point : sphrerePoints ) {
    // ...
}

Vaihtoehtoina olen miettinyt std::list- ja std::forward_list-säiliöitä. Ymmärrän toki, että tässä kyseisessä tilanteessa ei säiliön vaihtaminen vaikuta suorituskykyyn merkittävästi. Tästä kuitenkin tämä kysymys heräsi, enkä Googlellakaan löytänyt vastausta.

Etsit ehkä väärällä tavalla: sinun ei pitäisi etsiä tietoa nimenomaan C++:n eri luokista vaan niiden edustamista tietorakenteista yleisesti.

Tiedon lukemisessa vektori on nopein, koska data on muistissa peräkkäin ja minkä tahansa alkion osoitteen pystyy suoraan laskemaan. Vektorin olennainen huono puoli on, että alkion lisääminen tai poistaminen vaatii koko vektorin loppuosan siirtämistä, minkä vuoksi muutokset alkupuolelle ovat hitaita.

Linkitetyssä listassa tieto on hajallaan. Selaaminen vaatii enemmän muistioperaatioita ja on siis hitaampaa. Listaa on möys pakko selata järjestyksessä, vaikka haluttaisiin vain hakea yksi alkio listan keskeltä. Listan etu on, että muutoksia voi tehdä ilman, että muita osia tarvitsee siirtää.

Kiitos vastauksesta. Olenkin lukenut noiden luokkien käyttämistä rakenteista, ja toistaiseksi jäänyt ilman vastausta. Jatkan opiskelua :)

Toisaalta, jos kysymyksessä on juuri sellainen tilanne, että halutaan lisätä uusia alkioita listaan ja aina iteroida koko lista läpi, niin silloin linkitetty lista sopii mielestäni parhaiten.

Tilanne on juuri se, mitä koodissa näkyy. Säiliöön säilötään alustuksessa nuo oliot, minkä jälkeen se iteroidaan läpi. Sen sisältöä ei muuteta.

Niin no sitten siinä tapauksessa, jos sinne ei enää lisätä uusia alkioita myöhemminkään, niin ei lieni järimmin merkitystä käyttääkö random accessiin perustuvaa vectori vai linked listiä.

Jees, hyvä tietää.

Nyt on pakko kysyä, että mikä Metabolixin vastauksessa oli niin vaikeaa ymmärtää?

En tiedä. Oliko se jonkun mielestä vaikea ymmärtää?

Lisäys:

Päädyin siihen, että viittaat tähän

vesikuusi kirjoitti:

Olenkin -- toistaiseksi jäänyt ilman vastausta. Jatkan opiskelua :)

Ymmärsin kyllä Metabolixin viestin, mutta mielestäni se ei vastannut siihen, kumpi on tässä kohtaa tehokkaampi, vektori vai linkitetty lista.

Metabolixin viestin luettuani tiedän, että vektori suoriutuu paremmin tuon tiedon lukemisesta, kun linkitetty lista hoitaa populoinnin nopeammin. Kuten Triton sanoi, ei sillä taida paljon merkitystä ollakaan, kumpaa käyttää tällaisessa tilanteessa.

vesikuusi kirjoitti:

Ymmärsin kyllä Metabolixin viestin, mutta mielestäni se ei vastannut siihen, kumpi on tässä kohtaa tehokkaampi, vektori vai linkitetty lista.

Kyllä se vastasi:

Metabolix kirjoitti:

Tiedon lukemisessa vektori on nopein. – – Linkitetyssä listassa – – selaaminen vaatii enemmän muistioperaatioita ja on siis hitaampaa.

Ero on siinä, että vektorilla seuraava alkio saadaan, kun vain siirrytään seuraavaan muistiosoitteeseen, kun taas listassa seuraava osoite pitää lukea muistista. Prosessorin eri välimuistit lisäävät eroa, koska vektorin tapauksessa tieto on muistissa peräkkäin ja yhtä alkiota haettaessa välimuistiin tulee usein jo valmiiksi myös seuraavia alkioita, kun taas listassa alkiot voivat olla (toteutuksesta riippuen) missä tahansa eikä välimuistiin välttämättä tule kuin yksi ainoa alkio kerrallaan.

vesikuusi kirjoitti:

Metabolixin viestin luettuani tiedän, että – – linkitetty lista hoitaa populoinnin nopeammin.

En sanonut noin. Vektori on hyvin nopea, kun alkiot lisätään vain loppuun. Vielä lisää nopeutta saadaan, jos alkioiden määrä tiedetään valmiiksi ja vektorille pystytään varaamaan kerralla riittävästi tilaa, mutta muutenkaan vektori ei suinkaan varaa lisää tilaa joka kerta vaan ennakoi tulevia lisäyksiä ja varaa saman tien vähän ylimääräistä tilaa. Linkitetystä listasta on etua vain, jos alkioita lisätään väleihin tai jos vektoria joudutaan jostain syystä laajentamaan ja pienentämään poikkeuksellisen monta kertaa.

Niin aivan, eilen vielä tajusin tuon

Metabolix kirjoitti:

Vektorin -- muutokset alkupuolelle ovat hitaita.

Mutta tänään se olikin jo unohtunut...jees kiitti, eiköhän se ole se vektori sitten :)