STL-Lectures and Exam 2 Review for C++

Please Note that exam might contain short answers type questions.

Standard Template Library for C++

• A library in C++ that provides a set of common classes, algorithms, and data structures for generic programming.

• Includes: Containers, Adaptors,Utilities, Iterators, Functors, and Algorithms

• which can hold any data type

• largely created by Alexander Stepanov

• ready-made set of classes

• algorithms are INDEPENDENT of containers

• reduce complexity

• provides:

  1. compile-time polymorphism

  2. more efficient than run-time polymorphism

• first library with generic programming and data structures with 4 ideas in mind:

  1. generic programming (use of templates)

  2. abstractness without the loss of efficiency

  3. Von Neuman Computation Model

  4. value semantics

     • as part of the C++ Standard Library.

Containers

• Objects that contain other objects, such as vector, set, and map.

• Data structures that hold a collection of elements.

• Container-based code (2 rules):

  1. Never pass container into a function→iterator

  2. Never return containers→ Return or pass iterators

• 2 Types: Sequence and Associative Sequence

• The image shows what falls under each type.

Iterators

• Represent locations in a container and allow for traversal and manipulation of the container's elements.

• each container has its own iterator type

• They can be incremented or dereferenced, and two iterators can be compared.

• specify the position in the container

• special type: past-the-end

• can ask vector for iterator (use of begin and end)

• to get the source element: increment and dereference 1st iterator UNTIL = 2nd iterator (semi-open range, has start but not an end)

STL:

<iterator> A header in the STL that includes iterator classes for traversing containers.

• not specific, does not end at a specific value

• any object pointing to some element in a range of elements

• ITERATE through elements

• most obvious: POINTER (form of iterator)

• other types: vector container type

• NOTE: not all iterators have the same functionality as a pointer

5 Categories;

1. Random Access—> implement all functions below + can access ranges non-sequentially, offsets can be applied directly, can iterate without having to iterator though ALL elements eg. pointers

2. Bidirectional—> iterate through both directions, all standard containers support this.

3. Forward—> have the functionality of input and output, limited to 1 direction, iterate through the range

4. Input: most limited, only sequential

5. Output: most limited, only sequential

In order, of what each can do. EX. Random Access can do all

Algorithms Page 34 to 39

• Operations on containers, such as find, sort, and random_shuffle.

• Routines to perform operations on container classes.

• each need a certain level of iterator

• has its library in c++

• The algorithms library defines functions for a variety of purposes (e.g. searching, sorting, counting, manipulating) that operate on ranges of elements.

• Note that a range is defined as [first, last) where last refers to the element past the last element to inspect or modify.

• Types (All use <algorithm> unless stated otherwise ): Non-modifying sequence operations (16) , Modifying Sequence Operations (29), Partitioning Operations (5), Sorting Operations (7), Binary Search operations (4), Set Operations (7), Heap Operations(6), Minimum/Maximum operations (10), Numeric Operations (5)= needs<numeric> header, and for C-library(2)= need <cstdlib>

Functors

• Operations on objects, such as less and plus, that can be used as function objects.

• Classes in C++ that overload the function operator (operator()) and can be treated as functions or function pointers.

Adaptors

Objects that change the interface of other objects, such as not1 and not2.

Utilities

Components such as pairs and comparison operations that provide additional functionality. Eg. in ANSI standard allocators are categorized as utilities

Diagnostics (Background info. of the program)

Tools provided to handle exceptions and errors.

Locales (Background info. of the program)

Facilitate internationalization and provide localization support.

Numerics (Background info. of the Program)

Container types optimized for speed, such as valarray and complex.

Strings (Background info.)

Replace C's character arrays and provide string manipulation capabilities.

Streams (Background info. )

Used for input and output operations.

Allocators (Background info.)

Customize memory allocation, such as malloc_alloc.

Abstractness without loss of efficiency

The ability to write generic code that is efficient and can work with different types.

Von Neumann computation model

A model of computation that represents a computer's architecture.

Value semantics

The behavior of objects where their values are copied and modified independently.

Vector

• A container class in the STL that behaves like an array but can dynamically grow in size.

