C++ Templates (Pt.2)

C. Papachristos

Robotic Workers Lab

University of Nevada, Reno

CS-202

Course , Projects , Labs:

​

​

​

​

Your 10^th Project will be announced today Thursday 4/23.

9^th Project Deadline was this Wednesday 4/22.

• NO Project accepted past the 24-hrs delayed extension (@ 20% grade penalty).
• Send what you have in time!

​

Course Week

CS-202 C. Papachristos

Today’s Topics

CS-202 C. Papachristos

Template Specialization

• Specialization vs Overloading.

​

Class Template friend(s)

​

Template(s) and Names

• Dependent-Qualified Type names – Keyword typename Disambiguator.
• Explicitly-Qualified names – Keyword template Disambiguator.

​

The Standard Template Library

• Containers & Iterators.

std::vector

std::list , std::forward_list

std::set , std:: multiset

std::pair

std::set , std::multiset

std::map , std::multimap

Template(s)

CS-202 C. Papachristos

Function Overloads and Templates

​

A (misbehaving) Function Template

• Even though the behavior is well-defined, the function does not performs as intended.

​

char const * s1 = "abcd";

char const * s2 = "XYZW";

cout << Max( s1, s2 );

​

The compiler generates:

char const * Max (char const * const & a, char const * const & b){� if ( a < b ) � return b;

else � return a;�}

Will try to sort them by their Memory Address.

template < typename T >

T Max(T const & v1, T const & v2){

if (v1 < v2) return v2;

else return v1;

};

Remember: As we have mentioned on how to backwards-read these:�char const * “Pointer to Constant Character”

const char * “Pointer to Character that is Constant”

(They are the same const-qualified Pointer-Type declarations)

(Possible) Output: XYZW

Template(s)

CS-202 C. Papachristos

Function Overloads and Templates

​

Function Overloads vs Function Templates.

• Create an overloaded version specifically handling char * variables,

The compiler will “prefer” this instead of the Function Template version.

​

char const * Max(char const * a, char const * b)

{

if (strcmp(a, b) < 0)

return b;

else

return a;

}

​

Function Overload�has precedence over Function Template.

Template(s)

CS-202 C. Papachristos

Function Overloads and Templates

​

Function Overloads vs Function Templates.

• Note: Careful with Overloading and Template Type Deduction & cv-qualifiers !

​

char const * s1 = "abcd";

char const * s2 = "XYZW";

cout << Max( s1, s2 );

​

template < typename T >

T Max(T const & v1, T const & v2){

if (v1 < v2) return v2;

else return v1;

};

char * Max(char * a, char * b) {

if (strcmp(a, b) < 0)

return b;

else

return a;

}

This Overload is NOT a match!

char const * Max (char const * const & a,

char const * const & b) {� if ( a < b ) � return b;

else � return a;�}

So the compiler will still resort to the Template !

Template(s)

CS-202 C. Papachristos

The keyword template

​

Function template(s) Specialization.

• Making distinct family members�for specific Types.

​

​

Function Template Specialization.

​

Syntax A) – Implicit Type Deduction:

template < >

return-type TplFunc(params){ … }

​

Syntax B) – Explicit Type Deduction:

template < >

return-type TplFunc<Specific-Types>(params){ … }

template < typename T >

void Swap(T & v1, T & v2)

{

T temp=v1; v1=v2; v2-temp;

};

template < >

void Swap(char & v1, char & v2)

{

if ((v1…a-Z) && (v2…a-Z)){

char temp=v1;

v1=v2; v2-temp;

}

};

char–Specialized� Function Swap�Template

• Handles specific case of char value swapping.
• Implicit Type Deduction of T:=char by the compiler.

Function

Swap

Template

Template(s)

CS-202 C. Papachristos

The keyword template

​

Function template(s) Specialization.

• Making distinct family members�for specific Types.

​

​

Partial Specialization → Refers to a modifier of T.

​

​

Syntax:

template < typename T >

T-mod-return TplFunc(T-mod-params)�{ … }

​

template < typename T >

T Max(T const & v1,

T const & v2){

return (v1 < v2)? v2:v1;

};

​

template < typename T >

T * Max(T * const & v1,

T * const & v2){

return (*v1 < *v2)? v2:v1;

};

Pointer–Specialized� Function Max�Template

• Dereferences T *, otherwise the expression v1<v2 evaluates relationship of memory addresses.
• Pointer-Specialized version applies T-reliant operator< on objects (has to be defined for T).

Note: Formally Function Templates are not Partially Specializing, they Overload.

Function

Max

Template

Template(s)

CS-202 C. Papachristos

The keyword template

​

Function template(s) Specialization.

• Utility by-Example:

const char * s1 = "abcd";

const char * s2 = "XYZW";

cout << Max(s1, s2);

template < typename T >

T Max(const T & v1,

const T & v2){

return (v1 < v2)? v2:v1;

};

