[자료구조] Vector

• cVector (Array List): 객체를 저장하는 Sequence에 배열의 개념을 확장한 동적 배열 ADT
• 각 element는 그것의 특정한 index로 접근이 가능하다.
  • 음수와 같이 옳지 않은 index가 입력된경우 예외처리를 해준다.
• 주요 기능
  • at i: index i 에 있는 element를 반환한다.
  • set i,o: index i에 element o로 대체한다.
  • insert i,o: index i에 새로운 element o를 삽입하고 i부터 기존에 element들을 오른쪽으로 shift한다.
  • erase i: index i에 element를 삭제하고 i+1부터 기존에 element들을 왼쪽으로 shift한다.

data 1

data 2

data 3

data 4

data 5

data 6

       0            1             2             3             4            5             6            ...        n(size)

-> insert 4 , newdata

data 1

data 2

data 3

data 4

new data

data5

data6

0            1             2             3             4            5             6             7            ...            n

• 부가 기능
  • size()
  • empty()
• 예외 처리
  • at, set, erase -> vector가 비어있거나 i 가 vector의 size-1보다 큰 경우
  • insert -> i 가 vector의 size를 벗어난 경우
• 수행 시간
  • 배열의 크기를 N이라 하고 vector의 크기를 n이라 하면
  • at -> O(1) 상수시간
  • set -> O(1) 상수시간
  • insert -> O(n)
  • erase -> O(n)
  • 공간 사용 -> O(N) (배열기반) 

---

vector 는 그냥 array가 아니다.

Circular vector

• 환영 array, 실제 index와 사용자의 index를 다르게 함
  
  • 실제 index size-1인 사용자 index의 다음 index가 실제 index 0 인 vector

사용자 idx			0	1	2	3
실제 idx	0	1	2	3	4	5

Insert(0,obj)

    f <- f-1 (f의 index가 0일때 오류)
    f <- ((f-1)+N)Mod)N

   A[f] <- obj

Insert(i,obj)

    f <- (f+i)Mod N

    A[f] <- obj (f는 가장 앞의 실제 index) 

Erase(0)

    f <- f+1 (f의 index가 r의 index 보다 작을 때 오류)
    f <- ((f+1)+N)Mod)N

• Circular vector의 수행시간
  • insert(0, x), erase(0, x) -> O(1)
  • insert (i, x) -> O(n)
    worst case 기준 n/2 번 shift 연산으로 감소 시켜 줄 수 있음
    i의 index가 f와 가까우면 왼쪽으로 쉬프트 후 f<-((f-1)+N)ModN
    i의 index가 r과 가까우면 오른쪽으로 쉬프트 후 r<-((r+1)+N)ModN

Growable vector 

• Array가 다 차면 Array의 크기가 늘어남

data 1

data 2

data 3

data 4

data 5

insert(i,obj)

data 1

data 2

data 3

data 4

data 5

obj

 

#include <iostream>
#include <string>

using namespace std;
class GrowAbleVector{
private:
    int capa = 1;
    int size;
    int* Varr = new int[capa];
    int usr_idx = 0;
    void reserve(int newCapa){
        int* tmp = new int[newCapa];
        for(int i=0; i<getSize(); i++){
            tmp[i] = Varr[i];
        }
        capa = newCapa;
        Varr = tmp;
        delete[] tmp;
    }
public:
    GrowAbleVector(int capa){
        this->capa = capa;
    }
    bool empty(){ return (size==0); }
    int getSize(){ return size; }
    void setSize(int size){this->size = size;}
    int at(int idx){
        if(empty()||idx>=getSize()||idx<0){
            return -1;
        }
        else{
            return Varr[idx];
        }
    }
    void set(int idx, int data){
        if(empty()){
            cout << "Empty" << endl;
            return;
        }
        else if(idx>getSize() || idx<0){
            cout << "Index Error" << endl;
            return;
        }
        else if(idx == getSize()){
            insert(idx,data);
        }
        else{
            Varr[idx] = data;
        }
    }
    void insert(int idx, int data){
        if(getSize() == capa){
            reserve(2*capa);
        }
        if(idx>getSize() || idx<0){
            cout << "Index Error" << endl;
            return;
        }
        else{
            for(int i=getSize(); i>idx; i--){
                Varr[i] = Varr[i-1];
            }
            Varr[idx] = data;
            setSize(getSize()+1);
        }
    }
    void erase(int idx){
        if(empty()){
            cout << "Empty" << endl;
            return;
        }
        else if(idx>=getSize() || idx<0){
            cout << "Index Error" << endl;
            return;
        }
        else{
            for(int i=idx;i<getSize()-2;i++){
                Varr[i] = Varr[i+1];
            }
            Varr[getSize()-1] = 0;
            setSize(getSize()-1);
        }
    }
    void print(){
        if(empty()){
            cout << "Empty" << endl;
            return;
        }
        else{
            for(int i=0; i<getSize(); i++){
                cout<<Varr[i]<<" ";
            }
            cout << endl;
        }

    }
};
int main(){
    int t,n;
    cin >> n >> t;
    string cmd;
    GrowAbleVector V = GrowAbleVector(n);
    while(t--){
        cin>>cmd;
        if(cmd == "size"){
            cout << V.getSize()<<endl;
        }else if(cmd == "empty"){
            if(V.empty()){
                cout<<"yes"<<endl;
            }else{
                cout<<"no"<<endl;
            }
        }else if(cmd == "set"){
            int i,x;
            cin>> i>> x;
            V.set(i,x);
        }else if(cmd == "at"){
            int i;
            cin>> i;
            V.at(i);
        }else if(cmd == "insert"){
            int i,x;
            cin>> i>> x;
            V.insert(i,x);
        }else if(cmd == "erase"){
            int i;
            cin>> i;
            V.erase(i);
        }else if(cmd == "print"){
            V.print();
        }
        
    }
}