semi-semester review

example: C/C++ (dense) int(any type, through C++ template) array

  • 1 Lesson 7 container/iterator - 图1#card=math&code=%5CTheta%20%28N%29) storage(small)
  • 2 indexed (random) access R/W in Lesson 7 container/iterator - 图2#card=math&code=%5CTheta%20%281%29)
  • 3 iterative (sequential access) —->(ptr, index)
  • 4 fixed maxlen
  • 5 Lesson 7 container/iterator - 图3#card=math&code=%5Cmathcal%7BO%7D%20%28N%29) insertion/removal

This type of data structure can’t satisfy our command:
faster Lesson 7 container/iterator - 图4#card=math&code=%5Cmathcal%7BO%7D%20%281%29) insertion/removal & dynamic maxlen Lesson 7 container/iterator - 图5 doubly-linked list(better for removal)

  • 1 Lesson 7 container/iterator - 图6#card=math&code=%5CTheta%20%28N%29) storage, W/R
    -2 often slow
  • 3 iterative access (ptr) (restricted access)
  • 4 dynamic maxlen
  • 5 Lesson 7 container/iterator - 图7#card=math&code=%5Cmathcal%7BO%7D%20%281%29) insertion/ removal

  • sparse array “ordered by index” in array/ linked list

    • Lesson 7 container/iterator - 图8#card=math&code=%5CTheta%20%28NZ%29) storage
    • indexed access in Lesson 7 container/iterator - 图9#card=math&code=%5Cmathcal%7BO%7D%20%28log%20NZ%29) by binary search
    • iterative access with all non-zero terms
    • fixed maxlen
    • Lesson 7 container/iterator - 图10#card=math&code=%5Cmathcal%7BO%7D%28NZ%29) insertion/removal for array, Lesson 7 container/iterator - 图11#card=math&code=%5Cmathcal%7BO%7D%281%29) for linked list

doubly-linked list Lesson 7 container/iterator - 图12 deque (stack + queue)

vector

abstraction “essense”

    1. save implementation efforts (template: type abstraction)
    1. “easy” change of data structure

  • functionality abstraction
    dense array & sparse array
    indexed (random) access: vector

C++ vector

C++ vector: extendable array

  • at(i)
  • set(i)
  • insert
  • erase

extendable array

if array A “overflow” Lesson 7 container/iterator - 图13 grow the array

  • How to grow?

    • allocate new array B Lesson 7 container/iterator - 图14#card=math&code=%5Cmathcal%7BO%7D%20%281%29)
    • copy contents from A to B Lesson 7 container/iterator - 图15#card=math&code=%5Cmathcal%7BO%7D%20%28N%29)
    • remove A and assign B to A Lesson 7 container/iterator - 图16#card=math&code=%5Cmathcal%7BO%7D%20%281%29)

Lesson 7 container/iterator - 图17

Vector Lesson 7 container/iterator - 图18

list(iterative, sequential, postional) Lesson 7 container/iterator - 图19

  • insert(ptr, e)
  • remove(ptr,e)
  • get(ptr)
  • begin() : head
  • isEnd(): ==NULL
  • next()

iterator

abstraction of ptr (“address”)

dense array linked list
begin &arr[0] head
end &arr[N] NULL
next p++ p->next 
  1. for (iterator<vector<int>> p = c.begin();p!=c.end();p = p.next()){
  2.     sum += elem(p);
  3. }
  4. elem(p) ===> (*p)

iterator : an abstract of the element position