• one of its operations is push_back —> push an element onto the end of the vector (grows by one=increase size)

• block of contiguous initialized elements

• fast at the insertion end and has random access

• Insert and removing from the back: amortized constant time

• Insert and removing from beginning or middle: linear time

• example of specialized type is bool

• if one element k is initialized then so have the rest with one indices less than K

• can be pre-sized, given size at construction

• logical number of elements: number of elements it has with size (highest-indexed)

• size: function that returns the number of elements in a vector

• capacity: maximum number of elements the vector can hold before reallocating

• use iterator to get to the first element with begin and use past-the-end iterator with end which will point to the first element of the vector.

• Vector & Iterator: compared equal if they refer to the same element of the same vector

 

Public member function: std::Vector::Vector

1. Default Constructor (empty): explicit vector (const allocator_type& alloc = allocator_type()); or  eg. std::vector <int> vector1;

2. Fill Constructor (container with n elements): explicit vector (size_type n, const value_type& val= value_type(), const allocator_type& alloc= allocator_type()); or eg. std:: vector<int> vector1 (10,6); 10 is the size and 6 is the value

3. Range Constructor (many elements as the range [first,last)): template <class InputIterator> vector (InputIterator first, InputIterator last, const allocator_type& alloc= allocator_type ()) ; or eg. std::vector<int> vector1(vector2.begin(),vector2.end() );

4. Copy Constructor (copy of each element): vector (const list& x);

or eg. std:: vector<int> vector1(vector2);

Numbers 2 to 3 are considered overloaded as they give you different options to create the container std::vector. 

past-the-end

A special iterator value that represents the position after the last element in a container.

begin

A message that can be sent to a vector to obtain an iterator that points to the first element.

end

A message that can be sent to a vector to obtain a past-the-end iterator.

sort

An operation that takes two iterators to specify the source range and sorts the elements between them.

RandomAccess

An iterator category that implements all the functionalities of bidirectional iterators and can access ranges non-sequentially.

Bidirectional

An iterator category that can be iterated through in both directions.

Forward

An iterator category that has all the functionality of input and output iterators but is limited to one direction.

Input

An iterator category specialized in performing only sequential input operations.

Output

An iterator category specialized in performing only sequential output operations.

iterator_traits

A class template that provides a uniform interface to the properties of an iterator.

reverse_iterator

An iterator adaptor for reverse-order traversal.

back_insert_iterator

An iterator adaptor for insertion at the end of a container.

front_insert_iterator

An iterator adaptor for insertion at the front of a container.

insert_iterator

An iterator adaptor for insertion into a container.

advance

A function that advances an iterator by a given distance.

distance

A function that returns the distance between two iterators.

begin

A function that returns an iterator to the beginning of a container or array.

end

A function that returns an iterator to the end of a container or array.

Iterator adaptors

Types in the Standard Template Library (STL) that transform the interface of other types, allowing iterators to iterate over streams.

istream_iterator

An iterator adaptor in the STL that reads elements from an input stream, such as cin.

It’s Constructor: template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>

class istream_iterator {

public:

// ...

istream_iterator(istream_type& s);

// ...

}; or

istream_iterator<int>start(cin);//input from stream

link: cplusplus.com/reference/iterator/istream_iterator/

Template

• A feature in C++ that allows functions and classes to operate with generic types, enabling them to work on many different data types without being rewritten for each one.

• very useful when combined with multiple inheritance and operator overloading

• Think of it as a FORMULA

• can generate type-specific versions

• Example in Image→ click on it to view

Function template

A formula from which type-specific versions of a function can be generated, allowing the function to be used with different types without having to rewrite it for each type.

max

A function template example that returns the maximum of two values, with the type determined at compile time based on how the function is used.

myReverse

A function template example that reverses the elements in a container, such as a vector or string.

showContents

A function template example that displays the contents of a container, such as a vector or string.

Class template

A specification for generating classes based on parameters.

Templated class

A class that is instantiated by passing a given set of types as template arguments.

Sequences

Contiguous blocks of objects that allow insertion at any point in the sequence.

Stacks

A restricted version of a container that provides LIFO (Last-In, First-Out) behavior.

