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; } add_val<int,100>(x);

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]) { }

**THE ABOVE IS SUPER COOL. IT TAKES IN THE WHOLE ARRAY, NOT THE FIRST ELEMENT. AMAZING.**

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!

typeid(T).name()

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) { //stuff } }

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.

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.

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 10^{3} 10^{4})

Constant -> 1 1 1 1 1 1 1 1

Linear -> 1 2 5 10 50 100 10^{3} 10^{4}

Logarithmic -> 1 2 3 4 6 7 10 13

n-log-n -> 1 4 15 40 300 700 10^{4} 13*10^{4}

Quadratic -> 1^{2} 2^{2} 5^{2} 10^{2} 50^{2} 100^{2} 10^{6} 10^{8}

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.