Vector, Set, Map (6/20)

Author

Batsambuu Batbold

1 Удиртгал

Энэ хичээлээр C++ хэл дээрх гурван чухал өгөгдлийн бүтэц (data structure) болох vector, set, map-ийг судална.

Эдгээр нь C++-ийн Standard Template Library (STL)-ийн үндсэн хэсэг бөгөөд олимпиад, competitive programming-д заавал сурах хэрэгтэй бүтэц юм.

2 `vector` — Динамик массив

2.1 Vector гэж юу вэ?

vector бол C++-ийн динамик массив юм. Хэмжээ нь программ ажиллах явцад өөрчлөгдөж болдог.

#include <vector>
using namespace std;

vector<int> v;

2.2 Үндсэн үйлдлүүд

v.push_back(10);    // Сүүлд 10 нэмэх
v.pop_back();       // Сүүлийн элементийг устгах
v.size();           // Хэмжээ авах
v.empty();          // Хоосон эсэхийг шалгах (true/false)
v.clear();          // Бүх элементийг арилгах
v[i];               // i-р элементийг авах (0-based)

2.3 Зарлах аргууд

vector<int> v = {1, 2, 3};         // Шууд утгаар
vector<int> a(5);                  // 5 ширхэг 0
vector<int> b(4, 7);               // 4 ширхэг 7

2.4 Давталт ашиглах

for (int i = 0; i < v.size(); i++)
    cout << v[i] << " ";

for (int x : v) // range-based for
    cout << x << " ";

2.5 Векторын сорт хийх

sort(v.begin(), v.end());           // өсөхөөр
sort(v.rbegin(), v.rend());         // буурахаар

2.6 2D vector (матриц)

vector<vector<int>> grid(3, vector<int>(4, 0)); // 3x4 matrix

3 `set` — Давтагдахгүй элемент хадгалах

3.1 Set гэж юу вэ?

set бол unique (давтагдахгүй) утгуудыг хадгалах бүтэц. Мөн автоматаар эрэмбэлэгддэг.

#include <set>
using namespace std;

set<int> s;

3.2 Үндсэн үйлдлүүд

s.insert(5);       // 5-г нэмэх
s.insert(2);
s.erase(2);        // 2-г устгах
s.count(5);        // 5 байвал 1, байхгүй бол 0
s.size();          // хэмжээг авах
s.empty();         // хоосон эсэх

s.clear();         // бүгдийг устгах

3.3 Давталт ашиглах

for (int x : s)
    cout << x << " ";

3.4 Set-ийн шинж чанарууд

Давхардсан утга хадгалахгүй
Автоматаар эрэмбэлнэ
Оролт, гаралт O(log n) хугацаанд ажиллана

3.5 `multiset`

Хэрэв та давхардсан утгууд хадгалахыг хүсвэл multiset ашиглана.

multiset<int> ms;
ms.insert(5);
ms.insert(5); // OK

4 `map` — Түлхүүр ба утга (key-value pair)

4.1 Map гэж юу вэ?

map бол түлхүүр-утга хос хадгалах бүтэц. Жишээлбэл, нэр болон оноо.

#include <map>
using namespace std;

map<string, int> scores;

4.2 Үндсэн үйлдлүүд

scores["Bold"] = 90;
scores["Amar"] = 85;

cout << scores["Bold"];  // 90
scores.erase("Amar");    // "Amar" устгах
scores.count("Tuya");    // байгаа эсэх (0 эсвэл 1)

4.3 Давталт ашиглах

for (auto it : scores) {
    cout << it.first << ": " << it.second << endl;
}

4.4 Автоматаар эрэмбэлэгддэг

Map дахь key-үүд өсөх дарааллаар эрэмбэлэгдэнэ.

4.5 `unordered_map`

Хэрэв эрэмбэлэх шаардлагагүй бол unordered_map ашигласнаар илүү хурдан ажиллана:

#include <unordered_map>
unordered_map<string, int> freq;

⚠️ unordered_map нь key-үүдийг hash ашиглан хадгалдаг тул O(1) дундаж хугацаатай.

