MikeChen's Blog

Template classes In the last blog, we introduce template functions: Also, we can make a template class, which is similar to generic class in Java. Here is a simple version of linked list to store integer value Let’s now using template to make it to store all kinds of data Add prior to each member function definition: template < typename T> Add the < T >to the end of the class name in the member function implementation/definition(if we have separate .h and .cpp file) Still remember we use it in STL containers : vector<int> vector1; Functors Simple functors functors are classes which overload () operator Functors with member data Functors taking variables by reference Functors vs Functions Here, what we did is to use a function pointer and apply function using this function pointer. But now i want to make the function pointer to functors or make it to use both , what should i do? Use Template! What we do here?! Be

Overview There are various general methods for finding solutions to problems. Common ones include: Brute force - “generate and test” Divide and conquer Heuristics Dynamic Programming Brute Force This is roughly “generate and test”, generate all potential solutions and test for which ones are actual solutions. This method is extremely inefficient, as is O(n!), but can be useful in some small cases. Divide and Conquer Recursively, break the problem into smaller pieces, solve them, and put them back together. Merge-sort and Quick-sort were classic examples of this. Heuristics Two common types: Decisions within a procedure that gives optimal answer to make it go faster. Decisions within a procedure that might not give optimal answers, but are designed to give good answers that are impractical to obtain otherwise. Examples: “Admissible heuristic” in A* search - decreases the search time compared to plain search “pick a random pivot” in quick sort Greedy algorith

We have covered basic operator overloading in the previous blog, to summarize it, operator overloading can: Can define/change meaning of an operator, you can make it as member functions you can use it by a-b, or converts it to a.operator-(b) or operator-(a,b) , Access rights like any other function, e.g. has to be a friend or member to access private/protected member data/functions, Also, parameter types can differ from each other, e.g. MyFlt operator-(const MyFlt &, int); would allow an int to be subtracted from a MyFlt. Continued-Assignment vs comparison For example, we have created one class. And we new two object of this class, then we want to compare if two object are the same. We can’t simply use ob1 == ob2 . Because there is no == operator defined by default. Pointers could be compared though, but not the objects themselves. That why we need == operator overloading. Questions to ask yourself Define as a member or as a global? If global then does it need

Casting Casting away the const-ness When we have a const value, normally we can’t change them, but using casting, we can cast the const value to remove the constness of a reference or pointer. WARNING: Do not actually do this unless there is a really good reason! Casting away const-ness is really bad. C++11 new way to cast Four new casts: cosnt_cast< newtype >(?) dynamic_cast < newtype >(?): safely cast a pointer or reference from base-class to sub-class static_cast< newtype >(?): cast between types, converting the type reinterpret_cast< newtype >(?) Four types give more control over what you mean, and help you to identify the effects. Sometimes needed : dynamic_cast provides run-time type checking . Note: Casting a pointer will not usually change the stored address value, only the type. This is NOT true with multiple inheritance. static_cast Commonly used cast, attempts to convert correctly between two types. The example is in the pr

Default member functions Automatically generated functions 4 functions created by default if needed You can make them unavailable(e.g. private) Or change their behaviour A default constructor (no parameters needed) A copy constructor(copy one object to another) An assignment operator ( = operator) A destructor A default constructor Automatically created if and only if you do not create any other constructors This is why you can still create objects even when classes appear to have no constructors If you create any constructor, compiler will not create a default one for you. Since C++ 11 you can tell it to create a default one anyway by putting “= default” instead of “{}” ClassName() = default; if we comment on “DemoClass() = default;” This program will not compile. The copy constructor The copy constructor is used to initialize one object from another of the same type This includes when a copy is implicitly made: Passing object as a parameter i

Function Pointers Functions are stored in memory, in code segament. You can ask for the address of them. You can store these in function pointers. void (*g1)() = NULL; The above code means g1 is a function pointer, the function takes no parameter and it returns void. Note that (*g1)(); and g1() both call f1() Here we change again , we assign g1 to g2: Remember g2 is just a pointer , g1 assign to g2 so g2 just assign the address of g1 and g1 points to f1, so when we call g2, what we actually did is to call f1(); Callback Function A callback is any executable code that is passed as an argument to other code, which is expected to call back (execute) the argument at a given time Briefly speaking, callback function is a function pointer(a address), you know this pointer or address, you can use it whenever and wherever you want. Therefore, you can use it as function argument. v-tables non-virtual For normal/default (non-virtual) functions: Type of pointer determ

Inheritance how to use the inheritance? class MyClass : public MySuperClass{ //Do something } Equivalent of Java’s extends A class can have multiple base classes public/private/protected public : Anything can access the member private : Only class members can access the members, not even sub-class members protected : like private but also allows sub-class member to access the members Overriding methods If there is no override for some method The method will be unchanged in sub-class and use the base class method. There is overriden method and we don’t use virtual Because the subclass object is assigned to a baseclass pointer, so it will cast to baseclass. You can choose which you want to apply (by making the function virtual or not) When you use virtual , the functions in the sub-class are used (because the object is really of the sub-class type) When you don’t use virtual , the functions in the base-class are used (because the pointer type is used to deter

Graph Definition of a graph A graph is a set of nodes, or vertices, connected by edges. Graphs can be undirected - edges don’t have direction directed - edges have direction Undirected graphs can be represented as directed graphs where for each edge (X,Y) there is a corresponding edge (Y,X) . Graphs can also be unweighted weighted - edges have weights Notation Set V of vertices (nodes) Set E of edges (E⊂V*V) Node B is adjacent to A if there is an edge from A to B.(A —–>B) Paths and reachability A path from A to B is a sequence of vertices A1,…,An such that there is an edge from A to A1, from A1 to A2,… from An to B Vertex B is reachable from A if there is a path from A to B Other Terminology A cycle is a path from a vertex to itself Graph is acyclic if it does not have cycles Graph is connected if there is a path between every pair of vertices Graph is strongly connected if there is a path in both directions between every pair of vertices how t