Complete Table of Contents

Front Matter

Legal and foreward

• Copyright Notice
• GNU Free Documentation License
  • 0. PREAMBLE
  • 1. APPLICABILITY AND DEFINITIONS
  • 2. VERBATIM COPYING
  • 3. COPYING IN QUANTITY
  • 4. MODIFICATIONS
  • 5. COMBINING DOCUMENTS
  • 6. COLLECTIONS OF DOCUMENTS
  • 7. AGGREGATION WITH INDEPENDENT WORKS
  • 8. TRANSLATION
  • 9. TERMINATION
  • 10. FUTURE REVISIONS OF THIS LICENSE
  • 11. RELICENSING
    • ADDENDUM: How to use this License for your documents
• Foreword
• Preface
  • Overview
  • How to Contribute

Preliminaries

• C and C++ concepts
  • Hello, world!
    • Built-in types, variables and operations
    • User-defined types
    • File input and output
    • Statements and branching
    • Fixing errors in code
  • Types
    • Fundamental representations
      • Sign and magnitude
      • One’s complement
      • Two’s complement
      • Overflow
        • Preventing overflow errors
    • Compound types
      • Array types
      • Reference types
    • The type std::size_t
    • Displaying numbers
  • Random numbers
  • Code comments
    • Comments in assignments
    • Commenting “anti-patterns”
    • Commenting Dos and Don’ts
  • What you don’t need to know (yet)
  • Self Check
• Mathematical Background
  • Sets and Relations
    • Set Notation
    • Relations
    • Equivalence Relations
    • Partial Orders
  • Selected functions
  • Modulus operator
  • Permutations
  • Logarithms
  • Summations
    • Summation facts
    • Approximating Sums
  • Estimation
  • Pseudocode conventions and definitions
• Algorithm Analysis
  • Problems, Algorithms, and Programs
    • Problems
    • Algorithms
    • Programs
    • Summary
  • Comparing Algorithms
    • Basic operations and input size
    • Growth Rates
  • Best, worst, and average cases
  • Asymptotic Analysis and Upper Bounds
    • Big-O Notation
    • Using summation facts
    • Pitfall: Confusing upper bound and worst case
  • Lower Bounds
  • Theta Notation
    • Classifying Functions
    • Pitfall: Confusing lower bound and best case

Main Body

• 1. Development tools
  • 1.1. Git setup
    • 1.1.1. Step 1: Install Git
    • 1.1.2. Step 2: Setup your username and email address in Git
    • 1.1.3. Step 3: Setup authentication
      • 1.1.3.1. Creating an SSH key
      • 1.1.3.2. Using an SSH key on the command line
      • 1.1.3.3. Creating a GitHub personal access token
      • 1.1.3.4. Using a token on the command line
  • 1.2. Tutorial: Using Git
    • 1.2.1. Initialize a git repository
    • 1.2.2. Editing files
    • 1.2.3. Renaming files
    • 1.2.4. Adding and removing files
    • 1.2.5. Recovering files from the repository
  • 1.3. Building software
    • 1.3.1. How to access the Mesa Server
    • 1.3.2. For the impatient: A quick summary
  • 1.4. Compiling code on your local computer
    • 1.4.1. Compiling using the CISC187 Docker image
    • 1.4.2. Compiling with Visual Studio
    • 1.4.3. Compiling with Code Blocks
    • 1.4.4. Compiling with Xcode
    • 1.4.5. Compiling on Linux
    • 1.4.6. Which option should I choose?
  • 1.5. Introducing Gnu/Linux
    • 1.5.1. The command line
    • 1.5.2. Absolute vs relative paths
    • 1.5.3. Basic commands
  • 1.6. Introducing the vim editor
    • 1.6.1. Modes
    • 1.6.2. Motions
      • 1.6.2.1. Word motions
      • 1.6.2.2. Other motions
    • 1.6.3. Selections
    • 1.6.4. Command & motion examples
    • 1.6.5. Creating ‘Hello World’ using vim
    • 1.6.6. Navigating to make errors
  • 1.7. Command-line compiling
    • 1.7.1. The C++ compiler
    • 1.7.2. The make utility
    • 1.7.3. Running your programs
  • 1.8. Debugging
    • 1.8.1. Syntax errors
      • 1.8.1.1. I can’t get my program to compile no matter what I do.
    • 1.8.2. Link errors
    • 1.8.3. Runtime errors
      • 1.8.3.1. My program does absolutely nothing.
      • 1.8.3.2. My program hangs.
      • 1.8.3.3. Infinite loops
      • 1.8.3.4. Infinite recursion
    • 1.8.4. Semantic errors
    • 1.8.5. General debugging tips
      • 1.8.5.1. My program doesn’t work
      • 1.8.5.2. I’ve got a big hairy expression and it doesn’t do what I expect
      • 1.8.5.3. I’ve got a function that doesn’t return what I expect
      • 1.8.5.4. Assertions
    • 1.8.6. Debugging tools
      • 1.8.6.1. The GNU debugger (gdb)
        • 1.8.6.1.1. Useful gdb commands
