Miben gyorsabb a C++ std::set az std::vector-nál? Van amiben gyorsabb?

Ez két teljesen eltérő funkciójú adatszerkezet.

A vektor egy dinamikus "tömb", míg a set kulcs-érték párokat tartalmaz.

[link]

[link]

Mármint a set sima kulcsokat tartalmaz.

Amúgy igaza van az elsőnek, teljesen más a két adatszerkezet célja: a vector egy szekvenciális adatszerkezet, tehát az elemeket egy adott sorrendben tárolja, a másik pedig a halmazt, többé-kevésbé mint a matematikai fogalmat implementálja.

Amúgy ha használsz egy vectort, amiben rendezetten tartod az elemeket, akkor kb ugyanott vagy, mint a halmaz esetén.

Közös függvények, no, pont erről pofázunk, hogy az kevés.

A konstruktora a setnek lesz a lassabb, mivel egy fát kell fölépítenie. Destruktor, operator= szintúgy, hasonló okok miatt.

Az iterátoros függvények (begin, end, rbegin, rend) szintén a setben lassabbak (bár itt is konstans idő alatt futnak), mivel neki bonyolultabb az iterátora.

Size mindkettőben konstans idő, max_size szintén, empty szintén.

Swap mindkettőben konstans.

Erase, insert a setben gyorsabb (általánosságban), mivel csak pointerezgetni kell, nem másolni.

Kb ennyi. Az insert, erase-ben veri, de akkor már a lista még jobb.

Ezt így tök jól fel lehet sorolni, de semmi értelme.

Másra való.

Ha az egyik kell, használd azt, ha a másik, akkor azt.

Nem bonyolult...

Az alapvető probléma,hogy nem írtad,hogy milyen feladatra akarod használni. Van eset amikor az egyik "gyorsabb" van amikor a másik. Itt nem a c++ beli megvalósítás a kérdés, hanem a tervezés. Amikor egy feladat megvalósításához konkrét adatszerkezetet akarsz használni,akkor figyelembe veszed,hogy az adatszerkezeteken végzendő műveleteknek milyen műveletigényük van.

Pl.: 1..10 -ig a termszetes számok. Ábrázolhatom vektorban őket,de akár bináris fa-ként is. Viszont ha csak annyit tudunk,hogy a felhasználó véletlen sorrendben fogja az adatokat beírni,és a feladat az,hogy írjuk ki őket rendezetten,akkor vektoros ábárzolás esetén rendezni kell, míg bináris fa(láncolt listás reprezentációval) már szimplán egy rekurzív fabejáró algoritmussal kiíraható rendezetten,ami hatékonyabb lesz,mint vektorban először rendezni, vagy rendezés közben kiírni.

Tehát az adatszerkezeteken végezhetőek mveletek,de nem mindegy mi a feladat.

A kérdésedre vonatkozóan,tahát a set és vector -nál például az összeadás set esetében orto(n+m) műveletigényű,míg vector esetében teta(n+m), feltételezve,hogy mindkét adatszerekzetet uyanolyan típusú elemekkel töltötted fel,és az elemek között az összeadás hatékonyan van megírva.Egyébként a set az a magyarban az ún. zsák adatszerkezet,ami nem teljesen ugyanaz,mint a halmaz.

Megjegyzés:

C++ -ban az STL Container-ek hatékonyan vannak megírva és generikusak. Viszont,ha a feladat specializálódik egy kérdésre,akkor érdemesebb a saját magad elkészíteni az adatszerkezetet a speciális esetre,hiszen egy adatszerkezetet többféle képpen is lehet ábráhzolni(tömbösen,láncolt listásan).