​

char const * Max(char const * const & v1,

char const * const & v2)

{

return (v1 < v2)? v2:v1;

};

Compiler-made

Direct Template�use with char *

• Sorts them by the highest memory address.

Function

Max

Template

Function Instantiation from Template

Template(s)

CS-202 C. Papachristos

The keyword template

​

Function template(s) Specialization.

• Utility by-Example:

const char * s1 = "abcd";

const char * s2 = "XYZW";

cout << Max(s1, s2);

Note:

Partial Specialization for Pointer-modifier�of T is necessary, otherwise the Explicit�Specialization will not find an appropriate function definition.

template < typename T >

T Max(T const & v1,T const & v2){

return (v1 < v2) ? v2:v1;

};

template < typename T >

T const * Max(T const * const & v1,

T const * const & v2)

{

return (*v1 < *v2) ? v2:v1;

};

const-Pointer

Specialized� Function Max�Template

template < >

char const * Max(char const * const & v1,

char const * const & v2)

{

int res = strcmp(v1,v2);

return !res ? NULL : (res<0?v1:v2);

};

char *–Specialized� Function Max�Template

• operator< is not defined to do what we want for C-strings,�hence we specialize function for char const *-handling�with strcmp.

Function

Max

Template

Template(s)

CS-202 C. Papachristos

The keyword template

​

Function template(s) Specialization.

• Utility by-Example:

const char * s1 = "abcd";

const char * s2 = "XYZW";

cout << Max(s1, s2);

char const * Max(char const * v1,

char const * v2)

{

return strcmp(v1,v2) ? v2:v1;

};

Simpler:�char const *–Overloaded Function Max

• Function Overloading is simpler.
• Compiler will always give Overloaded functions precedence over any Template.
• If Overloading is possible, use it.
• If you have to, then use Specialization. Why would I ? �a) Somewhere/someone explicitly calls a Templated Function version, e.g. Max<char const *>(s1, s2);�so the compiler is forced to use the Templated version.�b) You got mixed up in Template Metaprogramming…

template < typename T >

T Max(T const & v1,T const & v2){

return (v1 < v2) ? v2:v1;

};

Function

Max

Template

Template(s)

CS-202 C. Papachristos

The keyword template

​

Function template(s) Specialization (Advanced)

• Compiler rules - Specialization semantics:

​

A non Explicitly-Templated call of a function.

​

​

1. If an Overloaded function definition matches the call, it will have precedence:

void func(int *);

b) If no such match is found, Base-Templates (ones with Type) are queried, and the “most specialized” will be used:

template<typename T> (a) A Base-Template

void func( T ){ … }

​

template<typename T> (b) A second Base-Template,

void func( T * ){ … } (Partially-Specializes/) Overloads (a)

​

template <> (c) Explicit Specialization of (b)

void func(int *){ … }

int * int_Pt;

func( int_Pt );

template<typename T> (a) A Base-Template

void func( T ){ … }

​

template <> (c) Explicit Specialization of (a)

void func(int *){ … }

​

template<typename T> (b) A second Base-Template,

void func( T * ){ … } (Partially-Specializes/) Overloads (a)

The more specialized (the one that gets called).

Compiler will perform: 1^st Overload Resolution

2^nd Specialization Lookup

Template(s)

CS-202 C. Papachristos

The keyword template

​

Class template(s) Specialization.

• Making distinct family members�for specific Types.

​

​

Class Template Specialization.

​

Syntax:

template < >

class TplClass < special-type >�{ … }

​

template < typename T >

class Buffer {

public:

Buffer(); …

private:

T m_array[ARRAY_MAX];

int m_size;

};

template < >

class Buffer < char > {

public:

Buffer(); …

private:

char m_array[STRLEN_MAX];

int m_strLength;

};

char–specialized� Class Buffer�Template

• Other members, methods,�type-specific method implementations, etc.
• Altogether a different Class.

Class

Buffer

Template

Template(s)

CS-202 C. Papachristos

The keyword template

​

Function With Class Template Parameters.

​

• A function parameter can be a Class Template object:

​

template < typename T >

void Sort( ArrayContainer< T > arrayContainer ){

for (…){

if ( arrayContainer[…] < arrayContainer[…] )

arrayContainer[…] = …;

}

}

​

​

​

• Type T might never appear in the Sort function,�but the function parameter is a Class Template (ArrayContainer<T>) object.

• Still this is a Function Template, and we have to declare that�T is a template type parameter it depends on.

Template(s)

CS-202 C. Papachristos

The keyword template

​

Class friend(s) & template(s).

​

• A Class Template can have friend functions →

​

template < typename T >

class ArrayContainer {

public:

ArrayContainer(); …

friend ostream & operator<<(ostream& os, const ArrayContainer<T> & a);

​

private:

T * m_arr; …

};

​

​

​

