STL контейнерлери: терең изилдөө
Туура маалымат түзүмүн танда — программаң оңой эле тезирээк жана түшүнүктүү болот
Негизги идея: Стандарттык шаблон китепканасы даяр контейнерлерди берет —
vector, list, map, set жана алардын хеш-тууганы unordered_map / unordered_set. Алардын баары маалымат сактайт, бирок ар бири тез жетүү, тез издөө, тартип жана эстутумдун ортосунда өзүнчө компромисске барат. Туура тандай билүү — башталгычты орто деңгээлдеги C++ программисттен айырмалаган эң негизги көндүмдөрдүн бири.
Сабактын аягында сиз:
vector,list,map,set,unordered_mapжанаunordered_setмаалыматты кантип сактаарын сүрөттөй аласыз,- Big-O таблицасын окуп, жетүү үлгүңүзгө ылайык контейнер тандай аласыз,
- тартип качан маанилүү, а качан хеш-таблица жакшыраак экенин түшүндүрө аласыз,
- өндүрүмдүүлүктүн классикалык тузактарынан (орто жерге киргизүү, ашыкча көчүрмө,
reserveжоктугу) качууну билесиз.
1. Үч үй-бүлө
Ар бир стандарттык контейнер үч үй-бүлөнүн бирине кирет. Үй-бүлөнү билсеңиз, бир дагы методдун атын окубай туруп эле керектүү нерсенин көбүн түшүнөсүз.
- Ырааттуу контейнерлер (
vector,list,deque) элементтерди сиз кошкон тартипте сактайт. Орду маанилүү. - Иреттелген ассоциативдик контейнерлер (
map,set) элементтерди ачкыч боюнча иреттеп сактайт жана тең салмактуу экилик издөө дарагына негизделген. Иреттелген издөө маанилүү. - Иреттелбеген ассоциативдик контейнерлер (
unordered_map,unordered_set) элементтерди хеш-таблицада сактайт. Тартип таптакыр жок, бирок орточо издөө — O(1). Таза ылдамдык маанилүү.
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
std::vector<int> v; // dynamic array, contiguous memory
std::list<int> l; // doubly linked list
std::map<std::string, int> m; // sorted key -> value (tree)
std::set<int> s; // sorted, unique keys (tree)
std::unordered_map<int, int> um; // hashed key -> value
std::unordered_set<int> us; // hashed, unique keys