Queues

A restricted version of a container that provides FIFO (First-In, First-Out) behavior.

Associative containers

Containers that can be indexed by any type, such as sets and maps.

Priority queues

A container that provides a priority queue interface, where the element with the highest priority is on top.

Container algorithms

Algorithms that operate on containers, such as sorting or shuffling elements.

Pair

• A simple associative container consisting of a 2-tuple of data elements or objects.

• called ‘first’ and ‘second’ in that order

• can be assigned, copied, and compared

• Pairs by Default are: map and hash_map

• ‘first’ element acts as the unique keys, each associated with their ‘second’ value objects.

List → sequence container

• A doubly-linked list container.

• fast insertion anywhere

• ONLY sequential access

• not stored in contiguous memory

• opposite of vector

• Slow look-up and access (linear time) but once found is quick (constant time)

  public member function

  std::list::list

  
  

  1. Default Constructor (empty): 

  explicit list (const allocator_type& alloc = allocator_type());

  eg. std::list<int>list1;

  
  

  2.Fill Constructor (with n elements):

  explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());

  eg. std::list<int>list2(5,10); //5 is size and 10 is value

  
  

  3. Range Constructor (with as many elements [first,last)):

  template <class InputIterator>  list (InputIterator first, InputIterator last,  const allocator_type& alloc = allocator_type());

  eg. std::list<int> list1 (list2.begin(),list2.end());

  
  

  4. Copy Constructor (copy of each of the elements in x): 

  list (const list& x);

  eg. std::list<int>list1(list2);

  
  

Deque→sequence container

• A vector-like container with insertion/erase at the beginning or end in amortized constant time.

• double ended queue

• WARNING: lacks some guarantees on iterator validity after altering the deque.

Queue→ container adaptor

• provides a FIFO queue interface in terms of push/pop/front/back operations

• Any sequence supporting operations front(), back(), push_back(), and pop_front() can be used to instantiate queue (e.g. list and deque)

Public member function

std::queue::queue

1.Default Constructor: explicit queue (const container_type& ctnr = container_type());//constructs a queue container adaptor object.   

eg. std::queue<int> queue1;

2. Copy Constructor (another of same type)

queue (const queue& x);

eg. std::queue<int> queue1(queue2);

Priority_queue→Container adaptor

• provides a priority queue interface in terms of push/pop/top operations (the element with the highest priority is on top)

• Any random-access sequence supporting operations front(), push_back(), andpop_back() can be used to instantiate priority_queue (e.g. vector and deque). Elements should additionally support comparison (to determine which element has a higher priority and should be popped first).

Stack—>container adaptors

• provides a LIFO stack interface in terms of push/pop/top operations (the last-inserted element is on top).

• Any sequence supporting operations back(), push_back(), and pop_back() can be used to instantiate stack (e.g. vector, list, and deque)

public member function

std::stack::stack

1. Default Constructor: explicit stack (const container_type& ctnr = container_type());

eg. std::stack<int>stack1;

2. Copy Constructor (another of the same type)

stack (const stack& x);

eg.std::stack<int>stack1(stack2);

Associative containers

Containers that store elements in a specific order based on their values.

Unordered collections

Containers that do not maintain a specific order for their elements.

Set—> associative container

• stores a collection of unique elements

• a mathematical set; inserting/erasing elements in a set does not invalidate iterators pointing in the set. Provides set operations union, intersection, difference, symmetric difference and test of inclusion. Type of data must implement comparison operator < or custom comparator function must be specified. Implemented using a self-balancing binary search tree.

