Iterators and Running time analysis

• C++ won't compile templated method/classes until they are called/instantiated
• 'auto' : C++ will figure out that p is type BSTNode<int>*

auto p = new BSTNode<int> (10);

• Pointer arithmetic: C++ will add the value of a pointer by the size of its type.

void print_inorder(int* p, int size){
    for(int i=0; i<size; i++){
        std::cout<< *p << endl;
        ++p;
    }
}

• C++ STL interator:
  • can't redifine pointer arithmetic for pointers
• Iterator: a wrapper around an object that we can control its behavior by overloading its operators(such as *, !=, ++).
• Iterator can't be null.
• Iterators are the construct behind for loop.

• REFERENCES: UCSD CSE 100 - Data Structures Podcast 1/18/2017