C++ STL Containers for Relationships

Lecture 9 Overview

• Custom Comparison Operators will be covered
• Templates
• The Standard Template Library (STL)
• STL Iterators
• STL Algorithms (sort, etc.)

Generic Programming

• Generic proramming occurs when a function or class is able to process many different types of data
• A generic sorting function can sort an array holding any type of value
• A generic linked list class can therefore hold any type of variable
• Once a generic function or class has been defined, it can be reused quickly to solve problems
• This technique is used in almost every C++ program therefore improves development speed, i.e.. search engines, video games, etc.

Allowing Generic Comparisons

• Default C++ allows comparison of integers
• It can be useful to compare Objects too, e.g. Circles and Dogs
• Implementation requires Custom Operators
• The way two dogs are compared by weight, is different to how two circles may be compared by radius

Custom Comparison Operators

• Comparison operators must return a Boolean Value
• Boolean value will be set appropriately for the function implementation, based on true of false values
• A const specifier must be used, otherwise the function will not work when comparing const objects
• When operators are defined inside the class, the function has a single "other" parameter, similarly to a copy constructor
• "other" refers to the value to the right of the operator
• When the operator is placed outside of the class, it can only the public methods from the class

Writing Generic Functions

• Using templates enables writing of generic functions
• Before templates it was required to define a single function for each variable type, e.g. SwapCircle, SwapDog, etc.

Templates

• Templates enable one function to work for any data type

template <typename T>
void swap(T &a, T &b)
{
    T temp;
    temp = a;
    a = b;
    b = temp;
}

• or alternative Syntax:

template <class T>
void swap(T &a, T &b)

Template Usage

• Write templated functions in a header file
• Then include the header file in all CPP files using the function
• It is then possible to implement the templated function in the header file, and not just the prototype

Using Templates

• Using templates is a time-saving/bug-reducing/source-simplifying technique
• Number of functions does not effect compiled program or code size

Function Template Constraints

• You must use the templated data type (e.g. Data) to define the type of at least one formal parameter; otherwise, there will be an error
• If a function template has two or more templated parameters with the same type (e.g. Data), you must both pass the same type of variable/value

Hairy Template Example

• operator defined for Dogs

• operator is also defined for integers.

• Function requirements must be set for templated functions
• C++ requires that all values passed in support that operator
• If you use such a function with a user-defined class you mus define the operator for that class!

Multi-type Templates

• You can use multiple template types in a function

template <typename T, typename U>
void passTwoTypes(const T& first, const U& second) 
{
    std::cout << " First: " << first << " Second: " << second <<std::endl;
}

Writing Generic Classes

• Templates facilitate using generic classes, stack or queue classes for example
• The prefix must be used, i.e.. template before the class definition itself
• For example, it is not required to update every 'int' to Item, as int can be a counter variable

Templated Class in Externally-defined Member Function

• Add prefix template before the class definition itself
• Add prefix template before each function definition outside the class
• Types will require updating to using a templated type
• Place the postfix <XXX> between the class name and the :: in all function defs.

Template Classes

• Template classes are very useful when building container objects like linked lists

STL Library

• STL is a collection fo pre-written, tested classes provided by the authors of C++
• Classes that are built using templates, can be used with many different data types
• Usage of these classes saves hours of programming
• Examples include the Stack and Queue classes

STL: Container Classes

• Classes are called "container" classes because they hold groups of items

Cool STL Class #1: Vector

• STL vector has some of the same properties as arrays
• STL vector does not have a fixed size
• Vectors grow and shrink automatically when adding or removing items
• Program must "#include " to use vectors

    vector<string> strs;
    vector<int> nums;

• If using namespace std is excluded:

    std::vector<std::string> strs;

Creating Vectors

• You can add or remove items to/from existing vectors
• Push_back is used to add a new item to the end

    vector<string> strs;
        strs.push_back("Carey");
        strs.push_back("Scott");

• The brackets can be used to change an existing item
• However cannot be used to add a new item

