Set-н тухай.
Set гэдэг нь элемэнтүүдийн эрэмбэлж хадгалдаг бүтэц юм. Элемэнт нэмэх, устгах гэх мэт үйлдлүүдийн LogN хугацаанд хийдэг мөн давхардлыг арилгадаг. Цаанаа өөр бүтэц ашигладаг тул бид 3-р элемэнтийг мэдэж чадахгүй юм. Харин iterator ашиглаж элемэнтүүдийг мэднэ. Доорхи код энэ хаягдээр байгаа. Доорхи бүх үйлдлийг Log(N) хугацаанд хийнэ(2суурьтай). Мөн хэрвээ давхардлыг арилгахгүй байлгамаар байгаа бол multiset ашиглах хэрэгтэй. Энэ нь адил утгатай элемэнт нэгээс олон удаа орж болно. Харин erase(утга) гэхэд өгөгдсөн утгатай тэнцүү утгатай бүх элемэнтүүд устах тул нэгийг л утгамаар байгаа бол it = s.find(утга); s.erase(it) гэдгийг ашиглаарай.
Set гэдэг нь элемэнтүүдийн эрэмбэлж хадгалдаг бүтэц юм. Элемэнт нэмэх, устгах гэх мэт үйлдлүүдийн LogN хугацаанд хийдэг мөн давхардлыг арилгадаг. Цаанаа өөр бүтэц ашигладаг тул бид 3-р элемэнтийг мэдэж чадахгүй юм. Харин iterator ашиглаж элемэнтүүдийг мэднэ. Доорхи код энэ хаягдээр байгаа. Доорхи бүх үйлдлийг Log(N) хугацаанд хийнэ(2суурьтай). Мөн хэрвээ давхардлыг арилгахгүй байлгамаар байгаа бол multiset ашиглах хэрэгтэй. Энэ нь адил утгатай элемэнт нэгээс олон удаа орж болно. Харин erase(утга) гэхэд өгөгдсөн утгатай тэнцүү утгатай бүх элемэнтүүд устах тул нэгийг л утгамаар байгаа бол it = s.find(утга); s.erase(it) гэдгийг ашиглаарай.
- insert(утга)-элемэнт нэмэх.
- erase(утга)-элемэнт устгах.
- lower_bound(утга)-өгөгдсөн утгаас их буюу тэнцүү хамгийн бага утгатай элемэнтийг буцаана
- upper_bound(утга)-өгөгдсөн утгаас эрс их хамгийн бага утгатай элемэнтийг буцаана хэрэв бүгд бага бол end буюу хэмжээг буцаана
- // set-ын талаар үзэх болно.
- #include <set> // set-ын функцууд агуулдаг сан
- #include <iostream>
- using namespace std;
- int main() {
- /*
- set гэдэг нь элемэнтүүдийн эрэмбэлж халгалдаг бүтэц юм.
- мөн давхардлыг арилгадаг. элемэнт нэмэх мөн устгахад
- LogN үйлдэл шаарддаг ба N нь set байгаа элемэнтийн тоо юм.
- энэ нь цаанаа өөр зүйл ашигладаг тул бид 3р
- элемэнтийн утганд шууд хандаж чадахгүй. Харин map-ын
- адил iterator ашигладаг.
- */
- set<int> s; // int төрлийн утга авлаг set анх хоосон байгаа
- set<int>::iterator it; // int төрлийн утга авдаг set-ын заагч
- s.insert( 222 ); // set-д элемэнт нэмэх
- s.insert( 111 ); // set-д элемэнт нэмэх
- for( it = s.begin(); it != s.end(); it++) {
- // set-д байгаа бүх элемэнтийг хэвлэж байна
- cout << *it << " ";
- // it-нь заагч тул бид элемэнтийг утгыг хэвлэхийн тул *
- // тавьж мэднэ
- }
- cout << "\n----------------------------------\n";
- int n = s.size(); // одоо байгаа элемэнтийн хэмжээ
- cout << n << endl;
- cout << "----------------------------------\n";
- s.insert( 111 ); // энэ элемэнт байгаа тул хэмжээ өөрчлөгдөхгүй
- n = s.size();
- cout << n << endl;
- cout << "----------------------------------\n";
- s.insert( 22 );
- s.insert( 12 );
- for( it = s.begin(); it != s.end(); it++) {
- // set-д байгаа бүх элемэнтийг хэвлэж байна
- cout << *it << " ";
- // it-нь заагч тул бид элемэнтийг утгыг хэвлэхийн тул *
- // тавьж мэднэ
- }
- cout << "\n----------------------------------\n";
- s.erase( 22 ); // 22 гэсэн элемэнтийг устгаж байна
- // хэрвээ байхгүй бол юуг ч устгахгүй
- for( it = s.begin(); it != s.end(); it++) {
- // set-д байгаа бүх элемэнтийг хэвлэж байна
- cout << *it << " ";
- // it-нь заагч тул бид элемэнтийг утгыг хэвлэхийн тул *
- // тавьж мэднэ
- }
- cout << "\n----------------------------------\n";
- it = s.lower_bound( 12 );// 12-оос их буюу тэнцүү хамгийн бага
- // элемэнтийн байрлалыг буцаана. Хэрвээ
- // бүх элемэнт 12 бага бол size буюу
- // төгсгөлийн буцаана.
- cout << *it << "\n----------------------------------\n";
- it = s.upper_bound( 12 ); // 12-оос эрс их хамгийн бага
- // элемэнтийн байрлалын буцаана. Хэрвээ
- // бүх элемэнт 12 бага бол size буюу
- // төгсгөлийн буцаана.
- cout << *it << "\n----------------------------------\n";
- s.erase( it ); // it-ын зааж байгаа элемэнтийг устгана.
- for( it = s.begin(); it != s.end(); it++) {
- // set-д байгаа бүх элемэнтийг хэвлэж байна
- cout << *it << " ";
- // it-нь заагч тул бид элемэнтийг утгыг хэвлэхийн тул *
- // тавьж мэднэ
- }
- cout << "\n----------------------------------\n";
- return 0;
- }
Comments
Post a Comment