5 Харьцуулсан хүснэгт

Бүтэц	Давхар утга	Эрэмбэлэлт	Оруулах хурд	Олох хурд
vector	✅	❌	O(1)	O(n)
set	❌	✅	O(log n)	O(log n)
multiset	✅	✅	O(log n)	O(log n)
map	key-үүд давхардахгүй	✅	O(log n)	O(log n)
unordered_map	key-үүд давхардахгүй	❌	O(1) (avg)	O(1) (avg)

6 Жишээ код

6.1 Давтагдсан тоог арилгах

vector<int> a = {1, 2, 2, 3, 4, 1};
set<int> s(a.begin(), a.end());
for (int x : s) cout << x << " ";

6.2 Хэдэн удаа орсныг тоолох

vector<int> a = {1, 2, 2, 3, 1, 1};
map<int, int> freq;
for (int x : a) freq[x]++;
for (auto p : freq)
    cout << p.first << ": " << p.second << endl;

6.3 Vector сорт ба давталт

vector<int> a = {5, 3, 8, 2};
sort(a.begin(), a.end());
for (int i = 0; i < a.size(); i++)
    cout << a[i] << " ";

7 Дүгнэлт

vector бол динамик, уян хатан массив бөгөөд сорт хийх, push хийх зэрэг үйлдэлд тохиромжтой.
set нь давхардсан утгагүй, автоматаар эрэмбэлдэг бүтэц.
map бол түлхүүр-утга хос хадгалах, нэрс ба оноо гэх мэт өгөгдлийг хадгалахад маш тохиромжтой.
Эдгээр STL бүтцүүд нь C++ программчлалын чухал суурь тул заавал сайн эзэмшээрэй.

8 Practice Problems

8.1 Vector – Динамик массив

8.1.1 Тоонуудыг буурахаар эрэмбэлэх

Хэрэглэгчээс \(n\) ширхэг бүхэл тоо авч, vector<int>-т хадгал. Дараа нь эдгээр тоог буурах дарааллаар эрэмбэлээд хэвлэ.

8.1.2 Дундаж тооцох

Хэрэглэгчээс vector доторх бүх тоог авч хадгал. Бүх тооны дундажийг бодож, нэг орны нарийвчлалтайгаар хэвлэ.

8.1.3 Сүүлээс нь хэвлэх

Хэрэглэгчээс авсан vector-ийг урвуугаар (сүүлээс эхлэн) хэвлэ. reverse() функц ашиглаж болохгүй.

8.2 Давтагдахгүй, эрэмбэлэгдсэн өгөгдөл

8.2.1 Давхардсан үгсийг арилгах

\(N\) ширхэг string (үг) авч set<string>-д хадгал. Давхардлыг арилгаж, үсгийн дарааллаар хэвлэ.

8.2.2 Тоо агуулагдаж байгаа эсэхийг шалгах

set<int>-д тоонууд нэмээд, хэрэглэгчийн оруулсан \(x\) тоо байгаа эсэхийг шалгаж “YES” эсвэл “NO” гэж хэвлэ.

8.2.3 Огтлол олох

Хоёр set<int> өгөгдсөн бол, хоёуланд нь байдаг тоонуудыг олонлогийн огтлол хэлбэрээр хэвлэ.

8.3 Map – Түлхүүр-утга хос

8.3.1 Давтамж тоолох

Хэрэглэгчээс \(n\) ширхэг бүхэл тоо авч map<int, int>-д хадгал. Тоо бүр хэдэн удаа гарсан болохыг дарааллаар хэвлэ.

8.3.2 Нэрээр оноо хадгалах ба хэвлэх

map<string, int> ашиглан \(n\) ширхэг оюутны нэр болон оноог хадгал. Нэрийн үсгийн дарааллаар нэр болон оноог хэвлэ.

8.3.3 Хамгийн өндөр оноотой хүнийг олох

map<string, int>-д хадгалагдсан мэдээллээс хамгийн өндөр оноо авсан хүний нэр болон оноог хэвлэ.