container data type (tsz. container data types)
Ezeknél a konténereknél a beszúrási sorrend vagy index értelmezése fontos. Jellemző műveletek: push_back, push_front, insert(position), erase(position), operator, at(), front(), back().
std::vector<T> (amortizált O(1) push_back, O(1) random access)ArrayList<E>std::deque<T> (O(1) push/pop front és back, O(1) random access)LinkedList<E> implementálja Dequestd::list<T> (kétszeres láncolt lista, O(1) szúrás/eltávolítás ismert iterátorból, O(n) random access)std::forward_list<T> (egyszeres láncolt lista)
Itt az elem kulcsa (key) és hozzá tartozó adat (value) a lényeg; a sorrend általában rendeltetett (sorted) vagy hash‐alapú. Műveletek: insert(key,value), find(key), erase(key).
std::set<T>, std::map<Key,T> (RED‐BLACK fa, O(log n) műveletek)TreeSet<E>, TreeMap<K,V>std::unordered_set<T>, std::unordered_map<K,V> (amortizált O(1))HashSet<E>, HashMap<K,V>
Ezek speciális interface‐t kínálnak a fenti konténerek fölött, korlátozottabb eléréssel, de speciális viselkedéssel:
std::stack<T> (alapértelmezett alatt deque), Java: Stack<E>, vagy Deque-ből push/pop.std::queue<T>, Java: Queue<E>.std::priority_queue<T>, Java: PriorityQueue<E>.
A legtöbb konténer C++ STL‐ben és Java Collections‐ben támogat iterátorokat (vagy Java‐ban Iterator/Iterable), melyekkel bármely konténer egységes módon bejárható:
for(auto it = container.begin(); it != container.end(); ++it) {
process(*it);
}
STL‐beli algoritmusok (std::sort, std::find, std::accumulate, stb.) könnyen alkalmazhatók bármely konténerre, csak iterátorokat kérnek.
| Konténer | insert(push_back) | push_front | random access | insert middle | erase middle | find by key |
|---|---|---|---|---|---|---|
vector
|
amort. O(1) | O(n) | O(1) | O(n) | O(n) | O(n) |
deque
|
O(1) | O(1) | O(1) | O(min(i,n−i)) | O(min(i,n−i)) | O(n) |
list
|
— | O(1) | — | O(1) | O(1) | O(n) |
forward_list
|
— | O(1) | — | O(n)¹ | O(n)¹ | O(n) |
set, map
|
O(log n) | — | — | — | — | O(log n) |
unordered_set, map
|
amort. O(1) | — | — | — | — | amort. O(1) |
priority_queue
|
O(log n) | — | — | — | — | O(n) |
stack, queue (adapter)
|
O(1) | — | — | — | — | — |
¹: előtte kell a megfelelő pozícióra menni O(k).
vector, deque.list.map/set.unordered_map/unordered_set.priority_queue.stack, queue adapterek.
C++ STL – keresés és rendezés
#include <vector>
#include <algorithm>
std::vector<int> v = {3,1,4,1,5};
std::sort(v.begin(), v.end()); // rendezett v: {1,1,3,4,5}
auto it = std::find(v.begin(), v.end(), 3);
if(it != v.end()) std::cout << "Találtam 3-at a pozícióban " << (it - v.begin());
Java – halmaz és térkép
Set<String> s = new HashSet<>();
s.add("apple");
if(s.contains("banana")) { ... }
Map<String,Integer> m = new TreeMap<>();
m.put("alice", 30);
int age = m.get("alice"); // 30
A konténer ADT a modern szoftverfejlesztés egyik sarokköve. Azáltal, hogy egy egységes, magas szintű interfészt biztosítva elfedi a belső tárolási stratégiák részleteit, lehetővé teszi, hogy algoritmusainkat konténersémák fölé építsük fel, és csak a megfelelő implementációt válasszuk az adott használati mód (beszúrási/törlési mintázat, véletlen elérés, memóriakorlát stb.) alapján. A standard könyvtárak (STL, Java Collections, .NET Collections) épp arra szolgálnak, hogy ezt a sokszínű hátteret professzionális, optimalizált, jól tesztelt elemekkel kezeljük, ezzel jelentősen felgyorsítva a fejlesztést és javítva a kód minőségét.