• 2. String and Vector
  • 2.1. Using string and vector
  • 2.2. String abstractions in C
  • 2.3. Working with C strings
    • 2.3.1. Change character case
    • 2.3.2. Copying and comparing C strings
  • 2.4. The string class
    • 2.4.1. Getting information out of a string
    • 2.4.2. Convert a byte string to a number
    • 2.4.3. Converting a std::string to a C string
  • 2.5. Analysis of String Operators
  • 2.6. The vector class
    • 2.6.1. Adding data to a vector
    • 2.6.2. Vector capacity
  • 2.7. Analysis of Vector Operators
• 3. Introduction to functions
  • 3.1. Introduction to functions
    • 3.1.1. Function declarations and compilation units
    • 3.1.2. The call stack
  • 3.2. Passing parameters
  • 3.3. The main function
    • 3.3.1. Parsing command line arguments
  • 3.4. Scope
    • 3.4.1. Local variables
  • 3.5. Namespaces
    • 3.5.1. Prefer using declarations to using namespace std
  • 3.6. Keyword: const
    • 3.6.1. Prefer const to #define
      • 3.6.1.1. Function-like macros using #define
    • 3.6.2. Keyword: constexpr
    • 3.6.3. Guidelines for now
  • 3.7. Keyword: auto
  • 3.8. Error handling
    • 3.8.1. Handling multiple errors at once
  • 3.9. Exception handling
    • 3.9.1. Standard exceptions
    • 3.9.2. Using exceptions
    • 3.9.3. Exceptions and I/O streams
  • 3.10. Static functions and variables
    • 3.10.1. Anonymous namespaces
• 4. Function overloads and templates
  • 4.1. Function overloads
    • 4.1.1. Overloading anti-patterns
  • 4.2. Operator overloads
    • 4.2.1. Relational operators
    • 4.2.2. Insertion and extraction overloads
  • 4.3. Function templates
    • 4.3.1. Using templated functions
    • 4.3.2. Multiple template parameters
    • 4.3.3. Non-generic template parameters
  • 4.4. Concepts overview
    • 4.4.1. Concepts
    • 4.4.2. Keyword: requires
  • 4.5. Trailing return types
    • 4.5.1. Keyword: decltype
    • 4.5.2. Trailing return type syntax
  • 4.6. General function writing guidelines
    • 4.6.1. When to write a function
    • 4.6.2. Example: number guessing
