Dynamic array-г өөрсдөө бичих - C++

Би queue-г хэрхэн бичих талаар энд бичсэн ба vector-н тухай мөн бичсэн. Энэ удаа өмнөх queue-г хэрхэн бичсэнтэй адилаар dynamic array-г хэрхэн хийж болох талаар бичихээр шийдлээ. Dynamic array-р нь энгийн array-с ялгаатай нь хэмжээгээ өөрчлөх боломжтойгоор онцлог ба үүний нэг нь vector билээ. Мэдээж vector-н ямарч элементийг мэдэхэд O(1) үйлдэл хийдэг ба vector-т үндсэн 3 үйлдэл байдаг гэвэл

• size() - хэмжээг мэдэх
• push(element) - шинэ элемент хамгийн хойно нэмэх
• [index] - index-р элементийн утгыг мэдэх

Үүнийг яаж хийх хэр хэцүү байх талаар цааш уншихаас өмнө хэсэг бодоод үзээрэй.

Array болон санах ойд юу болоод байна вэ?

Array-д хэрхэн нэг үйлдлээр ямар ч элементийг утгыг мэдээд байгаа вэ гэдэг нь төсөөлөхөд энгийн. Учир нь санах ойд дараалсан сул зайг тухайн array-н хэмжээгээр авч байгаа ба үүнийг нэг том хайрцаг гэж төсөөлж болно. Тиймээс бид хайрцгийн эхлэлийг мэдэж байхад түүнээс улбаалаад хэддүгээр элементийг мэдэх вэ гэдгийг хялбар хийж болно. Жишээ нь int array авсан байлаа гэхэд нэг элемент нь 4B санах ой эзлэх ба 5 ширхэг тоо хадгалахад бид 20B санах ойд авна. Одоо харин 3-р элемент рүү хандлаа гэхэд бид эхний хаягаас 2*4=8B шилжихэд мэдэж чадна. Үүнийг доорх зурагт харуулахыг хичээлээ

Асуудал

Ямартай ч бид санах ой болон array-г гадарлалаа. Одоо харин яаж хэмжээгээ өөрчилдөг бүтэц үүсгэх вэ? Queue дээр ашигласан санаа шиг гинж хэлбэртэй бүтэц үүсгэж болох ба гинжний нэг гишүүн нь array байж болно гэсэн үг. Тэгэхээр хэрвээ бидэнд байгаа гинжинд хадгалж чадахгүй бол шинэ array үүсгээд түүнлүүгээ нэмээд байж болноо. Ингэснээр бид хэмжээгээ нэмж чадааг бүтэцтэй боллоо. Жишээ нь бидэнд тэгвэл хэсэг бүлэг array байгаа гэсэн үг ба сүүлийн array-д байгаа элемент рүү хандах хэрэгтэй болсон гэвэл гинжээр дамжин явж тэрхүү arry-н эхний байршлыг олон түүнээсээ тухайн элемент рүү хандах хэрэгтэй болох ба энэ нь O(1) гэсэн үг биш болж таарлаа. Жишээ нь бид нэг хэсэгтээ 50 элемент хадгалдаг гэе. Тэгвэл 200 элемент хадгалахад 4 ширхэг бүлэг хэрэгтэй ба сүүлийн бүлгийн элемент рүү хандахад 4 үйлдэл хэрэгтэй болж таарлаа. Бид 1 үйлдлээр хандах нь чухал, гэхдээ яаж?

Хэрэгжүүлэлт

Тэгэхээр олон бүлэг байвал ашиггүй болохнээ. Эсвэл бид бүлгүүдийн заагчийг хадгалдаг тусдаа array авч болох ба ингэснээр тухайн бүлгийг шууд олж чадна. Гэхдээ энд хэдэн бүлэг байхыг бид мэдэхгүй ба өнөөх л асуудал руугаа орчихлоо. Тэгвэл 1-л array ашиглаад хийж болох уу? Тэгвэл яаж хэмжээгээ нэмэх вэ гэсэн эхний асуудал руу оччихлоо. Бид гэхдээ чаднаа. Яаж вэ гэвэл одоо байгаа array хүрэхгүй тохиолдолд шинэ илүү том хэмжээтэй array үүсгээд өмнөхийг хуулахад болно. Гэхдээ хуулах үйлдэл мэдээж үнэтэй тул энэ нь ашигтай юу? Мэдээж ашигтай байхаар хийж болно. Өөрөөр хэлбэл аль болох багаар шинэ array үүсгэдэг байхад болох ба үүнд бид өмнөх array-н хэмжээнээс 2 дахин томоор үүсгэдэг байхаар хийж болох ба энэ нь илүү бага зардалтай хувилбар болно. Үүнийг хэрхэн бичих вэ гэвэл

