C++ Review: List of Concepts Covered (since Test 2)

Arrays: Searching and Sorting

Searching

• Linear Search
  • The most obvious and intuitive search mechanism
  • Looks through array elements one by one until the item is located
  • takes longer than some specialized search techniques
• Binary Search
  • Depends on array being maintained in some sorted order
  • Looks at "middle" element, and decide which "side" of the array the element being searched for would have to be in
  • On each comparison, cuts number of possibilities in half
  • Runs much faster than linear search

Sorting

• Bubble Sort
  • Compares side-by-side elements. If out of order, swap them
  • Uses nested loops
  • Each run through inner loop "bubbles" one element to the end, its final position
  • Outer loop must run size-1 times
• Selection Sort
  • Also uses nested loops
  • Run through inner loop "selects" the largest (or smallest) element of the remaining items (i.e. the ones that are not yet in position), and swaps it with the end element
  • Outer loop must run size-1 times

Classes and Objects

Object

• Name
• member data (attributes, or the state of the object)
• member functions (behavior)
• Know how to declare an object, how to access internal data, how to call member functions for an object

Class

• a blueprint for building objects
• a programmer-defined type

DDU Design Model

• Declare -- Declaration of class in header file
• Define -- Definition of class members in implementation file
• Use -- Usage of class by building objects

Building Classes

• Separating Interface from implementation
• access levels: public and private
• Understand the guidelines of using private data and creating an interface of public functions
• Constructor:
  • same name as the class, no return type
  • automatically invoked upon object creation
  • can have parameters
  • "default constructor" = no parameters
• Accessor functions (usually get functions)
• Mutator functions (usually set functions)
• Maintaining the valid state of an object
  • Using the constructor appropriately
  • Validation of outside input (in appropriate places)
• Syntax issues:
  • scope resolution operator (in class definition file)
  • dot operator (when calling members of an object)

Compiling Multiple-File Projects

Building a program

• Compile stage
  • Syntax checking
  • Checking "declare before use"
  • Matching function calls to prototypes
  • Type checking on variable usage
  • Translation to object code
• Linking Stage
  • Putting 1 or more object code files together
  • Matches function calls to their definitions
  • Usually result is an executable (but could be other target type, like a DLL)
• General
  • Don't #include the .cpp files!
  • #include header files to satisfy "declare before use"
  • Libraries sometimes distributed in pre-compiled format (meaning programmer only has header file and "object code", not full implementation code)