• 5. Pointers
  • 5.1. Pointers
    • 5.1.1. Declaring pointers
  • 5.2. Using pointers
  • 5.3. Comparison with references
    • 5.3.1. Function passing semantics
  • 5.4. Pointers and arrays
    • 5.4.1. Array indexing pitfalls
    • 5.4.2. Arrays of type char
  • 5.5. Pointers to pointers
  • 5.6. Other pointer characteristics
    • 5.6.1. Constant pointers
    • 5.6.2. The nullptr type
    • 5.6.3. void pointers
  • 5.7. Free store pointers
    • 5.7.1. STL memory management
      • 5.7.1.1. Class std::unique_ptr
  • 5.8. Pointer debugging
    • 5.8.1. Valgrind
  • 5.9. Pointers to functions
    • 5.9.1. Example: Caesar ciphers
  • 5.10. Lambda expressions
    • 5.10.1. Assigning a lambda to a variable
    • 5.10.2. Trailing return types in lambda expressions
  • 5.11. The std::function template
• 6. Recursion
  • 6.1. What is Recursion?
    • 6.1.1. Accumulating a sum
  • 6.2. Properties of recursive functions
  • 6.3. Example: Converting an Integer to a String
  • 6.4. The Binary Tree ADT
    • 6.4.1. Binary tree traversal
      • 6.4.1.1. Preorder traversal
      • 6.4.1.2. Postorder traversal
      • 6.4.1.3. Inorder traversal
      • 6.4.1.4. Level order traversal
• 7. Sorting
  • 7.1. Bubble sort
  • 7.2. Selection sort
  • 7.3. Insertion sort
  • 7.4. Costs of Exchange Sorting
  • 7.5. Shell sort
  • 7.6. Merge sort
  • 7.7. Quick sort
  • 7.8. Heap sort
  • 7.9. Radix sort
    • 7.9.1. Array-based Radix Sort
    • 7.9.2. Radix Sort Analysis
  • 7.10. Summary of sorting algorithms
• 8. Introduction to classes
  • 8.1. Classes
    • 8.1.1. The basic structure of a class
  • 8.2. Constructors
    • 8.2.1. Object life cycle
    • 8.2.2. Class invariants
  • 8.3. Pointers to objects
  • 8.4. ‘this’ pointer
  • 8.5. Interfaces and implementation
    • 8.5.1. File extensions
  • 8.6. const member functions
  • 8.7. Abstraction
    • 8.7.1. Class abstractions
  • 8.8. Enumerated types
    • 8.8.1. Unscoped enumerations
    • 8.8.2. Scoped enumerations
• 9. Class constructors and overloads
  • 9.1. Constructors
    • 9.1.1. Initialization syntax
    • 9.1.2. Overloaded constructors
    • 9.1.3. Telescoping constructors
  • 9.2. Static members
  • 9.3. Operator overloads
    • 9.3.1. Basic overloading guidelines
    • 9.3.2. Assignment operator
    • 9.3.3. Insertion and extraction operators
    • 9.3.4. Function call operator
    • 9.3.5. Comparison operators
    • 9.3.6. Binary arithmetic operators
    • 9.3.7. Increment and decrement operators
    • 9.3.8. Conversion operators
  • 9.4. Friend vs non-friend functions
• 10. Class design
  • 10.1. Object-oriented concepts
    • 10.1.1. Object-oriented programming principles
    • 10.1.2. Encapsulation
    • 10.1.3. Inheritance
    • 10.1.4. Polymorphism
    • 10.1.5. Abstraction
  • 10.2. Unified modeling language
    • 10.2.1. Static and Dynamic diagrams
    • 10.2.2. Class diagrams
  • 10.3. Composition
  • 10.4. Inheritance
    • 10.4.1. Base class references and pointers
    • 10.4.2. When to use inheritance
    • 10.4.3. Private inheritance
    • 10.4.4. Non-virtual base class functions
    • 10.4.5. Multiple inheritance
    • 10.4.6. Design problems
  • 10.5. Abstract base classes
    • 10.5.1. Interfaces
    • 10.5.2. The final specifier
  • 10.6. Design patterns
    • 10.6.1. Fixing an inheritance problem
  • 10.7. Strategy pattern
  • 10.8. Chain of Responsibility pattern
