C++

From David's Wiki
\( \newcommand{\P}[]{\unicode{xB6}} \newcommand{\AA}[]{\unicode{x212B}} \newcommand{\empty}[]{\emptyset} \newcommand{\O}[]{\emptyset} \newcommand{\Alpha}[]{Α} \newcommand{\Beta}[]{Β} \newcommand{\Epsilon}[]{Ε} \newcommand{\Iota}[]{Ι} \newcommand{\Kappa}[]{Κ} \newcommand{\Rho}[]{Ρ} \newcommand{\Tau}[]{Τ} \newcommand{\Zeta}[]{Ζ} \newcommand{\Mu}[]{\unicode{x039C}} \newcommand{\Chi}[]{Χ} \newcommand{\Eta}[]{\unicode{x0397}} \newcommand{\Nu}[]{\unicode{x039D}} \newcommand{\Omicron}[]{\unicode{x039F}} \DeclareMathOperator{\sgn}{sgn} \def\oiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x222F}\,}{\unicode{x222F}}{\unicode{x222F}}{\unicode{x222F}}}\,}\nolimits} \def\oiiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x2230}\,}{\unicode{x2230}}{\unicode{x2230}}{\unicode{x2230}}}\,}\nolimits} \)

C++ is a very popular and powerful language which includes all the low-level features of C (e.g. pointers, operator overloading) along many high-level features (RAII, regex, STL containers) thanks to the C++ standard library.

Usage

How to do things using the C++ standard library (stdlib).

Compilation

cmake

g++

g++ my_driver.c [-Iincludefolder] -o my_program.out

Standard optimizations

  • -std=c++17 for C++17 support
  • -O3 for level 3 optimizations
  • -g to include debugging info
  • -march=native - use all instructions available on the current CPU
  • -mtune=native - optimize for the current CPU

Syntax

Main

All C++ programs launch in a main function. Similar to C, the arguments are int argc and char *argv[].
These can be easily converted to a std::vector<std::string> for convenience.

#include <string>
#include <vector>
int main(int argc, char *argv[]) {
  std::vector<std::string> args(argv, argv + argc);
  // Your code here
  return EXIT_SUCCESS;
}

Headers

Reference

C++ includes C-headers such as math.h and cmath.
The C-style header will place everything in the global namespace while the C++ header will place everything in std.
You should use cmath.

Lambda Expressions

Reference

Casting

Types of casts

C++ has several types of casts including:

  • static_cast - your standard cast with conversion. Does not perform any checks.
  • dynamic_cast - for casting objects with checking, requires a polymorphic base class (with a virtual function). Will return nullptr.
  • reinterpret_cast - cast without any conversion, for directly dealing with binary data, equivalent to *(T*) in C.

References

References are accepted or store using &.
For example:

void healPerson(Person &person) {
  person.health = 100;
}

References are like pointers since they do not copy the object except they cannot be null and they cannot be reassigned.
Note that primitives can also be used with references, in which case changes will propagate to the underlying value.
You can also use them as class attributes, initializing them in the constructor's initializer list.
To store references in a vector, you can use std::reference_wrapper and include the functional header.

Types

For simple programs, you can use the standard types:

  • int, uint, long, size_t
  • float, double

See SO for the standard and guaranteed precision of these built-in types.

C++ also has fixed-width types in #include <cstdint (since C++11).
cppreference cstdint
I recommend using these for anything with specific or high precision requirements.
Typically, I use:

  • uint8_t instead of char or std::byte.
  • int64_t instead of long long

String

#include <string>

// c-str to string
char *old_string = "my c-style string";
string cpp_string(old_string);

// string to c-str
cpp_string.c_str();

// char to string
char my_char = 'a';
string my_str(1, my_char);

String Interpolation

Reference

#include <iostream>
#include <sstream>
#include <string>

int main() {
    std::string a = "a", b = "b", c = "c";
    // apply formatting
    std::stringstream s;
    s << a << " " << b << " > " << c;
    // assign to std::string
    std::string str = s.str();
    std::cout << str << "\n";
}

Buildings Strings

The Complete Guide to Building Strings In C++
There are multiple ways of buildings strings in C++.
Strings are mutable in C++.
I typically use + or ostringstream to build strings.

std::basic_string_view

std::basic_string_view

This is useful for writing functions which accept anything that looks like a string such as substrings, since typically std::string::substr performs a copy.

Note that std::string_view is std::basic_string_view<char>.

Filesystem

#include <filesystem>
Convenient functions for filesystem. Added since C++17.

Path

cppreference

Note if you use g++ <= version 9, you will need to add the flag -lstdc++fs.

using std::filesystem::path;

// Initialization
path my_path = "my_dir/my_file";
// or my_path = path("my_dir") / "my_file";