Reading and Changing Vector Items

• You can use the front or back methods for read to or write the first or last elements
• Once an item has been removed, the slot cannot be accessed with brackets

Removing Vector Items

• An item can be removed from the back via "pop_back" command
• This shrinks the vector

Vector Details

• You can view the size and ensure there are values through included functions
• Vectors are implented internally dynamically allocated arrays
• During array full and new item addition the vector object will allocate a new array as double the size of the original
• It will copy all items rom the old array and delete the old array

Cool STL Class #2: List

• STL list enables creation of a doubly-linked list
• List contains functions such as, "push_back", "pop_back", "front", "back", "size" and "empty" methods
• But also includes push_front and pop_front methods
• These methods allow items to be added or removed from the front of the list

List Usage

• Lists do not have brackets to access list elements

Iterating Items

• How can we iterate through elements of STL

    for (int j=0; j<poof.size(); j++)
        cout << poof[j];

• Other than the vector class this form of iteration does not work

Iterators

• Iterator variable enumerates the contents of a container
• Iterator variable works similar to a pointer variable
• An iterator works exclusively with containers

Iterator Variable

• Typically, starting with pointing an iterator to an item in the container
• Can be implemented through increment/decrement
• The iterator allows read/write functionality
• Create with, e.g..

vector<int>::iterator it;

• And must start with:

it = myVec.begin();

Iterator Details

• Can move your iterator down or back through increment or decrement of pointers
• There is addition of function "end", which denotes, what happens at end of the function

Algorithm Functions

• Find function can be applied to STL containers and arrays

Container Template Issues

• You have to make the iterator a const iterator

const list<string> & nerds

list<string>::const_itenator it

• Otherwise you can't use the STL container functionality

Iterator Object Details

• An iterator is an Object
• What that object does and contains
  • What element is it points to
  • How to find the next element in the container
    • This includes direction
  • How to find the previous element in the container - This includes direction

Alternative ways of looping

• C++ 11 now has easier to read way of iterating data

Other Important STL concepts

• Maps and other types of containers
• Use for finding and storing data, with search algorithm

Cool STL Class #3: Map

• Maps quickly look up items to find an associated integer "value"
• You can associate a string "Key" with set value

Map Usage

• Names can be stored in string variables with phone numbers in integers
  • Each Map can be associated with either direction

map<string, int> name2Fone; // String to Int
map<int, string> fones2Names; //Int to String

• Requires 2 maps

More Map Details

• Map always orders from First to Second
• Maps store this by pairing similar structs

Cool STL Class #4: Set

• Set always keeps track of unique values in a set
• Duplicates are ignored

a.erase(2)

Removes "2" value

Additional Cool Class points:

• You can find a previously added association
• This returns a map You can define special classes or structs to hold STL classes
• You cannot call erase, if you use the original object.

Algorithm

• STL is a common algorithm for different types of data
• This algorithm works to search STL containers and arrays for a value
• intersection of different data sets
• sorting vectors and list elements for use and analysis

STL Gotchas

• Add new items, with caution to validity, if modified
• You can run the danger of invalidity of pointer, this must be taken in consideration and the code updated

More STL Gotchas

• There are also dangers of deleting data incorrectly.
• When deleting iterator with set container
• Can avoid with returned iterator to the times following eraser

Deleting Items in Loop

• You can use the erase() method to return an iterator

STL Algorithms

• The STL contains extra functions that work with data find() function searches STL containers and arrays for value set_intersection() computes the intersection of two sorted sets/lists/arrays of data sort() sorts arrays/vectors/lists

Inline Functions

Template Exercise

• How to convert the Stack class to hold any type of data
• How to create a stack of dogs

Note: There is the find_if function to find the item that best suits requirements.

Explore suitable C++ STL containers for managing relationships such as one-to-many between people and courses. Learn about requirements for using set with custom objects and the benefits of STL containers over arrays. Understand how to efficiently use maps and vectors.