• 11. Class templates and std::array
  • 11.1. Class templates
    • 11.1.1. Value class templates
    • 11.1.2. Friend or non-friend?
  • 11.2. Overloading operator[]
    • 11.2.1. Multi-dimension array access
  • 11.3. Container classes
    • 11.3.1. Initializer list constructors
  • 11.4. Standard Template Library Containers
    • 11.4.1. Ordered and sorted containers
  • 11.5. The std::array class
• 12. Memory management and std::vector
  • 12.1. The std::vector class
    • 12.1.1. Passing vectors to C functions
  • 12.2. Copying objects
    • 12.2.1. Copy assignment
  • 12.3. Lvalues, rvalues, and references
  • 12.4. Moving memory
    • 12.4.1. Move constructors and move assignment
  • 12.5. Allocators
    • 12.5.1. Using std::allocator_traits
  • 12.6. constexpr classes
• 13. Stacks and Queues
  • 13.1. The Adapter pattern
  • 13.2. The stack class
    • 13.2.1. Postfix Notation
  • 13.3. The queue class
    • 13.3.1. Circular queues
  • 13.4. The deque class
• 14. Linked lists
  • 14.1. The list class
  • 14.2. Analysis of list operators
  • 14.3. std::forward_list
  • 14.4. Iterable ADT’s
  • 14.5. Iterator pattern
  • 14.6. Basic iterator operations
    • 14.6.1. Iterator categories
  • 14.7. Using iterators
    • 14.7.1. Limits of Range-based for loops
    • 14.7.2. Container functions that require iterators
• 15. Trees and associative data structures
  • 15.1. Tree ADT concepts
    • 15.1.1. The tree ADT
  • 15.2. Binary Search Trees
    • 15.2.1. The Binary Search Tree ADT
    • 15.2.2. Searching binary trees
    • 15.2.3. Inserting into binary trees
    • 15.2.4. Erasing binary tree nodes
      • 15.2.4.1. Removing a leaf node
      • 15.2.4.2. Removing a non-leaf node with a null child
      • 15.2.4.3. Removing a non-leaf node with a two children
  • 15.3. Binary Search Tree iterators
    • 15.3.1. BST iterator begin() and end()
    • 15.3.2. BST iterator operator++()
      • 15.3.2.1. BST iterator using parent pointers
    • 15.3.3. Implementing BST iterators
      • 15.3.3.1. Implementing operator++()
  • 15.4. Using parent pointers
  • 15.5. Priority queues
    • 15.5.1. Heaps
    • 15.5.2. Percolate up
    • 15.5.3. Percolate down
  • 15.6. The set class
    • 15.6.1. Variations on std::set
  • 15.7. The map class
    • 15.7.1. Selected map functions
    • 15.7.2. Map structure
    • 15.7.3. Variations on std::map
• 16. Hash Tables
  • 16.1. Hashing concepts
  • 16.2. Hash functions
    • 16.2.1. Integer hashes
    • 16.2.2. String hashes
    • 16.2.3. Hashing user defined types
  • 16.3. Resolving collisions
  • 16.4. Open hashing
  • 16.5. Analysis of separate chaining
  • 16.6. Closed hashing
    • 16.6.1. Choosing the next slot
    • 16.6.2. Analysis of closed hashing
  • 16.7. Analysis of hash tables
• 17. Algorithms
  • 17.1. Background
    • 17.1.1. STL Algorithms at a glance
    • 17.1.2. STL algorithms and loops
  • 17.2. Basic Model
    • 17.2.1. Basic Model in Action: find()
  • 17.3. Refactoring to Algorithms
    • 17.3.1. Removing a final assumption
  • 17.4. std::copy and Iterator Adapters
• Glossary

Back Matter

• Frequently asked questions (FAQ)
  • Why not use an IDE?
  • What language should I learn?
    • What languages did I learn first?
  • Should I learn C first?
  • What other good C++ resources are out there?
    • Coding challenges and puzzles
    • Suggested reading
  • What if I need help in this class right now?
    • Videos
    • Other resources
  • What major should I pick?
  • Do I need to know math?
• ASCII Character Set

• Search Page

• Glossary

• Index