// Append to path
path("foo") / "bar"; // path("foo/bar")
path("foo") / "/bar"; // path("/bar")

// Print
std::cout << my_path << std::endl; // prints "my_dir/my_file" with quotes
std::cout << my_path.string() << std::endl; // prints my_dir/my_file without quotes
Notes
  • path supports implicit conversion to string


Directories

Notes
  • create_directory requires that the parent directory already exists
    • If not, use create_directories instead

Fstream

#include <fstream>
Used for input/output of files

Reading and Writing

Reading and writing is done using fstream.
If you don't need r/w, use istream for reading or ostream for writing.

#include <iostream>
#include <fstream>

int main() {
  std::ifstream my_file("my_file.txt");
  std::string line;
  // Read line by line
  // You can also read using <<
  while (getline(my_file, line)) {
    std::cout << line << std::endl;
  }
  return 0;
}

Reading a whole file

Reference and comparison of different methods

#include <fstream>
#include <string>
#include <cerrno>

std::string get_file_contents(const std::string &filename)
{
  std::ifstream in(filename, std::ios::in | std::ios::binary);
  if (in.good())
  {
    std::string contents;
    in.seekg(0, std::ios::end);
    contents.resize(static_cast<unsigned int>(in.tellg()));
    in.seekg(0, std::ios::beg);
    in.read(&contents[0], contents.size());
    return contents;
  }
  std::cerr << "Failed to open file: " << filename << std::endl;
  throw(errno);
}

Regular Expressions

#include <regex>

Reference


Thread

#include <thread>
std::thread reference

Basic Usage:

std::thread my_thread(thread_function);
// Calling methods
// You can also pass in parameters as usual
std::thread my_thread(&Class::method, this));
// Lambda functions
std::thread my_thread([&]() {
 // do something
});

// Wait for thread to finish
my_thread.join();

// get id of thread
std::thread::id my_id = my_thread.get_id();

// get id of this thread
std::thread::id my_id = std::this_thread::get_id();

Sleep

std::this_thread::sleep_for(std::chrono::milliseconds(1));

Parallel For

Reference

Memory

#include <memory>

Smart Pointers

Smart Pointers
Smart pointers were added in C++11.
There are 3 types of smart pointers:

  • unique_ptr
  • shared_ptr
  • weak_ptr

Use unique_ptr when one piece of code owns the memory at any given time.
Use shared_ptr when multiple objects need to reference the same thing.
Use weak_ptr to avoid cyclic dependencies which cause issues with reference counting.
If you are using C++14 or newer, you should use make_unique or make_shared which will only make one memory allocation for both the object and the pointer rather than two memory allocations.
Alternatively if you already have a smart pointer, you can call my_ptr.reset(new Car()) to change the pointer or my_ptr.reset() to deallocate the object referenced by the pointer. Example:

// Block-scope car
Car my_car;

// Old C++
// Must call delete my_car; to avoid memory leaks.
Car *my_car = new Car();

// Using unique ptr
std::unique_ptr<Car> my_car(new Car());

// Or starting from C++14
auto my_car = std::make_unique<Car>();
Notes
  • If the object you need is not very large, you can consider just including it as part of your class (or leaving it on the stack) rather than use pointers.
  • If you want to get a copy of the smart pointer to the current object, the object must publically inherit std::enable_shared_from_this<T>
    • Then you can call shared_from_this() from within any method (not the constructor).
    • May throw bad_weak_ptr if you call shared_from_this() without make_shared or if you do not publically inherit std::enable_shared_from_this<T>
  • When writing functions when do not operate on pointers and do not claim ownership of objects, you should just take a reference to the object as the argument.

Garbage Collection

Starting from C++11, you should use smart pointers such as shared_ptr which have automatic garbage collection.

Traditional C++ does not have garbage collection.
After using new to allocate an object, use delete to deallocate it.
You can also use C allocation with malloc, calloc, alloca, and free, though it is not recommended since these are not type-safe.

Custom Deleter

Custom Deleters
When using smart pointers, the default deleter is the delete function but you can also specify your own deleter.


# Using a functor
struct AVFrameDeleter {
  void operator()(AVFrame *p) { av_frame_free(&p); }
};
std::unique_ptr<AVFrame, AVFrameDeleter> rgb_frame(av_frame_alloc());

# Using free
std::unique_ptr<void *, decltype(std::free) *> my_buffer(std::malloc(10), std::free);


Deallocate

Normally, containers such as std::vector will automatically deallocate memory from the heap when the destructor is called. However, occationally you may want to coerse this deallocation yourself.
There are a few ways to do this:

  • Use smart pointers
  • Swap
  • Call a clear/shrink/deallocate function

Example Reference:

// Using smart pointers
std::unique_ptr<std::vector<float>> my_vector = make_unique<std::vector<float>>(99);
my_vector.reset();

// Swap
std::vector<float> my_vector(99);
my_vector = std::vector<float>;
// Or alternatively
// std::vector<float>().swap(my_vector);
// std::swap(my_vector, std::vector<float>);

// Swap for cl::Buffer
cl::Buffer my_buf(context, CL_MEM_READ_WRITE, size);
my_buf = cl::Buffer();

// Clear and shrink
// Specific to std::vector
std::vector<float> my_vector(99);
my_vector.clear();
my_vector.shrink_to_fit();

Limits

#include <limits>
Reference
C++ has standard macros such as INT_MAX.
The limits header adds these limits for every type.

// Equivalent to FLT_MAX
std::numeric_limits<float>::max();

Utility

#include <utility>

std::move

Ref
Use std::move to move containers.

Algorithm

std::find

Reference

std::generate

cppreference
Allows you to fill a container using a function call

#include <random>
#include <iostream>
#include <algorithm>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    # Fill with integers in [0, 10]
    std::uniform_int_distribution<> dis(0, 10);

    std::vector<int> my_vec(10, 0);
    std::generate(my_vec.begin(), my_vec.end(), [&](){return dis(gen);});
  <br />
    for (int v : my_vec) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    return 0;
}

Numeric

std::iota

Reference
Fills an array or vector with increasing values. Can pass in a starting number.

std::vector<int> v(60);
std::iota(v.begin(), v.end(), 0);


std::accumulate

Adds up numbers. Can pass in a starting number.

std::vector<int> v(60);
std::iota(v.begin(), v.end(), 0);
std::accumulate(v.begin(), v.end(), 0);

Chrono

#include <chrono>
Lots of useful time stuff. Good for timing your code.

auto start = std::chrono::high_resolution_clock::now();
// do something
auto end = std::chrono::high_resolution_clock::now();
std::cout << "Time elapsed: " 
          << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
          << " ms" << std::endl;

Execution

#include <execution>
The execution header gives you tools for parallel execution (since C++17).
See execution_policy_tag.
C++17 Parallel Algorithms blog.
Nvidia Accelerating Standard C++ with GPUs Using stdpar

Parallel Sorting Example
std::sort(std::execution::par_unseq, sorted.begin(), sorted.end());
  • std::execution::seq sequential
  • std::execution::unseq vectorized only (C++20)
  • std::execution::par parallel
  • std::execution::par_unseq parallel and vectorized

Random

#include <random>
cppreference.com

std::random_device rd;  //Will be used to obtain a seed for the random number engine
std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
std::uniform_int_distribution<> dis(1, 6);
 
for (int n=0; n<10; ++n)
   //Use dis to transform the random unsigned int generated by gen into an int in [1, 6]
   std::cout << dis(gen) << ' ';
std::cout << '\n';

STL

STL is the Standard Template Library originally implemented in 1994 by Stepanov and Lee from HP.
STL consists of a general set of algorithms, containers, functions, and iterators.
Today, STL refers to those containers and algorithms which are now built into the standard library (std) of C++.

Simple Containers

std::pair

std::pair

Sequences

std::array

#include <array>
This wrapper around C-style arrays gives us size information and allows the array to be passed around by reference while keeping the array on the stack or in a struct. Unless you need stack allocation or allocation into a struct, you are should probably use a vector.

std::vector

#include <vector> https://en.cppreference.com/w/cpp/container/vector
This is a dynamically-allocated resizable array, known as an ArrayList in Java.

// Basics
vector my_vec;
// Vector with size 5
vector my_vec(5);
// Vector with size 5 initialized to 1
vector my_vec(5, 1);

// Length of vector
my_vec.size();

// Equivalent to size()==0
my_vec.empty();

// Equivalent to my_vec[0];
// Undefined on empty vectors
my_vec.front();

// Equivalent to my_vec[my_vec.size()-1];
// Undefined on empty vectors
my_vec.back();

Note that vector<bool> is a special case of bit-packed booleans instead of an array of bools. You should use vector<char> instead if your code relies on it being continguous.

std::span

#include <span>
https://en.cppreference.com/w/cpp/container/span
This is view of some contiguous amount of memory. If the size is static, this is equivalent to a single pointer, otherwise is it equivalent to two pointers (i.e. begin and end). If you use this as the parameter to your function, it will accept both arrays and vectors. Additionaly, there is a subspan function so you don't need to pass around indices or pointers to get subvectors.

std::deque

Double-ended queue

std::list

This is a doubly linked list. You can delete elements from the middle of the list if you know have an iterator.

list<int> m_list;

list<int>::iterator m_it = m_list.insert(5);

// Remove the element
m_list.erase(m_it);