warning: friend declaration 'std::ostream& operator<<(std::ostream&, const ArrayContainer<T>&)' declares a non-template function [-Wnon-template-friend]

note: (if this is not what you intended, make sure the function template has already been declared and add <> after the function name here)

undefined reference to `operator<<(std::ostream&, ArrayContainer<int> const&)'

Compilation proceeds with warnings.

Linking fails.

• Non-member Function appears as if non-Templated.
• Compiler will not attempt to find code Template & create code for one to match the Class Template.

BUT they might need�to be Templates too !

Template(s)

CS-202 C. Papachristos

The keyword template

​

Class friend(s) & template(s).

​

• A Class Template can have friend functions →

template < typename T >

class ArrayContainer {

public:

ArrayContainer(); …

friend ostream & operator<< <> (ostream& os, const ArrayContainer<T> & a);

​

private:

T * m_arr; …

};

​

• Implementation of the Templated friend function.

template < typename T >

ostream& operator<< (ostream & os, const ArrayContainer<T> & a)

{ for (…){ os << a[i]; } … return os; }

​

​

Declares the operator<< Function Template specialization (for�the particular T) as a friend.

BUT they might need�to be Templates too !

Template(s)

CS-202 C. Papachristos

The keyword template

​

Class friend(s) & template(s).

​

• Actual requirements for compiler to work:

​

template<typename T> class ArrayContainer;

template<typename T> ostream & operator<< (ostream & os, const ArrayContainer<T> & a);

​

template < typename T >

class ArrayContainer {

public:

ArrayContainer(); …

friend ostream & operator<< <> (ostream & os, const ArrayContainer<T> & a);

​

private:

T * m_arr; …

};

​

template < typename T >

ostream & operator<< (ostream & os, const ArrayContainer<T> & a){

for (…){ os << a[i]; } …

return os;

}

​

​

Forward Declarations

Class Template

Function Implementation

Template(s)

CS-202 C. Papachristos

The keyword template

​

Class friend(s) & template(s).

​

• Or the “easy” way:

​

template < typename T >

class ArrayContainer {

public:

ArrayContainer(); …

friend ostream & operator<< (ostream & os, const ArrayContainer<T> & a)

​

friend ostream & operator<< (ostream & os, const ArrayContainer & a)

{

for (…){ os << a[i]; }

return os;

}

​

private:

T * m_arr; …

};

​

Inline Declaration inside Templated Class Body generates�a separate non-templated operator<< for each T and makes it a friend of its ArrayContainer<T>.

or

Template(s)

CS-202 C. Papachristos

The keywords template and typename

​

Name(s) and template(s).

​

Qualified / Unqualified Names

​

• Example of Qualified names:

​

std:: cout << "Hello World! " << std:: endl ;

​

Objects’ Names cout and endl are Qualified (in the namespace std).

Template(s)

CS-202 C. Papachristos

The keywords template and typename

​

Name(s) and template(s).

​

Qualified / Unqualified Names

​

• Example of Qualified names:

​

std:: cout << "Hello World! " << std:: endl ;

​

• Example of Unqualified names:

​

using namespace std;

cout << "Hello World!" << endl ;

​

• The Compiler has to lookup names by respecting and evaluating qualifications.

using directive introduces Names into the Namespace scope that it appears in (same as using std::cout; using std::endl;).

Template(s)

CS-202 C. Papachristos

The keywords template and typename

​

Name(s) and template(s).

​

Qualified / Unqualified Names

​

• Example of Qualified names:

​

std:: cout << "Hello World! " << std:: endl ;

​

• Example of Unqualified names:

​

using namespace std;

cout << "Hello World!" << endl ;

​

• The Compiler has to lookup names by respecting and evaluating qualifications.

Note: Still Qualified names, despite introducing std names into global scope.

using namespace std;

std::cout << "Hello World!" << std::endl ;

Template(s)

CS-202 C. Papachristos

The keywords template and typename

​

Name(s) and template(s).

​

Dependent Names

​

• Name(s) of constructs whose instantiations Depend on Template Parameters (& can’t be looked-up until these are known).

​

template < typename T >

class MotionPlan : public List< T >

{

MotionPlan() : m_total( List<T>::total_num )

{ }

​

void AdvanceWaypoint(List< T > * l)

{ l -> m_wp ++; }

​

const int m_total;

​

typename List< T >::Waypoint m_wp;

};

List<T> is Dependent on T: (CityName, GeoReferencedCoordinate, CheckerboardSquare …)

Template(s)

CS-202 C. Papachristos

The keywords template and typename

​

Name(s) and template(s).

​

Dependent Names

​

• Name(s) of constructs whose instantiations Depend on Template Parameters (& can’t be looked-up until these are known).

​

template < typename T >

class MotionPlan : public List< T >

{

MotionPlan() : m_total( List<T>::total_num )

{ }

​

void AdvanceWaypoint(List< T > * l)

{ l -> m_wp ++; }

​

const int m_total;

​

typename List< T >::Waypoint m_wp;

};

A Member of the Templated Class l�whose instantiation is dependent on T: (raw pointer, index, iterator…)

Template(s)

CS-202 C. Papachristos

The keywords template and typename

​

Name(s) and template(s).

​

Dependent Names

​

• Name(s) of constructs whose instantiations Depend on Template Parameters (& can’t be looked-up until these are known).

​

template < typename T >

class MotionPlan : public List< T >

{

MotionPlan() : m_total( List<T>::total_num )

{ }

​

void AdvanceWaypoint(List< T > * l)

{ l -> m_wp ++; }

​

const int m_total;

​

typename List< T >::Waypoint m_wp;

};

A Type whose instantiation

is Dependent on T.

template < typename T >

class List

{

static const int total_num = … ;

​

typedef T* Waypoint;

};

Template(s)

CS-202 C. Papachristos

The (keyword) typename Disambiguator

​

Disambiguation of Dependent & Qualified Names:

​

​

template < typename T >

void sort_local(){

ArrayContainer< T > :: Accessor ac;

​

​

ac.moveToBeginning(); T data = ac.accessData();

ac.moveForward(); T data = ac.accessData();

…

}

​

C++ Standard (14.6/2): “A name used in a template declaration or definition and that is� dependent on a template-parameter is assumed not to name a type unless the applicable� name lookup finds a type name or the name is qualified by the keyword typename.”

Compiler will attempt to interpret this as a variable.

• … :: Accessor is a Qualified name.
• Accessor is the name of a Type whose instantiation is Dependent on Template Parameter T.

When instantiating code employing Names that are Qualified and Dependent�the Compiler needs to know T is used as part of a Type name, as the Standard demands early checking�to be enabled (otherwise Accessor can be the name of a Member or a nested Type, and we would have�to wait until T is known to perform any checks.

Template(s)

CS-202 C. Papachristos

The (keyword) typename Disambiguator

​

Disambiguation of Dependent & Qualified Names:

​

​

template < typename T >

void sort_local(){

ArrayContainer< T > :: Accessor ac;

​

typename ArrayContainer< T > :: Accessor ac;

​

ac.moveToBeginning(); T data = ac.accessData();

ac.moveForward(); T data = ac.accessData();

…

}

​

• … :: Accessor is a Qualified name.
• Accessor is the name of a Type whose instantiation is Dependent on Template Parameter T.

Template(s)

CS-202 C. Papachristos

The (keyword) template Disambiguator

​

Disambiguation of Explicitly Qualified Template Member(s):

​

​

• Explicitly-Qualified names:

​

class TplMethodClass {

public: …

template<typename T>

T tpl_member_func();

};

​

template < typename U >

void func( U arg )

{

int obj =

arg . template tpl_member_func<int>();

}

ISO C++03 14.2/4 :

​

When the name of a member template specialization appears after . or -> in a postfix-expression, or after nested-name-specifier in a qualified-id, and the postfix-expression or qualified-id�explicitly depends on a template-parameter (14.6.2), the member template name must be prefixed by the keyword template. Otherwise the name is assumed to name a non-template.

​

Note: Otherwise the compiler can’t know early on whether the upcoming symbol < is a less-than operator or the beginning of a template parameters list.

​

STL

CS-202 C. Papachristos

The Standard Template Library

​

A library of C++ very useful classes and functions that were developed over time and are now part of the C++ Standard Library.

​

The STL contains many useful things, including:

​

• Containers

Store Data and maintain Data Association.

• Container Adapters

Provide Higher-level Data Structure interfaces but can rely on different Container back-ends.

​

• Iterators

Access & Manipulation of Data.

​

All are Function & Class Templates !

• They can be used with (almost) any type of data.

​

STL

CS-202 C. Papachristos

The Standard Template Library

​

A library of C++ very useful classes and functions that were developed over time and are now part of the C++ Standard Library.

​

The STL provides Re-usable code:

​

• Exhaustively tested & optimized
• Thoroughly debugged
• Standardized
• Extensive & Comprehensive

linked list, vector, map, multi-map, pair, set, multi-set, queue, stack, etc …

​

We usually have many more things to do than re-inventing the wheel ...

STL

CS-202 C. Papachristos

STL Containers

​

All containers implemented in the form of multilayered Class Templates.

​

They all provide interfaces for some common basic operations:

​

• bool empty();

​

• void clear();

​

• std::size_t size();

​

Note:

std::size_t is the type of any sizeof expression and is guaranteed to be able to express:

• The maximum size of any object (including any array).
• The maximum number for any array index.
• Used for array sizes, indexes, and for iteration:

for ( std::size_t i = 0; i<…; ++i){ … }

Check if container is empty.

Mark the container as empty, and deallocate data if necessary.

Return number of elements in the container.

STL

CS-202 C. Papachristos

STL Containers

​

Vector(s) ( std::vector< … > )

​

Basic attributes:

​

• Dynamic Container (its size can change), contains elements of Type T.
• Sequential Container (its elements are in order).
• Random Access Container.

Using:

T & operator[](std::size_t pos);

​

T & at(std::size_t pos);

Access element at position pos (without bounds checking).

Access element at position pos�(throws a std::out_of_range Exception�if !(pos < size())).

Both return Reference (not Pointer) to requested element.

STL

CS-202 C. Papachristos

STL Containers

​

Vector(s) ( std::vector< … > )

​

Basic functions:

​

• T & front();
• T & back();

​

• void push_back(const T & value);
• void pop_back();

​

​

​

​

• std::vector<T>::iterator insert(std::vector<T>::const_iterator pos, � const T & value);
• std::vector<T>::iterator erase(std::vector<T>::const_iterator pos);

​

• void resize(std::size_t size);

Access first and last element in the container.

Push element to last position (back) or remove last element (back).

Insert or erase element in any position within the container (iterator-based method).

Resize container to fit size number of elements.

STL

CS-202 C. Papachristos

STL Containers

​

Linked-List(s) ( std::list< … > , std::forward_list< … > )

​

Basic attributes:

​

• Doubly–Linked –or– Forward–List, contain elements of Type T.
• Constant-time insertion / removal from anywhere in the List.
• Does not support Random Access.

​

Basic functions:

​

• T & front(); / T & back();
• void push_back(const T & value); / void pop_back();
• void push_front(const T & value); / void pop_back();

​

• std::list<T>::iterator insert(std::list<T>::const_iterator pos, const T & value);
• std::list<T>::iterator erase(std::list<T>::const_iterator pos);

​

• void reverse(); / void sort(); / void merge(std::list<T> & other);

STL

CS-202 C. Papachristos

STL Containers

​

Set(s) ( std::set< … > )

​

Basic attributes – Unique Keys :

​

• Associative Container – contains Sorted set of elements of Type Key.
• Elements are sorted when added to the set, uses a Compare function (by default std::less, largely operator<()) to perform ordering of Key elements.
• Cannot change the Key key element value once added.
• Does not support Random Access.

​

Basic functions:

​

• std::set<Key>::iterator find(const Key & key);
• std::size_t count(const Key& key);

​

• std::pair<std::set<Key>::iterator, bool> insert(const Key & value);
• std::set<Key>::iterator erase(std::list<Key>::const_iterator pos);

Note:

Uses Equivalence checking (via the Compare function) to find matching Key key from the Set.

STL

CS-202 C. Papachristos

STL Containers

​

Multiset(s) ( std::multiset< … > )

​

Basic attributes – Multiple Key Entries :

​

• Can contain multiple Type Key keys with Equivalent values (unlike std::set<…>).
• Elements are sorted when added via Compare (by default operator<()).
• Cannot change the Key key element value once added.
• Does not support Random Access.

​

Basic functions:

​

• std::list<T>::iterator find(const Key & key);
• std::size_t count(const Key & key);

​

• std::pair<std::multiset<Key>::iterator, bool> insert(const Key & value);
• std::multiset<Key>::iterator erase(std::multi<Key>::const_iterator pos);

Note:

Uses Equivalence checking.

STL

CS-202 C. Papachristos

STL Containers

​

Pair(s) ( std::pair< …,… > )

​

Basic attributes:

​

• Connects two-Type items into a single Object.
• Two elements are stored in type T1 and T2 member variables:

T1 first;

T2 second;

• Publicly accessible (std::pair is a struct ADT).
• std::pair(s) are used by other containers.

​

Basic functions:

​

• std::pair<T1,T2> make_pair(T1 t1, T2 t2);

int racePosition = 1;

Car myCar("Gandalf");

​

std::pair<int, Car> racecar;

racecar.first = racePosition;

racecar.second = myCar;

std::pair<int, Car> racecar = std::make_pair(racePosition, myCar);

STL

CS-202 C. Papachristos

STL Containers

​

Map(s) ( std::map< …,… > )

​

Basic attributes – Unique Keys :

​

• Associative Container – contains Sorted Pairs of Type Key–Type T (value).
• Elements are sorted by their Key key when added (via Compare –by default operator<()), while association to the Type T value is maintained in the Pair.
• Cannot change the Key key element value once added.
• Can change however the associated T value of that key-value Pair.

​

Basic functions:

​

• std::map<Key,T>::iterator find(const Key & key);
• std::size_t count(const Key & key);

​

• std::pair<std::map<Key,T>::iterator, bool> insert(const std::pair<const Key,T> & v);
• std::map<Key,T>::iterator erase(std::map<Key>::const_iterator pos);

Note:

Uses Equivalence checking (via Compare) to find matching Key key.

STL

CS-202 C. Papachristos

STL Containers

​

Multimap(s) ( std::multimap< …,… > )

​

Basic attributes – Multiple Key Entries :

​

• Can contain Sorted Pairs of Type Key–Type T (value) with multiple Type Key keys with Equivalent values (unlike std::map<…,…>).
• Elements are sorted by their Key key when added (via Compare).
• Cannot change the Key key element value once added.
• Can change however the associated T value of that key-value Pair.

​

Basic functions:

​

• std::multimap<Key,T>::iterator find(const Key & key);
• std::size_t count(const Key & key);

​

• std::pair<std::map<Key,T>::iterator, bool> insert(const std::pair<const Key,T> & v);
• std::multimap<Key,T>::iterator erase(std::multimap<Key>::const_iterator pos);

Note:

Uses Equivalence checking.

STL

CS-202 C. Papachristos

STL Containers

​

Unordered Map(s) ( std::unordered_map< …,… > )

​

Basic attributes – Unique Keys :

​

• Associative Container – contains Non-Sorted Pairs of Type Key–Type T (value).
• Operations such as element Search, Insertion, Removal have Average Constant Time complexity.
• Typically used to implement Hash-Tables.
• Cannot change the Key key element value once added.
• Can change however the associated T value of that key-value Pair.

​

Basic functions:

​

• std::unordered_map<Key,T>::iterator find(const Key & key);

​

• std::pair<std::unordered_map<Key,T>::iterator, bool> insert(const std::pair<const Key,T> & v);
• std::unordered_map<Key,T>::iterator erase(std::unordered_map<Key>::const_iterator pos);

STL

CS-202 C. Papachristos

STL Containers

​

A Cheatsheet for:

• Array(s)
• Vector(s)
• Queue(s)

Double-ended Queue(s) – Deque(s) …

Priority Queue(s) …

• Stack(s)
• List(s)

Doubly-Linked List(s)

Forward-Linked List(s)

​

Many more …

​

​

STL

CS-202 C. Papachristos

STL Iterators

​

Iteration over STL Container elements.

​

• Problem: Not all STL classes provide Random Access

(Remember: Like std::vector<T>::at(size_t pos); conveniently does.)

​

Iterators

• Special (Container & Template-Dependent) pointers.
• Enable Iteration through each element in the STL Container.
• Abstraction → The same iteration Interface for any Container.
• Encapsulation → The user shouldn’t need to know how it works.

STL

CS-202 C. Papachristos

STL Iterators

​

Access elements in any STL Container using a unified interface, regardless of the internal details of the Container itself.

​

Any such Iterator should be able to perform:

• Moving to the container’s “beginning” (first element).
• Advancing to the “next” element.
• Returning the “value” it refers (points) to.
• Check if it has reached the container’s “end”.

STL

CS-202 C. Papachristos

STL Iterators

​

Iterator Operations

​

• begin()

​

intVec_it = intVec.begin();

​

• end()

intVec_it = intVec.end();

Handling of empty range condition: intVec.begin()==intVec.end().

• operator++(…) / operator--(…) (Post-&-Pre Increment / Decrement)

​

​

++intVec_it; / intVec_it++;

--intVec_it; / intVec_it--;

​

a) A STL Vector Container of Type int

std::vector<int> intVec;

​

b) An Iterator for a STL Vector of Type int

std::vector<int>::iterator intVec_it;

Returns an iterator (pointing) to first element in Container.

Returns an iterator to one element past the last of the Container.

Advances iterator (element it is pointed to) by one, forward or backward.

Note:

Kinds of Iterators include Forward Its (++ works), Bidirectional Its (++/-- works), Random Access Its (++/-- works).

STL

CS-202 C. Papachristos

STL Iterators

​

Iterator Operations

​

• Dereferencing an Iterator

​

if (!intVec.empty())

​

​

intVec_it = intVec.begin();

​

​

int intVec_element0 = * intVec_it ;

}

​

Dereferencing returns a Reference-to the Container’s element pointed-to by the Iterator.

​

a) A STL Vector Container of Type int

std::vector<int> intVec;

​

b) An Iterator for a STL Vector of Type int

std::vector<int>::iterator intVec_it;

Note:

Attention, the end() Iterator is pointed to one element past the last in the Container.

• It should never be Dereferenced:

Set Iterator to point to first element in the Container.

Checking with empty() is usually faster than checking size()>0.

intVec_it = intVec.end();

* intVec_it;

Undefined Behavior

STL

CS-202 C. Papachristos

STL Iterators

​

Iterator Operations

​

Behavior of Dereferencing an Iterator dictates if it is Constant / Mutable.

​

Mutable Iterator

​

• Can change corresponding element in Container using a Mutable Iterator.
• Can use *it to assign to variable or output, but as well assign to the element in the Container by-Reference (and change it).

​

Example:

*it Returns an lvalue

*it can be on the left-(or right)-hand side of the assignment operator.

STL

CS-202 C. Papachristos

STL Iterators

​

Iterator Operations

​

Behavior of Dereferencing an Iterator dictates if it is Constant / Mutable.

​

Constant Iterator

​

• Cannot change contents of Container using a Constant Iterator.
• Dereferencing ( * ) produces a read-only version of element.
• Can use *it to assign to variable or output, but cannot change element in container

​

Example:

*it = <anything>; Illegal

*it can only be on the right-hand side of the assignment operator.

STL

CS-202 C. Papachristos

STL Iterators

​

Iterator Operators

​

​

• * Dereferences the Iterator.

​

• ++ Moves Iterator forward to point to “next” element.
• -- Moves Iterator backward to point to “previous” element.

​

• == True if two Iterators point to same element.
• != True if two Iterators point to different elements.

​

• = Assignment, makes two iterators point to same element.

​

STL

CS-202 C. Papachristos

STL Iterators

​

Iterator Operations – std::vector<T>

​

Container Traversal w/ Iterator(s)

​

#include <vector>

​

std::vector<int> intVec;

intVec.push_back( 1 );

intVec.push_back( 5 );

…

for (std::vector<int>::iterator it = intVec.begin();

it != intVec.end();

++it)

{

std::cout << *it << std::endl;

}

Declare Iterator for STL Vector�of Type int.

• Set it to the first element.
• Check to see if container end has been reached.
• Advance to next element.

• Dereference current element.

• Include appropriate Header(s).

STL

CS-202 C. Papachristos

STL Iterators

​

Iterator Operations – std::list<T>

​

Container Traversal w/ Iterator(s)

​

#include <list>

​

std::list<int> intList;

intList.push_back( 1 );

intList.push_front( 5 );

…

for (std::list<int>::iterator it = intList.begin();

it != intList.end();

++it)

{

std::cout << *it << std::endl;

}

Declare Iterator for STL List�of Type int.

• Set it to the first element.
• Check to see if container end has been reached.
• Advance to next element.

• Dereference current element.

• Include appropriate Header(s).

STL

CS-202 C. Papachristos

STL Iterators

​

Reverse-Iterator(s)

​

Container Reverse-Traversal w/ Reverse-Iterator(s)

​

a) A STL Vector Container of Type int.

std::vector<int> intVec;

​

b) A Reverse-Iterator for a STL Vector of Type int.

std::vector<int>::reverse_iterator intVec_revit;

​

for ( intVec_revit = intVec.rbegin();

intVec_revit != intVec.rend();

++intVec_revit )

{

std::cout << *intVec_revit << std::endl;

}

• Working with Reverse-Iterators requires using rbegin() and rend().
• ++ advances Reverse-Iterator reversely (so backwards in the Container order).

STL

CS-202 C. Papachristos

STL Iterators

​

Iterator Examples – std::set<Key>

​

int main ( ) {

​

set<int> iSet;

​

iSet.insert(4);

iSet.insert(12);

iSet.insert(7);

​

/* the same looping construct for traversal */

​

for (set<int>::const_iterator it = iSet.begin(); it != iSet.end(); ++it)

{

cout << *it << endl;

}

​

return 0;

}

A Constant (non-Mutable) Iterator for a STL Set of Type int.

Output:

4

7

12

STL

CS-202 C. Papachristos

STL Iterators

​

Iterator Examples – std::map<Key,T>

​

int main ( ) {

​

map<string, float> stocks;

​

stocks.insert( make_pair( string("IBM"), 42.50) );

stocks.insert( make_pair( string("MS"), 2.50) );

stocks.insert( make_pair( string("FB"), 0.50) );

​

/* the same looping construct for traversal */

​

for (map<const string,float>::iterator it=stocks.begin(); it!=stocks.end(); ++it)

{

cout << it->first << "," << it->second << endl;

}

​

return 0;

}

Iterator for STL Map functions�like a Pointer to a Pair Struct.

Output:

FB,0.5

IBM,42.5

MS,2.5

Template(s)

CS-202 C. Papachristos

Remember: The template Parameter(s) List

​

The Template Parameter(s) List – More General.

​

• Supports multiple Parameter Types & Non-Type Parameters:

​

template < typename T, typename U, typename V, int N, char C >

return-type func_tpl_name(parameters-list){ … }

​

template < typename T, typename U, typename V, int N, char C >

class ClassTplName { … };

​

• Supports Default Parameters:

​

​

template < typename T = int , size_t N = MAX_ELEMENTS >

class ClassTplDfltParamsName {

…

};

Note:

Used to be only for Class Templates, from C++11 supported fully.

Template(s)

CS-202 C. Papachristos

Advanced: The template Parameter(s) List

​

Template Template Param(s) : template< template< … > >

• ~Enforced usage-case for keywords class & typename:

​

A simple Class Template:

template < typename T >

class TplClass{ public: TplClass(); … private: T * m_t_Pt; … };

​

A simple Type parameter T.

Note:

Not any more either,�but not a bad practice!

Template(s)

CS-202 C. Papachristos

Advanced: The template Parameter(s) List

​

Template Template Param(s) : template< template< … > >

• ~Enforced usage-case for keywords class & typename:

​

A simple Class Template:

template < typename T >

class TplClass{ public: TplClass(); … private: T * m_t_Pt; … };

​

Another Class Template, for which one Template Type is another Class Template:

template < typename T , template < typename > class ClassTpl >

class ClassTplTpl {

public: …

private:

ClassTpl < T > m_classTpl;

…

};

2 Type Parameters: one is a simple T , and one is a Class Template ClassTpl<…> .

A member that is of a generalized Class Type that is itself templated for a some Type.

Template(s)

CS-202 C. Papachristos

Advanced: The template Parameter(s) List

​

Template Template Param(s) : template< template< … > >

• ~Enforced usage-case for keywords class & typename:

​

A simple Class Template:

template < typename T >

class TplClass{ public: TplClass(); … private: T * m_t_Pt; … };

​

Another Class Template, for which one Template Type is another Class Template:

template < typename T , template < typename > class ClassTpl >

class ClassTplTpl {

public: …

private:

ClassTpl < T > m_classTpl;

…

};

Note1: Template Template syntax (used to) need keyword class to compile.

Note: There is no Template Template Template in C++.

Note2: We don’t even need to specify typename U here, all the compiler cares about is ClassTpl.

Template(s)

CS-202 C. Papachristos

Advanced: The template Parameter(s) List

​

Template Template Param(s) : template< template< … > >

• Utility By-Example:

​

2 (or more) different�Class Templates:

​

​

The Class Template�Class Template:

​

​

Possible to create:

AdvancedClass< int , ClassA > intAType;

AdvancedClass< Car , ClassB > carBType;

​

template < typename T >

class ClassA {

public: ClassA();

private: T m_t_arr[…];

};

template < typename T >

class ClassB {

public: ClassB();

private: T * m_t_Pt;

};

template <typename T, template < typename > class ClassTpl>

class AdvancedClass {

public: …

private:

ClassTpl < T > m_advanced; …

};

m_advanced is of ClassA for int Types !

m_advanced is of ClassB for Car Types !

Template(s)

CS-202 C. Papachristos

Advanced: The template Parameter(s) List

​

Template Template Param(s) : template< template< … > >

• Utility By-Example:

​

2 (or more) different�Templated Classes�for element storage:

​

​

A Class Template�Class Template�acting as an Adapter:

​

Create Queue variations:

Queue< int, CircularArray > int_qA;

Queue< Car, ForwardList > car_qL;

​

template < typename T >

class CircularArray {

public: CircularArray();

private: T m_arr[…]; ...

};

template < typename T >

class ForwardList {

public: ForwardList();

private: Node <T> * m_head; ...

};

template <class Type, template < typename > class ContainerType>

class Queue { //or class Stack, or another DDS container adapter

public: …

private:

ContainerType < Type > m_container; …

};

m_container is CircularArray w/ ints!

m_container is ForwardList w/ Cars !

Remember: Queue(s) as Container Adaptors

CS-202 C. Papachristos

#ifndef QUEUE_HPP_

#define QUEUE_HPP_

​

// default-used container class template header

#include <CircularArray/CircularArray.hpp>

​

template <typename Type,

template <typename> class ContainerType = CircularArray>

class Queue{

public:

Queue();

Queue(size_t count, const Type & val = Type());

Queue(const Queue<Type,ContainerType> & other);

~Queue();

​

Queue<Type,ContainerType> & operator=(

const Queue<Type,ContainerType> & other);

bool empty() const;

size_t size() const;

void push(const Type & value);

void pop();

void clear();

Type & front(); const Type & front() const;

Type & back(); const Type & back() const;

private:

ContainerType<Type> m_container;

};

​

//class template Queue method implementations ...

​

#endif

“Common” Header File: Queue.hpp

#ifndef FORWARD_LIST_HPP_

#define FORWARD_LIST_HPP_

​

template <typename Type>

class ForwardList {

// Node helper struct

template <typename>

struct Node { … Type m_data; Node<Type> * m_next; };

​

public:

ForwardList();

...

private:

Node<Type> * m_front, * m_back;

};

//class template ForwardList implementations ...

​

#endif

#ifndef CIRCULAR_ARRAY_HPP_

#define CIRCULAR_ARRAY_HPP_

​

template <typename Type>

class CircularArray {

​

public:

CircularArray();

...

private:

Type * m_data;

std::size_t m_size, m_front, m_back, m_capacity;

};

//class template CircularArray implementations ...

​

#endif

Time for Questions !

CS-202

CS-202 C. Papachristos