STL eszközök és használatuk
Czirkos Zoltán, Dobra Gábor · 2019.03.31.
Jegyzet 10. fejezet: STL eszközök és használatuk
A C++ tartalmaz csomó olyan adatszerkezetet és osztályt, amire minden programnak szüksége lehet. Ilyenek a sztring, a duplán láncolt lista, a dinamikus tömb és még sok egyéb. Ezt az osztály gyűjteményt STL-nek, "Standard Template Library"-nek hívják. A programozást nagyban megkönnyítik, mert ezek a C++-ban szabványosak, bármikor használhatóak, nem kell őket újra megírni.
Ezeknek az osztályoknak a részletes megértéséhez szükség van az eddig bemutatott C++ nyelvi elemek ismeretére is (pl. osztály sablonok, iterátorok), ezért általában a félév végén szoktak szerepelni a tananyagban. Az egyszerűbb felhasználáshoz azonban – amilyen például a nagy házi feladatokhoz is elegendő – ez nem olyan lényeges még.
A házik közül a legtöbb feladat (és az összes olyan feladat, amit érdemes választani) nem valamilyen alapvető osztály létrehozására koncentrál. Ilyenkor igazából nem éri meg gürcölni a saját, kézzel megvalósított dinamikus sztringgel (char* rémálom), saját dinamikus tömbbel stb. Hogy az energia ne ezeknek a megvalósítására menjen el, röviden leírjuk, milyen beépített tároló osztályokat ad a C++. Ennek az irománynak az áttanulmányozása után sokkal könnyebb lesz a házit elkezdeni.
Ahogy az OOP tervezésről szóló fejezet is említi, a házi tervezésekor és az írásának az elején érdemes feltételezni, hogy ezeket a tárolókat mind használhatjuk. Ha a feladat és a laborvezető máshogy rendelkezik, akkor persze muszáj egy hasonlót írni magunknak.
Az STL részletes dokumentációja elérhető itt:
Az osztályok mind az std névtérben vannak, és érdemes is kiírni. Az using namespace std; erősen ellenjavallott, a legváltozatosabb, furcsa hibákat tudja okozni.
Dinamikusan átméreteződő, okos string, az összes értelmes operátora átdefiniálva. Hasonló a memóriakezeléses fejezetben bemutatotthoz, de annál jóval bővebb funkcionalitású, és sokkal ügyesebben kezel dinamikus memóriát. Például nem minden karakter hozzáfűzésénél foglal és másol memóriát, csak ritkán.
#include <string>
int main() {
std::string s; // Üres stringet hozunk létre.
// A méretével nem kell foglalkozni.
std::cout << s.size(); // Tudja a méretét, le lehet kérdezni,
std::cout << s.length(); // És hívhatjuk hossz-nak is.
std::string m("Hello vilag!"); // 0-val lezárt sztringet is átvehet a konstruktora.
std::string a = "alma"; // Ez a konstruktor implicit.
std::string k = "korte";
s = "Hello"; // Beállítjuk valamilyen értékre.
s += " vilag"; // Hozzátoldunk egy másik sztringet.
s += '!'; // Hozzátoldunk egy karaktert.
s.push_back('!'); // Hozzátoldunk egy karaktert, mint egy vector-hoz
s.pop_back(); // Ledobunk a végéről egy karaktert, mint a vector
std::cout << s; // Kiírjuk a konzolra.
std::cin >> s; // Beolvassuk valamilyen szóközig (azaz egy szót).
std::getline(std::cin, s); // Beolvassuk enterig.
std::getline(std::cin, s, '\t');// Beolvassuk tablulátorig.
if (s == m) // Összehasonlítjuk.
std::cout << "egyformák!";
if (a < k)
std::cout << "a < k"; // a (kvázi) előbb van az ABC-ben.
s[0] = 'h'; // hello vilag!
s.erase(2, 3); // Töröl a belsejéből: "he vilag!"
s = m.substr(2, 3); // m belsejéből egy darab, "llo"
int i = a.find("lm"); // Keresés: 1, mert "alma" szóban "lm" pozíciója.
a.insert(3, "er"); // Beszúrás: "alma"-ból almera lesz.
std::cout << a.c_str(); // A tartalmáról C-s sztringet, azaz
// 0-val lezárt const char*-ot is kérhetünk.
}Ezen kívül van iterátora, pont, mint az std::vector-nak. Például így is bejárhatunk egy sztringet, és kiírhatjuk karakterenként külön sorba:
std::string s = "hello";
for (auto it = s.begin(); it != s.end(); ++it)
std::cout << *it << std::endl;Az iterátora random access, tehát akár rendezhetjük is (erről később is lesz szó).
std::string s = "hello";
std::sort(s.begin(), s.end()); // ehlloAz egyetlen lényeges különbség az előadáson / jegyzetben / laboron látott sztringekhez képest, hogy a belsejében is lehet lezáró 0, akár csupa '\0'-kból is állhat:
std::string s(10, '\0'); // 10 db lezáró nullaA template-es fejezetben volt szó egy egyszerű vektor osztálysablonról, ami bármilyen elemeket tartalmazhat. Emlékeztetőül: a vektor egy átméretezhető, egydimenziós tömb, a tartalmazott típust <> között kell megadni. Például egész számokat tartalmazó tömb: std::vector<int>.
Az ott bemutatottnál jóval bővebb funkcionalitású az std::vector, és a dinamikus memóriakezelést sokkal profibban csinálja: nem hív felesleges konstruktort, és csak "ritkán" foglal újra.
A használata pont olyan, mint egy tömbnek, de a hosszát is le tudjuk kérdezni a .size() tagfüggvénnyel. Ezen kívül specialitása, hogy úgy "varázsol" a dinamikus memóriával, hogy ha a végére szúrunk be vagy veszünk el elemet, az konstans idejűnek tekinthető (de természetesen dinamikus memóriaterületre kerül).
#include <vector>
int main() {
std::vector<int> t; // Tömb, ami egyelőre üres.
std::vector<double> d(50); // 50 elemű double tömb.
d[23] = 3.14;
t.push_back(1); // A tömb végére rak egy új számot,
t.push_back(2); // és meg is növeli a tömb méretét.
for (int i = 0; i < t.size(); ++i) // Kiírjuk a tömb tartalmát,
std::cout << t[i] << ' '; // az aktuális méretét a size() adja meg.
std::cout << std::endl;
t.clear(); // Kitörli a tömböt, újra üres lesz.
d[60] = 10.3; // NEM SZABAD!!! Továbbra is 0..49 között
// indexelődik az 50 elemű tömb.
d.at(120) = 0.012; // Ugyanaz, mint az indexelő, csak
// ellenőrzi, hogy nem hivatkozunk-e
// nem létező indexre. Ha igen, kivételt dob.
}Szintén van iterátora, ami random access, tehát ugyanúgy járhatjuk be, vagy rendezhetjük, mint pl. a sztringet:
#include <vector>
#include <algorithm> // rendezéshez, std::sort
#include <cstdlib> // rand() véletlenszámokhoz
int main() {
std::vector<int> t;
t.resize(100); // Méretezzük át a tömböt 100 eleműre.
srand(time(0)); // Véletlenszám-generátor indítása
for (int i = 0; i < t.size(); ++i)
t[i] = rand() % 200; // Minden elem: véletlenszám 0..199 között
std::sort(t.begin(), t.end()); // Növekvő sorrendbe az egész
// tömb, az elejétől a végéig.
for (auto it = t.begin(); it != t.end(); ++it)
std::cout << *it << ' '; // Bejárjuk, és szóközzel elválasztva kiírjuk.
std::cout << std::endl;
}Érdemes abba belegondolni, hogy az egyszerű másolás, mint lehetőség, illetve a méret az adatokkal történő egységbe zárása miatt már sokszor megéri std::vector-t használni sima tömb helyett. Például nem kell átadnunk egy függvénynek a tömb méretét, mert az már tartalmazza azt:
double atlag(const double *tomb, int meret);
double atlag(const std::vector<double> &tomb);Egy függvény, amely valahány (nem kell tudni előre, mennyi) stringgel tér vissza:
std::vector<std::string> beolvas();Az std::deque egy mindkét végén módosítható várakozási sor. Az std::stack és az std::queue pedig std::deque-et használó adapterosztályok. Bővebben az adapteres fejezetben volt róluk szó.
Az iterátoros fejezetben bemutattunk egy egyszerű, egyszeresen láncolt listát. Az std::list is ilyen, csak kétszeresen láncolt, és a lista mellett a méretet is nyilvántartja.
#include <list>
#include <cctype>
int main() {
std::list<std::string> szavak; // stringekből álló lista (!)
szavak.push_back("alma"); // alma (... került az üres lista végére)
szavak.push_back("korte"); // alma, korte
szavak.push_front("malna"); // malna, alma, korte (elejére teszi!)
szavak.push_front("villa"); // villa, malna, alma, korte
std::cout << szavak.size() << " szót tartalmaz.\n";
szavak.remove("villa"); // kitöröljük a kakukktojást
std::cout << "Az első elem: " << szavak.front() << std::endl;
std::cout << "Az utolsó elem: " << szavak.back() << std::endl;
std::list<std::string> masolat;
masolat = szavak; // Lemásoljuk a listát: értékadás!
while (!masolat.empty()) { // Amíg nem üres a lista:
std::cout << masolat.back() << ' '; // Kiírjuk az utolsó elemet...
masolat.pop_back(); // és kitöröljük.
}
}A legtöbb tároló osztályokhoz létezik iterátor osztály, amely legegyszerűbb esetben arra jó, hogy az összes adaton egy ciklussal végig tudjunk menni. A láncolt listánál az adatszerkezet miatt az iterátor tényleg erre és csak erre jó.
Összevissza nem ugrálhatunk, mint mondjuk egy vektornál, mert mindig csak a következő és az előző elemet ismerjük. Épp ezért sehogy máshogy nem érjük el a lista belsejét, csak iterátorokkal; egy lista igazából iterátor nélkül nem sok mindenre jó.
std::list<std::string>::iterator it; // Sztringekből álló lista iterátora.
// Indulunk a lista elejéről (begin). Addig megyünk, amíg
// el nem érjük a lista végét (end). Amikor egy adott elemmel
// elvégeztük a dolgunkat, ugrunk a következőre (++).
for (it = szavak.begin(); it != szavak.end(); ++it) {
char & c = (*it)[0]; // Az iterátor által mutatott sztring
// kezdő karakterére referencia.
c = toupper(c); // nagybetűsítjük az első karakterét
std::cout << *it << ' '; // kiírjuk a szót.
}Figyeljük meg, hogy a lista belső felépítéséről semmit nem tudunk, ez el van rejtve előlünk. Az iterátor viszont együtt dolgozik a listával; tudja, hogy a lista belsejében mi hogyan van megoldva. De azt nekünk nem kell tudni, legyen az az iterátor dolga.
A belső adatszerkezet miatt az iterátor elég buta, viszont néhány műveletet meg lehet oldani a vektornál sokkal egyszerűbben, az elemek átláncolásával. Például a rendezést:
szavak.sort(); // rendezzük ábécésorrendbe!
std::list<std::string>::iterator it;
for (it = szavak.begin(); it != szavak.end(); ++it)
std::cout << "*it << ' ';Szintén az adatszerkezet sajátossága, hogy lassú. Ha sorban szeretnénk belepakolni az elemeket, majd bejárni, a vektor gyorsabb. Ha az elejére és a végére, akkor a deque gyorsabb. Ha a közepére, sok esetben akkor is gyorsabb a vektor, még az átméretezéssel együtt is. Bizonyos speciális problémák megoldására vagy megkerülésére viszont jól használható, pl. iterátor invalidálódás, vagy költségesen mozgatható elemek.
A tárolók kapcsán az egyik legfontosabb hiányosság C++11 előtt az volt, hogyan inicializáljuk őket beégetett adatokkal. A tömböt ugyanis lehet egy beépített nyelvi elemmel:
int arr[] = {5, 2, 3, 4, 1}; // 5 elemű, intekből álló tömb, előre feltöltve:C++11-ben bevezettek egy új típust a jobb oldalon álló, kapcsos zárójeles kifejezésre. Ez lett az std::initalizer_list. Arra jó, hogy a tárolóknak így már lehet írni olyan konstruktort, ami inicializáló listát vesz át. Az STL tárolókhoz meg is írták őket:
std::vector<int> t = {1, 2};
std::list<std::string> szavak = {"villa", "malna", "alma", "korte"};
std::deque<int> sor = {1, 2, 3, 4, 5};C++11-ben a kapcsos zárójeleket még néhány új dologra felhasználták, amivel néha ütközhet az inicializáló lista szintaxisa, de ebbe nem megyünk bele.
A C++ fájlműveleteket megvalósító osztályai. Jól kombinálhatók az std::string-gel.
#include <fstream>
#include <iomanip> // manipulátorok, lásd lent
int main() {
std::ifstream is; // input file stream, vagyis olvasunk egy fájlból
is.open("fajl.txt"); // megnyitjuk a fájlt
if (!is) {
std::cerr << "Nincs ilyen fájl!";
// ... meg csinálunk is valami értelmeset ilyenkor
}
std::ofstream os("out.txt"); // a párja az std::ofstream. a konstruktoruk megnyitja
std::string s; // A string szükség szerint átméreteződik!
int i = 0;
while (std::getline(is, s)) { // Beolvasunk egy teljes sort.
// Számozva kiírjuk a sorokat. std::setw manipulátor: az utána
// következő kiírt dolgot 5 karakter szélességűre veszi.
// Mintha printf %5d lenne.
os << std::setw(5) << ++i << ". sor: " << s << std::endl;
}
is.close(); // kézzel is bezárhatjuk, de a destruktor
// os dtor // automatikusan bezárja a fájlt, ha még nyitva van
}A generikus algoritmusokról szóló fejezetben volt szó arról, hogy az STL-ben találhatók ilyenek.
A legfontosabb közös jellemzőjük, hogy iterátorokon vagy iterátorokkal megadott tartományokon dolgoznak. Számos algoritmusnak, amelyik objektumot vesz át, van predikátumot átvevő változta is.
Eddig ezekről volt szó az iterátoros fejezetben:
std::find: megtalál egy tartományban egy elemetstd::find_if: megtalál egy tartományban egy valamilyen feltételnek eleget tevő elemetstd::min_element: megtalálja a legkisebb, vagy a predikátum szerinti legkisebb elemetstd::max_element: ugyanez, csak a legnagyobb elemetstd::count: megszámolja, hányszor szerepel a tartományban az elemstd::count_if: megszámolja, hány elem van, ami a feltételnek eleget tesz
Korábban említettünk még néhány STL algoritmust, pl. a rendezés:
#include <algorithm>
#include <vector>
#include <cstdlib>
bool kozelebb_0_hoz(int a, int b)
{
return std::abs(a) < std::abs(b);
}
int main() {
std::vector<int> t = {-3, 2, 5, 1, 4};
std::sort(t.begin(), t.end()); // növekvő sorrendben
std::sort(t.begin(), t.end(), std::greater<int>()); // csökkenő sorrendben
std::sort(t.begin(), t.end(), kozelebb_0_hoz); // abszolútérték szerint
// ha rendezve sorrendben vannak, lehet benne binárisan keresni,
bool benne_van = std::binary_search(t.begin(), t.end(), kozelebb_0_hoz, 4);
// de az elemet pl. a lower_bound adja vissza:
auto it = std::lower_bound(t.begin(), t.end(), kozelebb_0_hoz, 4);
if (it != t.end())
std::cout << *it << std::endl;
}Ezeket név szerint felesleges megtanulni, viszont ha kódolás során egy hasonlóan általános algoritmus szagát érezzük, érdemes megnézni, valaki megoldotta-e már. Erre a célra a cppreference.com-ot és a cplusplus.com-ot érdemes használni. Előbbi általában egy egyszerű implementációt is mellékel a leírás mellé, algoritmusoknál ez sokat segíthet a megértésben.
Előfordul, hogy 1-1 objektumot kell dinamikusan foglalnunk, hogy ezzel valamilyen problémát megoldjunk. Például heterogén kollekciónál, vagy a vektorba tett elemek invalidálódásánál. Ez viszont mindig hozza magával azt a problémát, hogy a dinamikusan foglalt memória kezeléséért mi vagyunk a felelősök.
Természetesen nem akarjuk magunk kezelni a memóriát minden ilyen esetben. A RAII elv értelmében egy erre való osztályt kell használnunk. Az ilyen, 1 db objektum élettartamáért felelős osztályokat okos pointereknek hívjuk.
Az eredeti C++98 szabvány is magában foglalt egy okos pointert, ez volt az std::auto_ptr. Ez azonban nagyon nehézkesen használható (pl. nem szabad STL tárolóba tenni), így C++11-ben gyorsan elavulttá nyilvánították.
A helyébe az std::unique_ptr lépett. Attól unique, hogy az általa menedzselt objektumnak ő az egyetlen, kizárólagos tulajdonosa. Nem másolható, de a tartalma átadható másik unique_ptr-nek.
#include <memory> // unique_ptr
#include <utility> // move, lásd lent
class Ember {
// ...
};
std::unique_ptr<Ember> f() {
// a konstruktora egy dinamikusan foglalt Ember*-ot vár
std::unique_ptr<Ember> valaki(new Ember("Bjarne"));
// érték szerint visszaadható
return valaki;
}
int main() {
std::unique_ptr<Ember> bjarne = f(); // temporálist el lehet tárolni belőle
std::unique_ptr<Ember> masik; // most még NULL
masik = bjarne; // ERROR, nem másolható!
masik = std::move(bjarne); // mozgatni szabad
if (bjarne == NULL) { // NULL is lehet
std::cout << "bjarne most kiürült." << std::endl;
}
if (masik) { // nyíl operátor
std::cout << "masik-ba átkerült " << masik->nev() << std::endl;
}
Ember *ptr = masik.get(); // sima C-s pointer, nem szabad felszabadítanunk,
// az a unique_ptr destruktorának a dolga!
Ember& ref = *masik; // operator*
// destruktora felszabadít
}Ha heterogén kollekcióra van szükségünk, ezt érdemes a tárolóba tennünk.
#include <memory>
#include <utility>
// Alakzat, Negyzet, Teglalap, Kor
int main() {
std::vector<std::unique_ptr<Alakzat>> alakzatok;
std::unique_ptr<Alakzat> kor(new Kor(3.0));
alakzatok.push_back(kor); // ERROR: nem másolható
alakzatok.push_back(std::move(kor)); // viszont mozgatható
// csinálhatunk egy temporális unique_ptr-t, azt gond nélkül betehetjük
alakzatok.push_back(std::unique_ptr<Alakzat>(new Negyzet(1.2)));
// vagy helyben konstruálhatjuk a unique_ptr-t egy Alakzat*-ból
alakzatok.emplace_back(new Teglalap(3.0, 4.0));
}Ez egy halmaz osztály, bármilyen típusokat képes tárolni. Az elemeket rendezett struktúrában tárolja, így összehasonlíthatónak kell lenniük (operator< és operator==). Adott értékről meg tudja mondani, szerepel-e benne. Az iterátorok itt is használhatóak.
#include <set>
int main() {
std::set<int> s; // Egész számok halmaza
std::cout << "Írj be számokat, 0=vége!" << std::endl;
int i;
std::cin >> i;
while (i != 0) {
if (s.find(i) != s.end()) // Így jelzi, ha nincs benne
std::cout << "Ez már benne volt!\n";
else // Berakjuk a halmazba a kapott számot.
s.insert(i); // Természetesen, ha már benne volt,
// amúgy se történne semmi.
std::cout << "Most " << s.size() << " szám van a halmazban.\n";
std::cout << "Kérem a következőt!\n";
std::cin >> i;
}
std::cout << "A halmaz elemei: ";
for (std::set<int>::iterator it = s.begin(); it != s.end(); ++it)
std::cout << *it << ' ';
}Asszociatív tömb, kulcsokhoz értékeket rendel hozzá. Mintha egy tömb lenne, amit nem számmal kell indexelni.
A kulcs szerint rendezett, ezért gyors benne a keresés. Ehhez a kulcsokat kell tudni összehasonlítani, pont úgy, mint a halmaznál.
#include <map>
int main() {
// Sztringeket képezünk le egész számokra;
// vagyis minden sztringhez rendelünk egy egész számot.
std::map<std::string, int> m = {
{"Ernőke", 4},
{"Pistike", 7},
};
m["Orsika"] = 4; // Mintha a tömböt indexelnénk, csak épp sztringgel.
std::cout << "Ernőke, még csak " << m["Ernőke"] << " éves vagy." << std::endl;
// Vigyázni kell, hogy ha olyan névvel indexeljük a map-et, ami még
// nem szerepel benne, akkor létrejön az az elem! És kap kezdeti
// értéket is, ami intek esetén nulla.
// std::cout<<m["NincsIlyen"]<<std::endl;
// Ez a sor nullát írna ki, és létrehozna egy NincsIlyen nevű embert!!!
// Ha ellenőrizni szeretnénk, hogy van-e benne, akkor a find
// függvény használható.
std::cout << "Kinek szeretnéd tudni a korát? ";
std::string s;
std::cin >> s;
auto talalat = m.find(s);
if (talalat != m.end())
std::cout << s << ' ' << *talalat << " éves." << std::endl;
else
std::cout << "Nincs ilyen név, hogy " << s << "!" << std::endl;
// Persze itt is lehet iterátorunk, viszont nem csak az értéket, hanem
// a kulcsot is látjuk. it->first a kulcs, it->second pedig az érték,
// mert az std::map belül std::pair elemeket tárol.
// Sztringeket egészekre leképező map iterátora:
std::map<std::string, int>::iterator it;
for (it = m.begin(); it != m.end(); ++it)
std::cout << it->first << " még csak " << it->second << " éves." << std::endl;
}A map belül kulcs-érték-párokat tárol, azaz std::pair<Kulcs, Ertek>-eket. Az std::pair csak annyit tud, hogy van first és second adattagja.
Pont, mint a set és a map, csak adott kulccsal több érték is szerepelhet.
Adott kulcs szerinti tartományt az equal_range függvénnyel kereshetünk. A count függvénnyel kérhetjük le az elemek számát.
Érdekesség, hogy a sima std::map-nek és std::set-nek sincs contains függvénye, ahelyett is a count használható.
Az UML-es fejezetben volt szó az aggregációról, aminek egyik speciális esete a megosztott, közös erőforrás. Azaz több objektum is használhatja ugyanazt a (mondjuk Negyzet) objektumot. Mindaddig szükség van a négyzetre, amíg legalább egyvalakinek kell. Ha már nem kell senkinek, akkor lehet felszabadítani.
Például ha szeretnénk egy alakzatokból álló heterogén kollekciót, azt csinálhatjuk úgy is, hogy ne csak a rajztábla érje el az alakzatokat, hanem az is, aki beletette. Így mindketten tulajdonosai lesznek.
Aki használja a dinamikusan foglalt négyzetet, annak van egy shared_ptr-e a négyzetre, a négyzet maga pedig dinamikusan foglalt. Ha a shared_ptr-t lemásoljuk, akkor keletkezett egy új "használója" a négyzetnek. Tehát a négyzet mellett nyilván kell tartani, hogy hány darab shared_ptr hivatkozik ugyanarra a négyzetre, és ha már egy sem, akkor lehet felszabadítani:
Emellett a shared_ptr úgy viselkedik, mint minden rendes okos pointer: konstruktora dinamikusan foglalt objektumra mutató pointert vár, van nyíl és csillag operátora, és a destrukora akkor szabadítja fel az objektumot, amikor kell.
#include <memory>
// class Alakzat
// class Negyzet : public Alakzat
int main() {
std::shared_ptr<Negyzet> n(
// (120; 140), a=10, szin=kek
new Negyzet(Point(120,140), 10, BLUE));
// n referenciaszámlálója 1
{
std::vector<std::shared_ptr<Alakzat>> rajztabla;
rajztabla.push_back(n); // n referenciaszámlálója 2 lett
n->set_a(20); // a=20 lett a rajztáblában lévő négyzet is,
// hiszen ugyanaz az objektum!
// blokk végén megszűnik a rajztabla,
// a referenciaszámláló lecsökken 1-re
}
// a main végén n megszűnik, a referenciaszámláló lecsökken 0-ra,
// tehát maga a négyzet is felszabadul
}Figyeljük meg, hogy a példában n típusa std::shared_ptr<Negyzet>, a vektorban viszont std::shared_ptr<Alakzat>-ok vannak. Ezt azért tehetjük meg, mert a shared_ptr-ek ugyanúgy kompatibilisek, ahogy a sima pointerek, az öröklés miatt.
Egyszerű példák
Az STL lényege az, hogy egyszerű feladatokat egyszerűen tudjunk megoldani.
Ez azért lehetséges, mert - a jegyzetben is bemutatott - objektumorientált elvek alapján készültek.
- A RAII elv értelmében a memóriakezelés a tárolók feladata, és nem a mi kódunké.
- A legalapvetőbb OOP elv, az SRP szerint a tárolóknak csak a tárolt elemek kezelése a feladata, más pedig nem.
Így a memóriakezelés, és a tárolók kezelése - végére beszúrás, rendezve beszúrás, törlés, stb. - nem a mi kódunkban van. A mi kódunkban tehát kizárásos alapon pusztán a feladat megoldása, lekódolása.
A feladat egyszerű: olvassunk be szavakat a standard bemenetről, és mondjuk meg, melyik volt közülük a leghosszabb!
Prog1-ből tanultuk, hogy elég mindig a leghosszabbat megjegyezni, a többit el is dobhatjuk.
Azt is tanultuk, hogy egy szó bármilyen hosszú lehet, és ezért dinamikusan kell foglalni - de C++-ban már nem a mi dolgunk. Az std::string beolvasó operátora épp szavanként olvassa be a bemenetet:
std::string leghosszabb;
std::string szo;
while (std::cin >> szo) // addig megy, amíg sikerült szót beolvasni
if (szo.length() > leghosszabb.length())
leghosszabb = szo;
std::cout << leghosszabb << std::endl;Csavarjunk rajta egyet: írjuk ki az összes leghosszabbat! Ehhez már nem elég egyetlen szót megjegyezni, hanem akármennyi lehet belőle: tegyük őket tömbbe! A dinamikus tömb pedig a vektor.
Ha találunk hosszabbat, mint a mostaniak, akkor dobjuk ki az eddigieket, és tegyük bele az újat. Ha ugyanolyan hosszút találunk, elég csak elrakni azt is.
// tegyünk bele egy üres szót, hogy ne legyen túlindexelés
std::vector<std::string> leghosszabbak = {""};
std::string szo;
while (std::cin >> szo) { // addig megy, amíg sikerült szót beolvasni
if (szo.length() > leghosszabbak[0].length()) {
leghosszabbak.clear();
leghosszabbak.push_back(szo);
} else if (szo.length() == leghosszabbak[0].length()) {
leghosszabbak.push_back(szo);
}
}
for (std::string const& leghosszabb : leghosszabbak)
std::cout << leghosszabb << std::endl;Érdemes belegondolni, hogy C-ben mennyire bonyolult lenne ehhez egy dinamikus sztringtömböt csinálni. Ezzel szemben C++-ban ebből semmit nem látunk.
A fenti megoldás minden leghosszabb szót annyiszor ír ki, ahányszor szerepeltek a bemenetben. Ha csak egyszer szabad kiírni minden leghosszabbat, akkor nem írhatjuk ki a vektor tartalmát egészben.
Az egyik megoldás, hogy nem vektorba szúrjuk be a szavakat, hanem egy olyan tárolóba, ami biztosítja, hogy nem lehet benne ugyanaz az elem többször: ez a halmaz, az std::set. Ehhez a vector-t kell kicserélni setre, a leghosszabbak[0]-t *leghosszabbak.begin()-re, a push_back-et pedig insert-re, és működne is.
Ezzel csak az a probléma, hogy a set-be beszúrás sokkal lassabb a vektorba beszúrásnál: O(log n) az átlagosan O(1) helyett. Valószínűleg kevés hosszú és sok rövid szó lesz, azaz rengeteg elemet szúrunk be, majd dobunk el, ha találunk hosszabbat.
Ehelyett érdemes megtartani a vektort, és csak akkor szüntetjük meg a duplikációkat, mielőtt kiírjuk. Ekkor már csak viszonylag kevés elemünk van, így annyira nem fáj a halmazba beszúrás.
Szinte minden STL tárolónak van olyan konstruktora, ami egy másik tároló elemeiből képes inicializálni magát, értelemszerűen a másik tárolóra iterátorokat (begin, end) kap. A set-nek is van ilyen:
std::vector<std::string> leghosszabbak; // beolvassuk
// átmásoljuk
std::set<std::string> egyszer(leghosszabbak.begin(), leghosszabbak.end());
for (std::string const& leghosszabb : egyszer)
std::cout << leghosszabb << std::endl;Csavarjunk rajta még egyet: ne a leghosszabb szavakat, hanem a leghosszabb sorokat keressük meg!
Ehhez a beolvasás módján kell változtatni, egész sort kell beolvasni a sztringünkbe. Szerencsére létezik erre egy függvény, az std::getline, erre kell lecserélnünk a beolvasó operátort:
while (std::getline(std::cin, sor)) { // addig megy, amíg sikerült sort beolvasni
// ugyanaz, mint eddig
}Bjarne Stroustrup a C++ nyelv atyja. Számos C++-ról szóló könyvet írt, és szinte mindben benne van ez a feladat:
Számoljuk meg, egy szövegfájlban melyik szó hányszor szerepel!
Például ha ez van a fájlban:
alma barack körte barack alma barackEzt kell kiírnunk:
2x szerepelt ez: alma
3x szerepelt ez: barack
1x szerepelt ez: körteElmélkedjünk az adatszerkezetről! Nekünk nyilván kell tartani minden szóhoz az eddigi előfordulásainak számát. Ha találunk egy új szót, akkor meg kell keresni az eddigi előfordulásait, és azt növelni eggyel.
Ide egy asszociatív tömb kell: sztringeket képezünk le egész számokra. Az STL-ben van ilyen, ez az std::map.
#include <iostream>
#include <map>
#include <string>
#include <fstream>
int main() {
std::ifstream is("fajl.txt"); // konstruktor egyből meg is nyitja
if (!is) {
std::cerr << "Nem lehet megnyitni!" << std::endl;
return 1;
}
std::string s;
std::map<std::string, int> m; // sztringeket képzünk le egészekre
// Beolvasunk egy szót...
while (is >> s) {
// A map megfelelő számát növeljük eggyel. Ha még
// nem volt olyan, létrejön 0 értékkel, és az növelődik.
m[s]++;
}
std::map<std::string, int>::iterator it;
for (it = m.begin(); it != m.end(); ++it) {
std::cout << it->second << "x szerepelt ez: "
<< it->first << std::endl;
}
}Figyeljük meg, hogy a fenti megoldás szavak szerint rendezve írja ki a gyakoriságokat. Csavarjunk rajta egyet: írjuk ki a szavakat gyakoriság szerint rendezve!
Tehát ha ez van a fájlban:
alma barack körte barack alma barackEzt kell kiírnunk:
3x szerepelt ez: barack
2x szerepelt ez: alma
1x szerepelt ez: körteEhhez a jelenlegi std::map<std::string, int> alkalmatlan, mert mindig a sztring szerint fogja rendezve tartani az értékeket. Egy másik adatszerkezetet kell találni, amiben lehet gyakoriság szerint rendezve tárolni.
Az eredeti map-et viszont meg kell tartani, mert a gyakoriságok számolásához muszáj a sztring szerint rendezett tárolót használni, tehát a map tartalmát kell átalakítani valami más formátumba.
Az első ötlet, hogy másoljuk át egy vektorba, és rendezzük. Az std::vector-ba szintén std::string, int párokat kell tenni. Ha a sorrendjét megfordítjuk, és std::pair<int, std::string>-eket tartalmaz, akkor a sima rendezés elsősorban az int, és másodsorban std::string szerint fog rendezni.
std::map<std::string, int> m; // beolvassuk
std::vector<std::pair<int, std::string>> r;
for (auto it = m.begin(); it != m.end(); ++it)
// fordított sorrendben
r.push_back(std::pair<int, std::string>(it->second, it->first));
std::sort(r.begin(), r.end());
for (auto it = r.begin(); it != r.end(); ++it) {
// itt is fordított sorrendben
std::cout << it->first << "x szerepelt ez: "
<< it->second << std::endl;
}A második ötlet, hogy használjunk egy tárolót, ami alapból rendezett: az std::map-et. A probléma csak annyi, hogy most több szó is szerepelhet azonos gyakorisággal, nem csak egy. Tehát az értékek nem lehetnek sima std::string-ek, hanem akárhány std::string: legyen std::vector<std::string>!
std::map<std::string, int> m; // beolvassuk
std::map<int, std::vector<std::string>> r;
for (auto it = m.begin(); it != m.end(); ++it)
// ha nem létezik még a vektor, létrehozza üresen
r[it->second].push_back(it->first);
for (auto it = v.begin(); it != v.end(); ++it) {
auto& szavak = it->second;
for (auto szoit = szavak.begin(); szoit != szavak.end(); ++szoit)
std::cout << it->first << "x szerepelt ez: "
<< *szoit << std::endl;
}A harmadik ötlet, hogy már létezik olyan tároló, ami egy kulcshoz akárhány értéket tud tárolni: ez az std::multimap. Tegyük multimapbe az értékeket!
std::map<std::string, int> m; // beolvassuk
std::multimap<int, std::string> r;
for (auto it = m.begin(); it != m.end(); ++it)
// fordított sorrendben
r.insert(std::pair<int, std::string>(it->second, it->first));
for (auto it = r.begin(); it != r.end(); ++it) {
// itt is fordított sorrendben
std::cout << it->first << "x szerepelt ez: "
<< it->second << std::endl;
}Érdekesség: az eredeti feladat megoldásának a komplexitása O(n*log n): n darab szót szúrunk be a vektorba, egy beszúrás költsége O(log n). A gyakoriság szerint rendezett megoldások is mind ugyanilyen komplexitásúak: az std::sort is, az std::map-be és az std::multimap-be beszúrások is ezt adják. A többi művelet költsége ehhez képest elhanyagolható.