Vectors and Maps

Vector या Map: Meaning से चुनें

vector<T> contiguous ordered sequence है; map<Key,T> unique ordered keys के साथ associations रखता है। “तीसरा score” positional/vector question है; “Sara का score” keyed/map question है।

Vector Deep Dive

std::vector<int> scores;
scores.reserve(100); // capacity, size अभी 0
scores.push_back(78);
scores.emplace_back(91);
int checked=scores.at(1);

Index O(1), end insertion amortized O(1)। Growth पर कभी larger block allocate और elements move/copy होते हैं। reserve capacity बदलता है पर elements नहीं बनाता; resize size बदलता और elements बनाता/हटाता है। इसलिए reserve के बाद values[0] तब तक invalid है जब तक size zero है। vector tutorial पढ़ें।

Map Deep Dive

std::map<std::string,int> marks{{"Sara",91},{"Aman",78}};
marks.insert_or_assign("Aman",83);
if(auto it=marks.find("Sara");it!=marks.end())
 std::cout<<it->second;
if(marks.contains("Kabir")){ /* C++20 */ }

Map comparator order maintain करता और search/insert/erase O(log n) देता है। Standard किसी specific tree implementation को mandate नहीं करता।

• m[key] missing key पर default mapped value insert करता है।
• at insert नहीं करता; missing पर exception।
• find iterator देता है; contains C++20 boolean देता है।
• try_emplace existing key में unnecessary mapped construction बचा सकता है।

set/map lesson भी देखें।

Combined Practical Lab और Output

std::vector<int> scores{78,91,84,91};
std::sort(scores.begin(),scores.end());
std::map<std::string,int> by_name{
 {"Sara",91},{"Aman",78},{"Kabir",84}};
by_name.at("Aman")+=5;
for(const auto& [name,score]:by_name)
 std::cout<<name<<':'<<score<<' ';

Vector duplicates रखता और values के अनुसार sort हुआ। Map insertion order नहीं, key order में Aman, Kabir, Sara देता है। const auto& copy बचाता है।

Complexity Comparison

Read-heavy data में sorted vector compact और fast हो सकता है, पर updates O(n)। Order न चाहिए तो unordered_map average O(1), worst O(n), rehash और unordered iteration देता है। Representative benchmark करें।

Iteration और Invalidation

• Vector capacity change हो तो सभी element iterators/pointers/references invalid।
• No reallocation में insert position और बाद के handles invalid; erase erased और बाद के handles invalid।
• Map insert existing handles valid रखता है; erase केवल erased element के handles invalid करता है।

for(auto it=by_name.begin();it!=by_name.end();){
 if(it->second<40) it=by_name.erase(it);
 else ++it;
}

Read-only range loop में const auto&, mapped value modify करने में auto&। Iterator द्वारा map key const है; key बदलनी हो तो erase/reinsert करें।

Real Design Patterns

Frequency table

std::map<std::string,int> frequency;
for(const std::string& word:words) ++frequency[word];

यहां [] intentional है: missing count zero से शुरू होना चाहिए।

Insertion order + lookup

Map अकेला insertion order preserve नहीं करता। Records vector और key-to-index map रख सकते हैं, लेकिन erase/reallocation से index consistency design करनी होगी।

Read-mostly data

Sorted vector<pair<Key,Value>> + lower_bound compact हो सकता है; duplicates, comparator और update cost carefully define करें। Profiling से जरूरत सिद्ध होने तक simple standard design रखें।

Mistakes और Checklist

1. Positional या keyed identity?
2. Required iteration order?
3. Duplicates?
4. Dominant operations?
5. Handle stability?
6. Lookup modification allowed?
7. Missing/empty tests?
8. Warnings/sanitizers?

Authoritative संदर्भ

• C++ Draft: vector
• C++ Draft: map
• C++ Draft: Container Requirements

Complexity, access और invalidation claims current working draft से verified हैं; vendor implementation के बजाय guarantees पर code design करें।