• Description: 

  These containers store unique elements that are organized in a specific order and each element is characterized by a value referred to as a key of type T which uniquely identifies it. Once set this key cannot be modified although elements are considered constant they can still be inserted or removed from the container. The sorting of elements is determined by a strict weak ordering using internal comparisons. This type of container is commonly employed in the context of binary search trees.

  
  

  public member function

  std::set::set

  
  

  1. Default Constructor (empty):

  explicit set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

  
  

  eg.std::set<int> set1;

  
  

  2. Range Constructor (with as many element as the range [first,last)):

  template <class InputIterator> set (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

  
  

  eg. std::set<int>set1(set2.begin(),set2.end());

  
  

  3. Copy Constructor (copy of each element x):

  set (const set& x);

  eg.std::set<int>set1(set2);

  
  

Multiset—> associative container

• same as set but allows duplicate elements

Map→associative container

• array that maps keys to values.

• Description: This belongs to the category of associative containers that organize elements using a combination of key and mapped values in a specific order. The key values serve to both sort and uniquely identify each element while the mapped values store content associated with the key values grouped by value type. Similar to the set containers this follows a strict weak ordering based on internal comparisons and is frequently employed in binary search tree structures. / allows mapping from one data item (a key) to another (a value). Type of key must implement comparison operator < or custom comparator function must be specified. Implemented using a self-balancing binary search tree.

  
  

  public member function:

  
  

  std::map::map

  
  

  1. Default Constructor (empty):

  explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());

  
  

  eg.std::map<int, std::string> map1; //int is the key type and string is the value type

  
  

  2. Range Constructor (with as many elements as the range [first,last)):

  template <class InputIterator> map (InputIterator first, InputIterator last,const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());

  
  

  eg. std::map<int, std::string> map1(map2.begin(),map2.end());

  
  

  3. Copy Constructor (copy of each element x):

  map (const map& x);

  
  

  eg. std::map<int, std::string> map1(map2);

Multimap—> associative container

• same as map but allows duplicate keys.

Hash_set

An unordered collection implemented using a hash table.

• All has starts with hash: similar to a set, multiset, map, or multimap, respectively, but implemented using a hash table; keys are not ordered, but a hash function must exist for the key type. Thesecontainers are not part of the C++ Standard Library, but are included in SGI's STL extensions, and are included in common libraries such as the GNU C++ Library in the__gnu_cxx namespace. These are scheduled to be added to the C++ standard as part ofTR1, with the slightly different names of unordered_set, unordered_multiset,unordered_map and unordered_multimap.

Hash_multiset

An unordered collection that allows duplicate elements, implemented using a hash table.

Hash_map

An unordered associative array implemented using a hash table.

Hash_multimap

An unordered associative array that allows duplicate keys, implemented using a hash table.

Bitset

• A data structure that stores a series of bits.

• stores series of bits similar to a fixed-sized vector of bools. Implements bitwise operations and lacks iterators. Not a Sequence.

Valarray

• A C-like array designed for high-speed numerics.

• It has many features that make it ideally suited for use with vector processors in traditional vector supercomputers and SIMD units in consumer-level scalar processors, and also ease vector mathematics programming even in scalar computers.

Non-modifying sequence operations→ <algorithm>

Operations that do not modify the elements in a range.

Modifying sequence operations→<algorithm>

Operations that modify the elements in a range.

*Page 35 to 36*

Partitioning operations→<algorithm>

Operations that divide a range of elements into two groups.

Sorting operations→<algorithm>

Operations that sort elements in a range.

Binary search operations→<algorithm>

Operations that search for elements in a sorted range using binary search.

Set operations→<algorithm>

Operations that perform set operations on sorted ranges.

Heap operations→<algorithm>

Operations that work with heap data structures.

Minimum/maximum operations→<algorithm>

Operations that find the minimum or maximum elements in a range.

Numeric operations→<numeric>

Functions in the header that perform mathematical operations on ranges of elements.

C library→<cstdlib>

• A library in C++ that provides functions for common operations, defined in the header.

• set of functions, macros, and constants that provide a wide range of functionality for tasks like input/output, string manipulation, memory allocation, and more.

Function objects/functors

• Another term for functors, which are objects that can be treated as functions.

• The STL includes classes that overload the function operator (operator())

• They are useful for keeping and retrieving state information in functions passed into other functions.

• Function objects (aka "functors").

• Functors are objects that can be treated as though they are a function or function pointer-

• -you could write code that looks like this:

• line 1: myFunctorClass functor;

• line 2: functor( 1, 2, 3 );

• This code works because C++ allows you to overload operator(), the "function call" operator.

