Array as Memory Block in C/C++
(1)acess:
data getByIndex(index)
insertByIndex(index, data)
(2)maintenance:
- construct(length)
- updateByIndex(Index, data)
removeByIndex(index)
desired property : fast computation of address from index
=> fast random access
implicit assumption:
index to address done by formula
C++ STL Vector : a Growing array
get, update
STL vector : a more "structured" way of using arrays
!!STL
2-D array
access:
index = (row, col)
data getByIndex(Index)
address = arr + sizeof(data)x(row x nCol + cool)
maintenance:
length = (nRow, nCol)
construction(length)
arr=new data [nRow x nCol]
implementation
(1)one-block:tradeoff & succinct
(2)array of array: easier for programmers
Ordered array
想像有連續放東西：排好的值(ordered Value)
insert
update
Asymptotic Notation
goal : tough rather than steps
f(n)
g(n)
