container
Főnév
container (tsz. containers)
Konténerek C++ nyelven
Bevezetés
A konténerek a Standard Template Library (STL) részei, és különböző típusú adatok tárolására és kezelésére szolgálnak. Az STL konténerek előre definiált adatstruktúrák, amelyeket hatékonyan használhatunk az adatok tárolására, módosítására és keresésére.
C++ konténerei három fő kategóriába sorolhatók: 1. Szekvenciális konténerek (pl. vector, list, deque)
2. Asszociatív konténerek (pl. set, map)
3. Konténer adapterek (pl. stack, queue, priority_queue)
Ebben a cikkben részletesen bemutatjuk mindegyik kategóriát, azok előnyeit és használati példákat.
1. Szekvenciális konténerek
A szekvenciális konténerek olyan adatszerkezetek, amelyekben az elemek egy meghatározott sorrendben helyezkednek el.
1.1. std::vector (Dinamikus tömb)
A std::vector egy dinamikusan növekvő méretű tömb, amely gyorsan hozzáférhető indexekkel.
Jellemzők: ✅ Gyors olvasás index alapján (O(1))
✅ Automatikus méretezés
❌ Beszúrás és törlés lassabb a közepén (O(n))
Használati példa:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {10, 20, 30};
v.push_back(40); // Új elem hozzáadása
v.pop_back(); // Utolsó elem eltávolítása
for (int i : v) {
cout << i << " ";
}
return 0;
}
1.2. std::list (Kétirányú láncolt lista)
A std::list egy kétirányú láncolt lista, amely gyors beszúrást és törlést biztosít.
Jellemzők: ✅ Gyors beszúrás és törlés (O(1))
❌ Lassú hozzáférés index alapján (O(n))
Használati példa:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> l = {10, 20, 30};
l.push_back(40);
l.push_front(5);
for (int i : l) {
cout << i << " ";
}
return 0;
}
1.3. std::deque (Dupla végű sor)
A std::deque egy olyan dinamikus tömb, amely két végén is gyors beszúrást és törlést biztosít.
Jellemzők: ✅ Gyors beszúrás és törlés mindkét végén (O(1))
✅ Indexelhető (O(1))
❌ Középen történő beszúrás lassabb, mint a listában (O(n))
Használati példa:
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d = {10, 20, 30};
d.push_front(5);
d.push_back(40);
for (int i : d) {
cout << i << " ";
}
return 0;
}
2. Asszociatív konténerek
Az asszociatív konténerek rendezetten tárolják az adatokat és hatékony keresési lehetőséget biztosítanak.
2.1. std::set (Rendezett halmaz)
A std::set egy olyan adatszerkezet, amely egyedi elemeket tartalmaz, és automatikusan rendezi őket.
Jellemzők: ✅ Automatikus rendezés
✅ Gyors keresés (O(log n))
❌ Nem lehet duplikátumokat tárolni
Használati példa:
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s = {30, 10, 20, 10}; // Duplikált értékeket nem tárol
s.insert(25);
for (int i : s) {
cout << i << " "; // Kiíratás rendezett sorrendben
}
return 0;
}
2.2. std::map (Rendezett kulcs-érték párok)
A std::map egy kulcs-érték párokat tároló adatszerkezet, ahol a kulcsok egyediek és rendezettek.
Jellemzők: ✅ Gyors keresés és beszúrás (O(log n))
✅ Automatikus kulcsrendezés
❌ Lassabb, mint az unordered_map
Használati példa:
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> m;
m[1] = "Egy";
m[2] = "Kettő";
for (auto i : m) {
cout << i.first << ": " << i.second << endl;
}
return 0;
}
3. Konténer adapterek
A konténer adapterek olyan speciális adatszerkezetek, amelyek a szekvenciális konténerekre épülnek.
3.1. std::stack (Verem)
A verem egy LIFO (Last In, First Out) adatszerkezet.
Jellemzők: ✅ Gyors beszúrás és eltávolítás (O(1))
❌ Csak a legfelső elem érhető el
Használati példa:
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
s.push(10);
s.push(20);
s.push(30);
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
return 0;
}
3.2. std::queue (Sor)
A sor egy FIFO (First In, First Out) adatszerkezet.
Jellemzők: ✅ Gyors beszúrás és eltávolítás (O(1))
❌ Csak az első és az utolsó elem érhető el
Használati példa:
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
return 0;
}
Összegzés
| Konténer | Adattípus | Hozzáférés | Beillesztés/Törlés | Keresés |
|---|---|---|---|---|
vector |
Dinamikus tömb | O(1) |
O(n) középen |
O(n) |
list |
Kétirányú láncolt lista | O(n) |
O(1) |
O(n) |
set |
Rendezett halmaz | O(log n) |
O(log n) |
O(log n) |
map |
Kulcs-érték párok | O(log n) |
O(log n) |
O(log n) |
stack |
LIFO verem | O(1) |
O(1) |
Nem támogatott |
queue |
FIFO sor | O(1) |
O(1) |
Nem támogatott |
✅ Melyiket válaszd?
- vector ha gyors indexelés kell.
- list ha gyakran módosítod az elemeket.
- set/map ha gyors keresés és egyediség fontos.
- stack/queue ha speciális LIFO/FIFO viselkedés kell.
A megfelelő konténer kiválasztása segíthet optimalizálni a programodat! 🚀