Used for implementing the same function repeatedly, but acting on different types.

It does pretty much the same thing, but again, on different types.

It is the most important feature of C++, at least in Prasanna's opinion.

template <typename T>
T const& Max(T const& lhs, T const& rhs) {
  return (lhs<rhs)?rhs:lhs;
template <typename T>
int Compare(T const& lhs, T const& rhs) {
  if(lhs<rhs) return -1;
  if(rhs<lhs) return 1;
  else return 0;

For templated functions, always pass by reference.

For templated functions that would not work with certain types (for example, using operators that are not overloaded), it will still compile unless it it specifically used by the incompatible type.

What this means is that the compiler compiles the template function multiple times, the first one being to check for general errors in the general template function and THEN compiling for each type.

However, the template function takes up no space in the text area due to the fact that it is not really a function; rather, it is a template.

Template functions should be defined in the header files

TemplateFunction<int>(1,2) FORCES the compiler to create a templated function with int as a template argument

Lazy Semantics means a shallow copy UNTIL the copier is changed. Thus there are some extra variables like boolean flags and such.

Template argument deduction: Deducing the template parameter from the template argument.

If you supply a different number of template arguments than the number of template paramaters, WHAT DO. Unless, of course, you force the compiler to use a certain template paramater and it works.

template <typename T, int VAL>
void add_val(T& t( {
  t += VAL;


So yeah, you can have templates with multiple types or types with scalars or whatever.

template classes NEED to be explicit, template functions do not.

T (&x) [N]

void array_init(T (&x) [N]) 

template <class InIter, class UnaryOp>
UnaryOp my_foreach(InIter first, InIter last, UnaryOp op

last is ONE after the last element being iterated through.

template <typename T, size_t N>
void array_init(T (&r) [N]) {

Also kinda cool is that if you do void test(&T) and test(T) and pass in an array, first one will take in the whole array, second one will only take in a pointer to the first element of the array.

When you have a test(&T) and test(T), its ambiguous

constexpr makes the compiler find the result of an expression at COMPILE TIME, which is weird but is useful. For example, you can use it to generate arrays of "variable" sizes (not really since it's done at compile time, but you get the gist.)

noexcept is added to the end of functions, like how you do a const function, but it makes it such that the compiler will NOT THROW AN EXCEPTION.

You can overload template functions, too!


Always place plain ol' functions at the TOP

Function template specialization

template <typename T>
void my_sort(std::vector<T>& r) {

template <>
void my_sort<char const*>(std::vector<char const*>& r) {

CITIZENSHIP Plain ol' functions > Generic Templates > Specialized Templates

Templates can check for better matches: in other words, foo(T) and foo(T*), foo(T*) would be picked if a pointer was used as an argument

Order matters for specialization

template <typename T, typename BinaryOp = std::less<T>>


Classes are ninjas. They can disguise as functions.

bool operator()(int lhs, int rhs)

^ A class or struct that implements the above is a functor.

template <typename T>
struct abs_cmp {
  bool operator() (T const& lhs, T const& rhs) {
abs_cmp<int> CO;
std::cout << CO(x,y) << std::endl;
template <typename T, typename BinaryOp = my_less<T>>
int Compare(T const& lhs, T const& rhs, BinaryOp f= BinaryOp()) { //myless is a functor

FOR A NON FUNCTOR, BinaryOp f = BinaryOp is fine.

Properties of Containers

1. Sequential

2. Associative

3. Unordered (Don't worry 'bout it.)

Sets/Maps (Associative) utilize Binary Trees. Let's say you have 2^20 values (around a million). You only need 20 iterations to get to where you wanna be. Sets don't have key-value, just value. Maps have key-value. Maps are awesome for high score storage. Multisets and multimaps are used for when two values can be the same.

Complexity & Big-O Notation

Linear algorithm, Quadratic algorithm and Constant-time algorithm (x is input, y is time taken)

ToLowerCase -> linear algorithm
Subscript [] operator -> Constant-timer operator

Type -> Notation -> Meaning
Constant -> O(1) -> Subscript operator
linear -> O(n) -> Linked list
Logarithmic -> O(log(n)) -> Binary Tree
n-log-n -> O(n.log(n)) -> std::sort (QuickSort)
Quadratic -> O(n^2) -> Selection sort

Complexity -> Number of elements (1 2 5 10 50 100 103 104)
Constant -> 1 1 1 1 1 1 1 1
Linear -> 1 2 5 10 50 100 103 104
Logarithmic -> 1 2 3 4 6 7 10 13
n-log-n -> 1 4 15 40 300 700 104 13*104
Quadratic -> 12 22 52 102 502 1002 106 108

Functions used for manipulating size: size(), empty(), max_size() (gives the amount that the container can store in memory, different for 32 and 64 bit)

g++ and cl have different policies about vector sizes and capacities.

std::vector<Str> vs = std::vector<Str>(1024)

Do the above and you will be banished. This calls the default constructor for all 1024 elements. Adding something else would be adding a 1025th element.

Instead use vs.reserve(1024) size will be 0, capacity will be 1024.

The following is stolen from http://www.gotw.ca/publications/mill17.htm:

  Why Not Specialize: The Dimov/Abrahams Example

  Consider the following code:

  // Example 2: Explicit specialization 
  template<class T> // (a) a base template 
  void f( T );

  template<class T> // (b) a second base template, overloads (a) 
  void f( T* );     //     (function templates can't be partially 
                    //     specialized; they overload instead)

  template<>        // (c) explicit specialization of (b) 
  void f<>(int*);

  // ...

  int *p; 
  f( p );           // calls (c)

  The result for the last line in Example 2 is just what you'd expect. The question of the day, however, is why you expected it. If you expected it for the wrong reason, you will be very surprised by what comes next. After all, "So what," someone might say, "I wrote a specialization for a pointer to int, so obviously that's what should be called" - and that's exactly the wrong reason.

  Consider now the following code, put in this form by Peter Dimov and Dave Abrahams:

  // Example 3: The Dimov/Abrahams Example 
  template<class T> // (a) same old base template as before 
  void f( T );

  template<>        // (c) explicit specialization, this time of (a)
  void f<>(int*);

  template<class T> // (b) a second base template, overloads (a) 
  void f( T* );

  // ...

  int *p; 
  f( p );           // calls (b)! overload resolution ignores 
                    // specializations and operates on the base 
                    // function templates only

  If this surprises you, you're not alone; it has surprised a lot of experts in its time. The key to understanding this is simple, and here it is: Specializations don't overload.