C++ in a Nutshell Skill

Templates

Function Templates

// Basic function template — compiler deduces T from arguments
template<typename T>
T abs(T x) { return x < 0 ? -x : x; }

// Explicit instantiation
int result = abs<int>(CHAR_MIN);
// Implicit instantiation (type deduced)
int result = abs(-5);

// Multiple type parameters
template<typename floatT, typename T>
floatT distance(const point<T>& p) {
    return std::sqrt(static_cast<floatT>(p.x()*p.x() + p.y()*p.y()));
}
// Call: must provide first arg explicitly when deduction is ambiguous:
double d = distance<double>(p);

Class Templates

template<typename T>
class point {
public:
    typedef T value_type;              // associated type — useful for generic code
    point(const T& x, const T& y) : x_(x), y_(y) {}
    point() : x_(T()), y_(T()) {}
    T x() const { return x_; }
    T& x()      { return x_; }
    void x(const T& nx) { x_ = nx; }
private:
    T x_, y_;
};

// Instantiation
point<int> p(42, 0);
point<std::complex<double>> s({1,2}, {3,4});

Template Parameters (3 kinds)

// 1. Type parameter (typename or class)
template<typename T> class container;

// 2. Value parameter (integral, pointer, or reference type)
template<unsigned Size>
struct fixed_name {
    char name_[Size+1];
    unsigned size() const { return Size; }
};
fixed_name<100> n;
// NOTE: string literals can't be template args (unnamed, internal linkage)
const char def[] = "default";
template<const char* Str> void print();
print<def>();    // OK
// print<"default">(); // Error

// 3. Template template parameter
template<template<typename, typename> class Container, typename T>
class adapter { Container<T, std::allocator<T>> data_; };

Total Specialization

// General template
template<typename T>
class point { /* general: use const T& for efficiency */ };

// Full specialization for int (pass by value — already cheap)
template<>
class point<int> {
public:
    point(int x, int y) : x_(x), y_(y) {}
    // ... simpler pass-by-value interface
private: int x_, y_;
};

// Function specialization
template<>
int abs<int>(int x) { return x < 0 ? -x : x; }

Partial Specialization (class templates only)

template<typename T>
class hashset { /* general */ };

// Partial specialization: pointer types
template<typename T>
class hashset<T*> { /* specialized for pointers */ };

// Default template arguments (class templates only, not functions)
template<typename T, typename A = std::allocator<T>>
class hashset { bool empty() const; };
// Member definitions omit default args:
template<typename T, typename A>
bool hashset<T, A>::empty() { return size() == 0; }

---

Type Traits

Trait tag dispatch pattern

// Tag types (empty structs used as compile-time values)
struct is_integer_tag {};
struct is_not_integer_tag {};

// Default: not integer
template<typename T>
struct is_integer { typedef is_not_integer_tag tag; };

// Explicit specializations for each integral type
template<> struct is_integer<int>            { typedef is_integer_tag tag; };
template<> struct is_integer<short>          { typedef is_integer_tag tag; };
template<> struct is_integer<unsigned>       { typedef is_integer_tag tag; };
// ... etc.

// Or use a macro to reduce repetition:
#define DECL_IS_INTEGER(T)          \
template<> struct is_integer<T> {   \
    typedef is_integer_tag tag;     \
}
DECL_IS_INTEGER(bool); DECL_IS_INTEGER(char); DECL_IS_INTEGER(int);
#undef DECL_IS_INTEGER

// Dispatch to different implementations based on trait
template<typename InputIter>
void list_init(InputIter first, InputIter last) {
    construct(first, last, typename is_integer<InputIter>::tag());
}
void construct(size_type n, T val, is_integer_tag) { /* fill n copies */ }
void construct(InputIter f, InputIter l, is_not_integer_tag) { /* copy range */ }

---

Function Overloading and Overload Resolution

Rules