• The function call operator can take any number of arguments of any types and return anything it wishes to. (It's probably the most flexible operator that can be overloaded)

C++ Standard Library

• A library in C++ that provides a collection of classes and functions for common programming tasks.

• builds on the foundations of the C Standard Library but extends it to provide generic, templated versions of data structures and algorithms.

ios→C++ Standard Library

A class in the C++ Standard Library for input/output stream operations.

iostream→C++ Standard Library

A header in the C++ Standard Library that includes the classes and functions for input/output stream operations.

iomanip→C++ Standard Library

A header in the C++ Standard Library that includes manipulators for formatting output.

fstream-→C++ Standard Library

A header in the C++ Standard Library that includes classes for file input/output operations.

sstream→C++ Standard Library

A header in the C++ Standard Library that includes classes for string stream operations.

functional

A header in the STL that includes function objects and other utility functions.

Container Adaptors

stack, queue & priority_queue

What is the relationship between objects and data type in C++ object-oriented programming?

Relationship : inheritance (is a), aggregation (has a), Association (general)

The C++ Language

Covers 3 aspects:

1. Data Abstraction (ex. classes allows us to do this) : Encapsulation, Protection, Resource Ownership

2. Relationship: Inheritance (is a), Aggregation (has a), Association (general)

3. Generic Programming: Components, Modeling Concepts, Adaptors

What is Data Abstraction?

• separates the interface.

• Implementation: how the object is used? Vs. How it works inside?

What does it mean by Relationship in C++?

• Relationship between Objects and Types in terms of object-oriented programming

• Inheritance: relationship between types “is a“

• Aggregation: relationship between types “has a“

• Association: relationship between types are “general“

What is generic programming in C++?

• originally used in ADA

• utilization of STL—> Standard Template Library

• emphasizes writing code in a way that is independent of the specific data types it operates on.

• It allows you to write algorithms and data structures that work with any type of data, rather than being tied to a specific type.

• key mechanism: the use of templates

• templates work as a placeholder

• emphasizes code reuse

Standard Containers

• manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference objects with similar properties to pointers)

• Containers replicate structures very commonly used in programming: dynamic arrays (vector), queues (queue), stacks (stack), heaps (priority_queue), linked lists (list), trees (set), associative arrays (map)...

Overall Characteristics of Each Category of iterator

All Can:

1. be copied and copy-constructed.

2. can be incremented.

Look at image for each of its specific

x →iterator type

a and b →objects of iterator

t→ object of the type pointed by the iterator type

n→ integer value

Iterator Classes Include several different types of templates: Page 12 to 14

1. Primitives = 7 of them

2. Adaptors = 5 of them

3. Stream Iterators= 4 of them

4. Functions Adaptors= 4 of them

5. Functions Operations= 6 of them

6. Non-member operations= 8 of them

Iterator Example

*Pay attention to Comments*

Here on Link: https://onlinegdb.com/GZxJfdwSh*

Iterator Adaptors

• iterate through streams!

• Either read or write elements to them

• Input stream: cin» has right functionality and privde access to a SEQUENCE element (WRONG interface for iterator)

• Adaptors→ transforms the interface of other types (like electrical adaptors)

• useful one: istream_iterator (is a template type)

• ex. istream_iterator <int>

• initialized by giving them a stream

• incrementing has no effect

• to deference, the iterator reads an element from the stream

• istream_iterator: can be created with a default constructor and has a past-the-end value

• Example in Image

Function Template Example

• In 19 and 21, the template argument T is automatically deduced by the compiler to be int and double, respectively.

• In 23, case deduction fails because the type of the parameters must in general exactly match the template arguments. (may be interpreted at int and double hence must be stated)

• This function template can be instantiated with any copy-constructible type for which the expression (y < x) is valid.

• For user-defined types, this implies that the less-than operator must be overloaded

Function template variations EXAMPLE: int and string example Page 23

https://onlinegdb.com/kV3U9xxXx

Class Templates

• generating classes based on parameters.

• instantiated by passing a given set of types to it as template arguments.

• The C++ Standard Library contains many class templates, in particular the containers adapted from the Standard Template Library, such as vector.

• Click Image to see syntax!