Эхлээд бүтцээ тодорхойлбол бидэнд size буюу хэмжээ, capacity буюу санах ойд авсан байгаа array-н хэмжээ болон arr буюу санах ойд авсан байгаа array-н заагч байхад болно.

class Vector {
private:
    int size; // ашигласан хэмжээ
    int capacity; // санах ойд авсан хэмжээ
    int *arr; // санах ойд байгаа хаяг
};

Шинэ элемент нэмэхэд юу болох вэ? хэрвээ санах ойд авсан хэмжээ хүрж байвал ямар ч асуудал байхгүй. Харин үгүй бол бид шинээр илүү томыг үүсгээд өмнөхөө хуулаад дараа нь устгахад болно

void resize(int new_size) {
    int *new_p = new int[new_size]; // шинээр үүсгэх
    for(int i = 0; i < size; i++) { // хуулах
        new_p[i] = arr[i];
    }
    capacity = new_size; // шинэчлэх
    delete[] arr; // өмнөхөө устгах
    arr = new_p; // заагчийг шинэчлэх
}

void push_back(int v) {
    if(capacity < size + 1) { // хэрвээ хэмжээ хүрэхгүй бол
        resize(capacity == 0 ? 1 : capacity * 2); // шинээр 2 дахин их болгоно
    }
    arr[size] = v; // шинэ элемэнтийг нэмнэ
    size++; // хэмжээгээ шинэчлэнэ
}

Бүтэн хэрэгжүүлэлт

Бүтэн хэрэгжүүлэлтийн кодыг доор харуулав

#include <iostream>
using namespace std;

class Vector {
private:
    int s, c;
    int *p;
public:
    Vector() {
        s = c = 0;
        p = nullptr;
    }
    int size() {
        return s;
    }
    int capacity() {
        return c;
    }
    bool is_empty() {
        return s == 0;
    }
    void resize(int new_size) {
        int *new_p = new int[new_size]; 
        for(int i = 0; i < s; i++) {
            new_p[i] = p[i];
        }
        c = new_size;
        delete p;
        p = new_p;
    }
    int operator[](int index) {
        return p[index];
    }
    void push_back(int v) {
        if(c < s+1) {
            resize(c == 0 ? 1 : c*2);
        }
        p[s] = v;
        s++;
    }
};

int main() {
    Vector v;
    v.push_back(1);
    cout << v.capacity() << " " << v.size() << "\n";
    v.push_back(2);
    cout << v.capacity() << " " << v.size() << "\n";

    v.push_back(3);
    cout << v.capacity() << " " << v.size() << "\n";

    v.push_back(4);
    cout << v.capacity() << " " << v.size() << "\n";

    v.push_back(5);
    cout << v.capacity() << " " << v.size() << "\n";
    
    v.push_back(5);
    cout << v.capacity() << " " << v.size() << "\n";

    cout << v[5] << endl;
    return 0;
}

Дүгнэлт

Dynamic array-н тухай ерөнхий ойлголтын талаар бичлээ. Үүнийг харахын бол элемент нэмэх нь O(1)-р байнга хийгдэхгүй байгааг харж болно. Тиймээс хэмжээгээ эсвэл хэдэн элемент нэмэхээ мэдэж байгаа бол resize буюу шинээр үүсгэсний дараа элементийн утгыг шинэчилсэн нь ашигтайг харж болно. Энэхүү ойлголт нь c++ гэлтгүй өөр хэлээр ч байгаа ба бид одоо size(), capacity()-н талаар ойлголттой боллоо. Үүндээр 2 дахин ихээр үүсгэж байгаа ч заавал ингэх албагүйг анхаарна уу.