Resolution process:
1. Name lookup builds candidate list (same name in scope)
2. Prune by argument count
3. Rank remaining candidates by argument types (NOT return type)
4. Select "best" — or report ambiguity error

Ranked (best-to-worst):
  Exact match (or trivial conversion: T → const T)
  Promotion (int → long)
  Standard conversion (double → int)
  User-defined conversion (operator T)
  Match with ellipsis (...)

Overloading pitfalls

// Cannot overload on return type alone:
int    add(int, int);
long   add(int, int); // ERROR

// Derived class hides base class overloads (doesn't overload):
class Base { void f(int); };
class Derived : public Base {
    void f(double);  // hides Base::f(int) — doesn't overload it!
    using Base::f;   // fix: bring f(int) into Derived's scope
};

// Operator overloading: prefer non-member for symmetric operators
// (allows conversion on BOTH operands, not just right)
// OK: rational + 2, and 2 + rational
template<typename T>
rational<T> operator+(const rational<T>&, const rational<T>&);
// Member: only rational + 2 works, not 2 + rational

---

STL Containers

Container selection guide

Container	Access	Insert/Erase	Notes
vector<T>	O(1) random	O(n) middle, O(1) amort. back	Cache-friendly; prefer by default
deque<T>	O(1) random	O(1) front/back, O(n) middle	Double-ended growth
list<T>	O(n)	O(1) anywhere with iterator	Node-based; stable iterators
set<T>	O(log n)	O(log n)	Unique keys, sorted
multiset<T>	O(log n)	O(log n)	Duplicate keys, sorted
map<K,V>	O(log n)	O(log n)	Unique K, sorted, K→V
multimap<K,V>	O(log n)	O(log n)	Duplicate K, sorted

Associative container API

std::map<std::string, int> m;

// Insert
m.insert({"key", 42});             // returns pair<iterator, bool>
m["key"] = 42;                     // operator[] inserts if not present

// Lookup
auto it = m.find("key");           // O(log n), returns end() if not found
if (it != m.end()) { it->second; }

// Range lookup
auto [lo, hi] = m.equal_range("key");  // lower_bound..upper_bound pair
auto it2 = m.lower_bound("k");     // first element >= "k"
auto it3 = m.upper_bound("k");     // first element > "k"

// Count
m.count("key");                    // 0 or 1 for map, 0..N for multimap

// Erase
m.erase("key");                    // erase by key
m.erase(m.find("key"));           // erase by iterator

Container exception guarantees

Single insert (push_back/insert single element):
  Failure leaves container unchanged (strong guarantee)

Range insert:
  list: all-or-nothing (strong)
  map/set/vector: partial success possible (basic guarantee)

erase, pop_back, pop_front: never throw
swap: only throws if Compare object's copy/assign throws

---

Iterator Categories

Input      →  read-only, single-pass, ++, *, == only
Output     →  write-only, single-pass, ++, *=
Forward    →  read/write, multi-pass, forward only
Bidirect.  →  forward + -- (backward)
RandomAcc  →  bidirectional + [], +n, -n, it1-it2

Container           → Iterator Category
vector, deque       → Random access
list                → Bidirectional
set, map, etc.      → Bidirectional
istream_iterator    → Input
ostream_iterator    → Output

Iterator safety rules

- Never dereference end() — undefined behavior
- [first, last) notation: first is included, last is NOT
- Iterators into node-based containers (list, set, map):
    → stay valid unless that node is erased
- Iterators into array-based containers (vector, deque):
    → may be invalidated by ANY insertion (reallocation)

Special iterators

// Stream iterators
std::copy(std::istream_iterator<double>(cin),
          std::istream_iterator<double>(),   // end-of-stream sentinel
          std::ostream_iterator<double>(cout, "\n"));

// Insert iterators (output iterators that call push_back/push_front/insert)
std::copy(src.begin(), src.end(),
          std::back_inserter(dst));          // calls push_back