Container adaptors

std::queue

Reference

std::queue<int> my_queue;

my_queue.push(a);
auto val = my_queue.front();
my_queue.pop(); // returns void

std::stack

cppreference

std::stack<char> my_stack;

// Push to stack
// You can also use emplace
// Returns void
my_stack.push('a');

// Peek
// Always make sure stack is not empty
char top = my_stack.top('a');

// Pop
// Note: returns void
// Always make sure stack is not empty
my_stack.pop();

std::priority_queue

This is a min/max heap.

Associative Containers

Also known as maps or associative arrays.

std::set

reference
#include<set>
This is a binary tree (likely red-black tree). You can assume \(\displaystyle O(\log n)\) operations.


std::map

reference
#include<map>
This is a binary tree (likely red-black tree). You can assume \(\displaystyle O(\log n)\) operations.

std::unordered_set

reference
#include <unordered_set>
This is a hashset. You can assume operations are \(\displaystyle O(1)\) on average and \(\displaystyle O(N)\) worst case.

std::unordered_set<int> my_set;
// Add
my_set.insert(5);
// Check contains
my_set.find(5) != my_set.end(); // Before C++20
my_set.contains(5); // C++20
// Remove
my_set.erase(5);

std::unordered_map

reference
#include<unordered_map>
This is a hashmap. You can assume operations are \(\displaystyle O(1)\) on average and \(\displaystyle O(N)\) worst case.

std::unordered_map<int, std::string> my_map;
my_map.insert(5, "hey");
my_map.find(5) != my_map.end();
my_map.contains(5); // C++20
Custom Keys

How to use a rational number as a key in C++

struct Fraction
{
    int num;
    int den;

    bool operator==(const Fraction &other) const { 
        return num*other.den == den * other.num;
    }

    Fraction(int a, int b) : num(a), den(b) {}
};

Functional Programming

https://medium.com/swlh/doing-it-the-functional-way-in-c-5c392bbdd46a

Many of these can be parallelized with execution policies such as std::execution::par and std::execution::par_unseq.

Most of these require C++20.

Map
  • std::for_each
  • std::transform
Reduce/Fold
Filter
  • std::copy_if
  • std::remove_if
  • std::find_if

Programming Styles

Modern C++

List of resources

  • Use RAII principles.
    • I.e. each object should manage it's own memory rather than the caller having to manage it.
    • You should never use `malloc` and `free` unless interfacing with C libraries.
  • Use smart pointers instead of new and delete.
    • Namely, std::unique_ptr, std::shared_ptr, and std::vector.
  • Use clang-format.
Resources

RAII

cppreference raii
Resource Acquisition Is Initialization - binds the life cycle of a resource to the lifetime of an object.
For instance, the resource for a vector is an allocated amount of memory. Once the vector is destroyed and the destructor called, the resource is released.
In general, each RAII object should have all of the following:

  • Constructor acquiring resources
  • Copy Constructor
  • Assignment operator
  • Destructor releasing resources
  • Swap function (for std::swap)
  • Move constructor (since C++11, for std::move)
Example RAII Class

Copied from stack overflow

#include <algorithm> // std::copy
#include <cstddef> // std::size_t

class dumb_array
{
public:
    // (default) constructor
    dumb_array(std::size_t size = 0)
        : mSize(size),
          mArray(mSize ? new int[mSize]() : nullptr)
    {
    }

    // copy-constructor
    dumb_array(const dumb_array& other)
        : mSize(other.mSize),
          mArray(mSize ? new int[mSize] : nullptr),
    {
        // note that this is non-throwing, because of the data
        // types being used; more attention to detail with regards
        // to exceptions must be given in a more general case, however
        std::copy(other.mArray, other.mArray + mSize, mArray);
    }

    // destructor
    ~dumb_array()
    {
        delete [] mArray;
    }

    friend void swap(dumb_array& first, dumb_array& second) // nothrow
    {
        // enable ADL (not necessary in our case, but good practice)
        using std::swap;

        // by swapping the members of two objects,
        // the two objects are effectively swapped
        swap(first.mSize, second.mSize);
        swap(first.mArray, second.mArray);
    }

    dumb_array& operator=(dumb_array other) // (1)
    {
        swap(*this, other); // (2)

        return *this;
    }

    dumb_array(dumb_array&& other) noexcept ††
        : dumb_array() // initialize via default constructor, C++11 only
    {
        swap(*this, other);
    }

private:
    std::size_t mSize;
    int* mArray;
};

Useful Libraries

A list of useful libraries

Boost

A set of popular C++ libraries. Most are header-only.

cxxopts

Link
A header-only C++ argument parser.
Note that if you already use Boost, you can use Boost::Program_options instead.

Eigen

A header-only C++ linear algebra library.

References