Vector or array list -> 보통 python에서는 Vector보다 Array list를 많이 사용하고 Array list가 좀 더 High-level ADT로 유저 친화적
ADT가 제공하는 함수
at(i) : index i에 있는 V의 원소를 리턴, 파라미터 i가 범위 밖으로 벗어나면 error
set(i,e) : index i에 있는 원소를 e로 대체, 파라미터 i가 범위 밖으로 벗어나면 error 바꾸기
insert(i,e) : index i에 e를 넣는데, index i 이후 원소들은 모두 오른쪽으로 밀고 빈자리에 e를 삽입, 파라미터 i가 범위 밖으로 벗어나면 error 오른쪽으로 밀기
erase(i) : index i에 있는 원소를 지움, 파라미터 i가 범위 밖으로 벗어나면 error
Example
Operation
Output
V
insert(0,7)
-
(7)
insert(0,4)
-
(4,7)
at(1)
7
(4,7)
insert(2,2)
-
(4,7,2)
at(3)
error
(4,7,2)
erase(1)
-
(4,2)
insert(1,5)
-
(4, 5, 2)
insert(1,3)
-
(4, 3, 5, 2)
set(3, 8)
-
(4, 3, 5, 8)
Pseudocode
Insert
Insert는 이런식으로 오른쪽으로 밀고 새로운 원소를 삽입해준다. (방 만드는 느낌)
Algorithm insert(i, e): //i는 index, e는 element
for j = n-1, n-2, ... , i do
A[j+1] = A[j] //j번째 있는 원소를 j+1번째에 넣는다.
A[i] = e // 빈 자리에 새로운 원소 e를 넣는다.
n = n + 1 //n은 사이즈, 삽입했으므로 사이즈 1 늘린다.
erase 메꾸는 느낌 (삭제할 인덱스에 덮어씌운다.)
Algorithm erase(i):
for j = i+1, i+2, ..., n-1 do
A[j-1] = A[j] // j번째 원소를 j-1번째 넣어준다.
n = n - 1 // erase 했으므로 사이즈를 하나 줄인다.
Time Complexity (Big-O Notation)
Operation
Time
size()
O(1)
empty()
O(1)
at(i)
O(1)
set(i,e)
O(1)
insert(i,e)
O(n)
erase(i)
O(n)
기존보다 capacity가 더 큰 Arry를 위한 코드
void ArrayVector::reserve(int N) { //최소 N 사이즈
if(capacity >= N) return; //이미 충분히 크므로 이 함수를 실행할 필요X
Elem* B = new Elem[N}; //B는 더 큰 Array 만듦
for(int j = 0; j < n; j++)
B[j] = A[j] //A의 원소를 새로운 Array B에 값 복사
if(A != NULL) delete[] A; // discard old array
A = B; //A를 B와 완전히 똑같게 만들어줌
capacity = N; //사이즈 = 용량
}
void ArrayVector::insert(int i, const Elem& e){
if(n >= capacity) //사이즈가 capacity보다 크거나 같으면, capacity 더 필요함
reserve(max(1,2*capacity)) //capacity 더 할당(double strategy)
for (int j = n-1; j>= i; j--)
A[j+1] = A[j]; // j번째 원소를 j+1번째에 넣어줌
A[i] = e; // 빈 공간인 index i에 원소 e 넣어줌
n++; //원소 추가했으므로 사이즈 1 늘리기
}
더 큰 용량을 할당하려고 하고 이를 reserve 함수로 구현했다. 한마디로 capacity를 늘리는 것인데 용량이라고 생각하면 된다. capacity를 늘리는 방법에는 incremental과 doubly 방법이 있는데 여기서는 doubly 방법을 이용했다.