std::copy(src.begin(), src.end(),
          std::front_inserter(lst));         // calls push_front

std::copy(src.begin(), src.end(),
          std::inserter(s, s.begin()));      // calls insert(pos, val)

// Reverse iterators
for (auto it = v.rbegin(); it != v.rend(); ++it) { /* backwards */ }

---

STL Algorithm Patterns

erase-remove idiom (algorithms can’t erase directly)

// Algorithms rearrange, not erase. Use erase+remove together:
std::vector<int> v = {1, 2, 3, 2, 4, 2};

// Erase all 2s
v.erase(std::remove(v.begin(), v.end(), 2), v.end());

// Erase elements matching predicate
v.erase(std::remove_if(v.begin(), v.end(),
                       [](int x) { return x % 2 == 0; }),
        v.end());

// Generic helper
template<typename C>
void erase(C& c, const typename C::value_type& item) {
    c.erase(std::remove(c.begin(), c.end(), item), c.end());
}

Search algorithms

// Linear search (all sequence containers)
auto it = std::find(v.begin(), v.end(), 42);
auto it2 = std::find_if(v.begin(), v.end(), [](int x) { return x > 10; });

// Associative container: use member find() — O(log n), not O(n)
auto it3 = mySet.find(42);         // Use this, not std::find
auto it4 = myMap.find("key");

Numeric algorithms ()

#include <numeric>
int sum = std::accumulate(v.begin(), v.end(), 0);
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
std::vector<int> cumsum;
std::partial_sum(v.begin(), v.end(), std::back_inserter(cumsum));
std::vector<int> diffs;
std::adjacent_difference(v.begin(), v.end(), std::back_inserter(diffs));

---

Custom Container Design

Required member types

template<typename T, typename Alloc = std::allocator<T>>
class slist {
public:
    // Required member types
    typedef typename Alloc::reference         reference;
    typedef typename Alloc::const_reference   const_reference;
    typedef typename Alloc::pointer           pointer;
    typedef Alloc                             allocator_type;
    typedef T                                 value_type;
    typedef size_t                            size_type;
    typedef ptrdiff_t                         difference_type;
    class iterator;
    class const_iterator;

    // Required operations
    iterator begin();   const_iterator begin() const;
    iterator end();     const_iterator end() const;
    bool empty() const;
    size_type size() const;
    void swap(slist& other);
};

Custom iterator (derive from std::iterator)

class my_iterator :
    public std::iterator<std::forward_iterator_tag, T> {
public:
    bool operator==(const my_iterator& o) const { return node_ == o.node_; }
    bool operator!=(const my_iterator& o) const { return !(*this == o); }
    my_iterator& operator++() {       // pre-increment
        node_ = node_->next;
        return *this;
    }
    my_iterator operator++(int) {     // post-increment
        my_iterator tmp = *this;
        ++(*this);
        return tmp;
    }
    T& operator*()  { return node_->value; }
    T* operator->() { return &node_->value; }
private:
    link_type* node_;
};

---

Preprocessor Tips

// Stringification
#define TEST(expr) std::cout << #expr << " = " << (expr) << '\n'
TEST(1 + 2);  // prints "1 + 2 = 3"

// Token concatenation (##)
#define DECLARE(type, name) type name##_ = type()
DECLARE(int, foo);  // expands to: int foo_ = int()

// Pitfall: template args with commas confuse preprocessor
#define DECL(t, n) t n
DECL(std::map<int,int>, m);  // Error: preprocessor sees 3 args

// Fix: use typedef or extra parens
typedef std::map<int,int> IntMap;
DECL(IntMap, m);  // OK

// Predefined macros
__FILE__       // current filename (string literal)
__LINE__       // current line number (integer)
__DATE__       // compilation date "Mmm dd yyyy"
__TIME__       // compilation time "hh:mm:ss"
__cplusplus    // 199711L for C++98/03