C++, STL - II.

Map-аас вектор үүсгэх:

map<string, int> M; 
 // ... 
 vector< pair<string, int> > V(all(M)); // umnuh post deer all(c)-g (c).begin(), (c).end() gesen macro zarlasan bga.

Вектор сортлогдсон байгаа. Ингэх нь мап хэрэггүй болсон мөн элементүүдийг индексжүүлэх хэрэгтэй үед ашиглах нь тохиромжтой. Нэг зүйлийг дурьдахад Мап-г индекслэх ашиглаж байгаа ч энэ нь хайх үйлдэл цаана нь ажиллаж байгаа ба Лог хугацаа зарцуулна.

Олонлогийн үйлдэлүүдийг агуулагч бүтэц төрлүүдэд хэрэглэх. Агуулагч бүтэц төрөл гэж би шугаман болон мод бүтэцтэй бүх төрлүүдийг хэлж байгаан шүү.
- 'union' нэгтгэх, R = A+B
- Огтлолын элементүүд, R = A*B
- 2 олонлогт 2ууланд нь зэрэг байдаггүй элементүүд, R = A*(~B) or R = A-B
- симметрик ялгаа, R = A XOR B

Дээрх 4-н үйлдэлд зориулагдсан функцууд бүгд байдаг. set_union(...), set_intersection(...), set_difference(...) and set_symmetric_difference(...).

Жишээ болгон огтлолыг яаж олохыг харууъя. Гэснээс бүгд яаж ашиглах нь адилхан шүү.

int data1[] = { 1, 2, 5, 6, 8, 9, 10 }; 
int data2[] = { 0, 2, 3, 4, 7, 8, 10 }; 
 
vector<int> v1(data1);
vector<int> v2(data2); 
 
vector<int> tmp(max(v1.size(), v2.size()); 
 
vector<int> res = vector<int> (tmp.begin(), set_intersection(all(v1), all(v2), tmp.begin());

accumulate:
Хэдэн параметрай дуудахаас шалтгаалаад өөр өөр үйлдэл хийдэг. Жишээ нь тухайн векторт байгаа элементүүдийн нийлбэрийг олъё.
3 дахь параметр нь анхны утга байх ёстой ба мөн уг утгын төрлөөс хамаарч ямар төрлөөр утгаа буцаахаа шийднэ.

vector<int> v; 
// ... 
int sum = accumulate(all(v), 0); 

vector<int> v; 
// ... 
long long sum = accumulate(all(v), (long long)0);  

Үржвэрийг нь олохдоо 4 дахь параметр нэмэх ба дараах байдлаар бичнэ. Анхны утгаа 1-ээр өгөхөө мартав.

vector<int> v; 
// ... 
double product = accumulate(all(v), double(1), multiplies<double>()); 

ЧУХАЛ

Энэ хүртэл зааж ашигласан жишээ бүгд энгийн төрлүүд ашигласан байсан, бүхэл тоон төрөл гэх мэт. Тэгвэл бид өөрсдөө бүтэц төрөл мөн класс байгуулвал эдгээр төрлүүдийг жишээ нь эрэмбэлэх хэрэг гарна. Үүнийг яаж зааж өгөх вэ. С++ бол зөвхөн энгийн төрлүүд байвал яаж эрэмблэх вэ гэдэгээ л мэднэ. Үүнийг зохицуулахын тулд бид тухайн класс бүтэцдээ зөвхөн "<" тэмдэгт таарвал яаж вэ гэдэгийг нь зааж өгөхөд хангалттай. Жишээ болгон хүртвэл хуваарьтэй бутархай тоон төрөл байгуулж үүнийгээ векторт хийж хэрхэн эрэмбэлэхийг харуулъя.

struct fraction { 
      int n, d; // (n/d) 
      // ... 
      bool operator < (const fraction& f) const { 
           if(false) { 
                return (double(n)/d) < (double(f.n)/f.d); 
           } 
           else { 
                return n*f.d < f.n*d; 
           } 
      } 
 }; 
  
 // ... 
  
 vector<fraction> v; 
  
 // ... 
  
 sort(all(v)); 

Одоо зарим нэгэн чухал алгоритмуудыг хэрхэн хялбар бичиж болохыг харуулъя.

DFS.

typedef vector<int> vi;
typedef vector<vi> vvi;


 int N; // Oroin too.
 vvi W; // graph 
 vi V; // tuhain oroid nevtersen eseh.
 
 void dfs(int i) { 
       if(!V[i]) { 
            V[i] = true; 
            for_each(all(W[i]), dfs); 
       } 
 } 
  
 bool check_graph_connected_dfs() { 
       int start_vertex = 0; 
       V = vi(N, false); 
       dfs(start_vertex); 
       return (find(all(V), 0) == V.end()); 
 } 

BFS, queue.

/*
чиглэлгүй граф, мөн хөршийн матриц ашигласан жишээ.
*/
 
 int N; // Оройн тоо.
 vvi W; // хөрш оройнууд
   
   
 bool check_graph_connected_bfs() { 
      int start_vertex = 0; 
      vi V(N, false); 
      queue<int> Q; 
      Q.push(start_vertex); 
      V[start_vertex] = true; 
      while(!Q.empty()) { 
           int i = Q.front(); 
           Q.pop(); 
           tr(W[i], it) { 
                if(!V[*it]) { 
                     V[*it] = true; 
                     Q.push(*it); 
                } 
           } 
      } 
      return (find(all(V), 0) == V.end()); 
 } 

Dijkstra, priority_queue.

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
      vi D(N, 987654321); 

      priority_queue<ii,vector<ii>, greater<ii> > Q; 
      D[0] = 0;
      Q.push(ii(0,0));

      while(!Q.empty()) {

            ii top = Q.top();
            Q.pop();
                        
            int v = top.second, d = top.first;
            if(d <= D[v]) {
                  tr(G[v], it) {
                        int v2 = it->first, cost = it->second;
                        if(D[v2] > D[v] + cost) {
                              D[v2] = D[v] + cost;
                              Q.push(ii(D[v2], v2));

                        }
                  }
            }
      }

Dijkstra, set.

  vi D(N, 987654321);
      set<ii> Q;
      D[0] = 0;
      Q.insert(ii(0,0));
 
      while(!Q.empty()) {
           ii top = *Q.begin();
           Q.erase(Q.begin());
           int v = top.second, d = top.first;


           tr(G[v], it) {
                int v2 = it->first, cost = it->second;
                if(D[v2] > D[v] + cost) {
                     if(D[v2] != 987654321) {
                           Q.erase(Q.find(ii(D[v2],v2)));
                     }
                     D[v2] = D[v] + cost;
                     Q.insert(ii(D[v2], v2));
                }
           }
      }