- real power of templates: define parameterized container classes
- Stack of integers:
class IntStack
{
protected:
int height;
int items[50];
public:
IntStack() : height(0) { }
void push(int x) { items[height] = x; ++height; }
int pop() { height--; return items[height]; }
int top() const { return items[height - 1]; }
int size() const { return height; }
bool isEmpty() const { return height <= 0; }
bool isFull() const { return height >= 50; }
};
- Stack of arbitrary type:
template<typename ItemType>
class Stack
{
protected:
int height;
ItemType items[50];
public:
Stack() : height(0) { }
void push(const ItemType &x) { items[height] = x; ++height; }
ItemType pop() { height--; return items[height]; }
ItemType top() const { return items[height - 1]; }
int size() const { return height; }
bool isEmpty() const { return height <= 0; }
bool isFull() const { return height >= 50; }
};
- heuristic: write template code using simple type, replace type by
template type
- use:
Stack<int> nums; nums.push(42); cout << nums.pop();
// reverse letters
Stack<char> lets;
char c;
cin >> c;
while ( cin.good() )
{
lets.push(c);
cin >> c;
}
while ( !lets.isEmpty() )
cout << lets.pop();
- or even a stack of stacks:
Stack<Stack<int>> ss;
- Note: type checking is guaranteed!
- Given Stack<char> lets;,
lets.push(1e30); // illegal!
lets.push("some string"); // illegal!
This is why
lets.pop()
doesn't need a type cast.
- Java does not actually guarantee this:
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> nums = new ArrayList<>();
nums.add(20);
test(nums);
System.out.println(nums.get(0));
System.out.println(nums.get(1));
}
public static void test(ArrayList myList) { // note: no item type
myList.add("duck");
}
}
which prints
20
duck
- You do get a warning:
C:\> java java-template-bug.java
Note: java-template-bug.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
20
duck
- But: it shows that Java generics provide no strong guarantees...
- caveat: put all code for C++ templates in .h file
- note: can also parameterize sizes of arrays:
template<typename ItemType, int size>
class Stack
{
protected:
int height;
ItemType items[size];
public:
Stack() : height(0) { }
void push(ItemType x) { items[height] = x; ++height; }
ItemType pop() { height--; return items[height]; }
bool isEmpty() const { return height <= 0; }
bool isFull() const { return height >= size; }
};
- passing monstrosity as parameter to function:
void dump(Stack<int, 1000> nums) { ...pop and print all... }
dump(bigstack);
Stack<int, 1001> xs;
dump(xs); -- illegal!
- alternatively:
template<int size>
void dump(Stack<int, size> nums) { ... }
dump(bigstack);
Stack<int, 1001> xs;
dump(xs); // ok
- usual solution: use typedef
- Introduces type synonyms:
typedef int num;
...
num x, y;
x = 100; y = x * x;
int z = y; // can mix int and num
- Also useful for consistency with templates:
typedef Stack<int, 1000> LgIntStack;
...
LgIntStack nums;
- Asside: older versions of C++ used class instead
of typename:
template<class ItemType, int size>
class Stack
{
protected:
int height;
ItemType items[size];
- This was just to minimize number of keywords
- typename is preferred
- Consider
IntStack s;
...
s.push(100);
- Classical issue: overhead of calling push
- C++: methods defined in class definition are inline
- Impact:
IntStack s; // see above
s.push(42);
int x = s.pop();
is compiled as
...
s.items[s.height] = 42; ++s.height;
int x = (s.height--, s.items[s.height]); // no calls
making further optimizations possible:
...
s.items[s.height] = 42; ++s.height;
int x = (s.height--, s.items[s.height]);
or even
int x = 42;
- Consider
const int MILLION = 1000000;
Vector nums(MILLION);
for(int i = 0; i < MILLION; ++i)
nums[i] = 1 / double(i);
- Remember that nums[i] is a call to operator[]:
for(int i = 0; i < MILLION; ++i) {
int &tmp = (if ( i < 0 || i >= nums._size )
throw std::out_of_range("Illegal index into vector."),
&nums.elements[i]);
tmp = 1 / double(i);
}
- Since no code changes nums._size, this is the same as
const int MILLION = 1000000;
Vector nums(1000000); // nums._size = 1000000
for(int i = 0; i < 1000000; ++i) {
int &tmp = (if ( i < 0 || i >= 1000000 )
throw std::out_of_range("Illegal index into vector."),
nums.elements[i]);
tmp = 1 / double(i);
}
- But a little logic shows i is never out of range, giving
const int MILLION = 1000000;
Vector nums(1000000);
for(int i = 0; i < 1000000; ++i)
nums.elements[i] = 1 / double(i);
- Other uses of inline:
template<typename T> inline
T max(T a, T b)
{
return a > b ? a : b;
}
- If a function is inline, its definition must be available to each call
- Typically: inline functions are defined in header files
- Inline is not compatible with virtual
- Virtual functions: code executed determined at runtime
- Must have address of function for this to work
- Inline functions have no address - substitute code at each call
- Standard template library: most operations are inline, code "compiles
away"
- An issue with inline functions: if inline a large function with
a loop, executable can be larger
- inline functions with loops don't make much sense - relative cost of
function call is small