Course STL

(Standard Template Library) in C++

1
 Overview
• Introduction in STL
• STL and generic programming
• STL containers
• Iterators
• Algorithms
• Function objects

2
 Introduction in STL
• STL (Standard Template Library) is a component library (basically a
framework of containers and algorithms of ISO C++), which
ensures interoperability between predefined components
(language included) and user-defined components.
• Thus, an STL algorithm can also operate on user-defined
containers and user-defined algorithms can also work on STL
containers if they meet certain requirements.
• The library was designed by Alex Stepanov and Meng Lee at HP's
Palo Alto laboratories. The STL library was included in the ANSI
C++ standard in 1994 and accepted in 1998.
• STL as a major positive element leads to:
- Separate compilation of templates
- Better support for generic programming
- Generalized list initialization mechanism, etc.
• Versions of C++ 1y/2z brings new improvements to basic containers
as well as additional features
• If you drive some car, some software parts in will be based on C++
with STL. Not the low-level safety relevant parts, but “Big” fancy stuff
for media and navigation is often based on C++ with use of STL.
3
 Do STL and generic programming mark a definite
departure from the common C++ programming style?
• C++’s history can be split in three distinct phases. Each phase looks quite
different to the point that almost no more-year-old C++ code would be
considered “good” in 2023. These are almost distinct languages. If you have
problems in C++, you may use: [Link]
• legacy (1985–199X): C++ before the standardization. Effectively C with
classes and runtime polymorphism based on “virtual”. If you deal with a custom
string class for no good reason (CString of MFC) you are dealing with legacy
C++.
• pre-modern (199X–2011): Templates and exceptions were around since +/-
1990 (Annotated C++ Reference Manual book). C++98, the first C++ standard,
is introduced: A stable basis for compiler developers, library writers, and
programmers. The STL became part of the C++ standard library. So, you are
very unlikely to actually use the STL today, but everybody knows what one is
talking about. Exceptions were praised in the beginning but never overcame
criticism. They violate the fundamental rule of C++ with is “You only pay for what
you use”. Even nowadays, a significant amount of major C++ code bases do not
allow exceptions. Templates were introduced, but it took time to actually
understood they were useful for soo much more than generic container classes
or generic algorithms. Templates are better understood as compile time-code
generation than only limiting them to “generic algorithms”, but that understanding
took some time. C++03 was a new start point that Bjarne Stroustrup considered
for C++ to be appropriate to the new languages as Java, C#, Python, Go. 4
• modern C++ (2011- today- 2023 version): C++11 introduces move semantics,
unique_ptr/shared_ptr, constexpr, lambdas that really change how the language
is used. The trend continues towards (efficient) value semantics and doing more
work statically (at compile time) instead of dynamically. C++ optimizers have
become very powerful.

A long the way, the code C++ is used for have changed. In the beginning (until
Java) C++ was used for general applications. Scripting languages, Java and the
web changed that. Now, you wouldn’t (and arguably shouldn’t) use C++ when
there is not some kind of performance-problem or memory limitation. If you
are writing performance-critical code, C++ is the best thing to use. That is the
reason why a lot of the additions in modern C++ deal with performance
(move semantics, constexpr, templates are compile-time code generation) and
multi-threading (e.g., std::atomic).
• Legacy C++ code doesn’t look anything like pre-modern C++ code, which
doesn’t look anything like modern C++ code.
• The question deals with the transition from the legacy to pre-modern phase. So,
the 2025 answer to the question if the STL and generic programming mark a
departure from the common C++ style is clear “No”. They are in a lot of ways
the common C++ style.
• Even when you invest the time to develop a non-standard container class, you
do so mimic the “STL”-style. Everything else would be strange.
• If you do not use templates, you are either copying code around more than
needed, loose type safety opening up yourself up for bugs, or leave
performance on the table. Likely all three of them.
• Consider learning and using modern C++, it is now easier to write correct,
maintainable, nicely-abstracted, high-performance (C++) code then ever before.5
 STL structure
Consider the following situation where software components are imagined as a
multi-dimensional space:
- a dimension represents data types (int, char, float, double, user type ...) (i)
- another dimension is containers (arrays, linked lists, ...) (j)
- and the last dimension is algorithms (searching, sorting, ...) (k)
- In this case, i * j * k code versions must be designed to cover all possible
situations.
If we use the template (generic) functions/classes, the "i" axis may be missing,
and j * k code versions are needed. For example, we will have a single
implementation of the linked list for all types of data.
The next step is to make algorithms work for different types of containers
(arrays, lists, ...). This will only require j + k code versions.
- STL incorporates this concept and, as a result, simplifies the application
development process by reducing creation time, simplifying debugging and
increasing portability.

i int, double,
char, ...

k j
6
Searching arrays…
 STL components
• The main components of STL are:
• - containers: objects that can store and manage objects; contain
the data structures supported by the STL; for this, defines
template classes that contain these structures and methods for
data manipulation;
• - algorithms: procedures (methods) that can operate on
different containers;
• - iterators: abstractions of algorithm access to containers so that
the algorithms can operate on different containers (in fact they
are pointers to containers but have less flexibility than ordinary
pointers, flexibility given by the nature of the containers);
• - function objects: class data that have overloaded the function
call operator, ( );
• - adapter: encapsulates a component to provide another
interface (for example, to get a stack from a list).
7
STL diagram

8
 How is used STL
STL usage:
- everything related to the STL is placed in the standard
namespace, std; this must be specified by a using directive:
using namespace std;
- there is also the possibility to use only a section of this
namespace as follows:
using namespace std:: string;

Starting from the standard C++ library with 51 header files, 13

header files make up the original STL library.
These are: algorithm, deque, functional, iterator, vector, list, map,
memory, numeric, queue, set, stack, utility.

• Are used by:

#include <algorithm>
using namespace std;
The STL Library allows expansion, being based by only one
core. Extensions are defined based on imposed rules. 9
 STL containers
There are types of abstract data (classes) that can be used to build data collections
of the same type.
Characteristics :
- All containers are parameterized by the Type they contain
- Each container declares an iterator and special methods for iterators

Categories :
1. Sequence container: The data is ordered in a linear fashion and allows searches
based on the key (array, vector, forward_list, list, deque). There are ordered
collections in which each element has a certain position. The term "ordered" does
not mean ascending or descending but refers to a particular position. This position
depends on the time and place of insertion but is independent of the element's value.
2. Associative containers: data is kept in appropriate data structures for
associative searches (set, map, multiset, multimap). Are sorted collections where
the actual position of an item depends on its value due to a particular sorting
criterion. C++1y/2z introduced Unordered Associative Containers that are
unsorted collections (Hash collections).
3. Adapters: Provides different but specific interfaces for the above containers. They
are built on other containers and are used to force access rules that do not support
iterators. Stack and queue containers are made from deque.
4. Special containers: are almost containers with some limitations (string, bitset,
valarray), and are usually not considered as a separate category. They are
especially used to provide additional facilities to manage this data effectively in the
program development process.
10
STL containers: [Link]

11
 STL ordered and sequence containers -
[Link]

12
STL Adaptive and unordered containers:

13
//Student_string_qsort: Sorting (qsort) example –Special string container
//Student.h
class Student {
string name;
string surname;
int* marks;
int group;
//double avg_mark;
public:
Student( ){
name = "Unknown";
surname = "Unknown";
group = 1;
marks = new (nothrow) int[dim_note];
for (int i = 0; i < dim_note; i++) *(marks + i) = 5;
//avg_mark = 5.;
}
Student(string n, string p, int gr, int* m){
name = n;
surname = p;
group = gr;
marks = new (nothrow) int[dim_note];
for (int i = 0; i < dim_note; i++)
*(marks + i) = m[i];
//avg_mark = media( );
}
Student(const Student &std) {//copy constructor
name= [Link];
surname= [Link];
group = [Link];
marks = new (nothrow) int[dim_note];
for (int i = 0; i < dim_note; i++)
*(marks + i) = [Link][i];
//avg_mark = media( );
} 14
Student& operator=(const Student& std) {//assign overload
if (this != &std) {
name = [Link];
surname = [Link];
group = [Link];
//marks = new (nothrow) int[dim_note];
for (int i = 0; i < dim_note; i++) *(marks + i) = [Link][i];
//avg_mark = media();
}
return *this;
}
~Student( ){
delete [ ] marks;
}
double media( ){
int s = 0;
for (int i = 0; i < dim_note; i++)
s += marks[i];
return ((double)s / dim_note);
}
void setName(string n){
name = n;
}
string getName( ){
return name;
}
void setSurname(string p){
name = p;
}
string getSurname( ){
return surname;
}
int getGroup( ){
return group;
}
double getMedia( ){
//return avg_mark;
return media( );
} 15
};//Student
//main
#include <iostream>
using namespace std;
constexpr int dim_note = 3;

#include "Student.h"

int cmp_int(const void * a, const void * b);

int cmp_double(const void* a, const void* b);
int cmp_str(const void * a, const void * b);

int main( ){
int n;
string na, sur;
int group, me[dim_note] { };
cout << "\nEnter number of students: ";
cin >> n;
Student* tab = new (nothrow) Student[n];
for (int i = 0; i < n; i++) {
cout << "\nEnter name: ";
cin >> na;
cout << "\nEnter surname: ";
cin >> sur;
cout << "\nEnter group: ";
cin >> group;
for (int i = 0; i < dim_note; i++){
cout << "\nEnter marks ("<<dim_note<<") the " << i + 1 << ": ";
cin >> *(me + i);
}
tab[i] = Student(na, sur, group, me);
}
cout << "\nInitial array: \n";//recommended to overload the << operator
for (int i = 0; i < n; i++)
cout << i + 1 << ". " << tab[i].getName( ) << " " << tab[i].getSurname( ) << " Group:" << tab[i].getGroup( ) << "
Average mark: " << tab[i].getMedia( ) << endl; 16
 qsort(tab, (size_t)n, sizeof(*tab), (int(*)(const void*, const void*))cmp_double);
cout << "\nSorted array by media: \n";
for (int i = 0; i < n; i++)
cout << i + 1 << ". " << tab[i].getName( ) << " " << tab[i].getSurname( ) << " Group:" << tab[i].getGroup( ) << " Average
mark: " << tab[i].getMedia( ) << endl;

qsort(tab, (size_t)n, sizeof(*tab), (int(*)(const void*, const void*))cmp_int);

cout << "\nSorted array by Group: \n";
for (int i = 0; i < n; i++)
cout << i + 1 << ". " << tab[i].getName( ) << " " << tab[i].getSurname( ) << " Group:" << tab[i].getGroup( ) << " Average
mark: " << tab[i].getMedia( ) << endl;

qsort(tab, (size_t)n, sizeof(*tab), (int(*)(const void*, const void*))cmp_str);

cout << "\nSorted array by Name & Surname: \n";
for (int i = 0; i < n; i++)
cout << i + 1 << ". " << tab[i].getName( ) << " " << tab[i].getSurname( ) << " Group:" << tab[i].getGroup( ) << " Average
mark: " << tab[i].getMedia( ) << endl;
}//main

int cmp_int(const void * a, const void * b) {

Student* pa = (Student*)a;
Student* pb = (Student*)b;
return (pb->getGroup() > pa->getGroup());
}//cmp_int
int cmp_double(const void* a, const void* b) {
Student * pa = (Student *)a;
Student* pb = (Student*)b;
if (pb->getMedia() > pa->getMedia()) return 1;
else if (pb->getMedia() == pa->getMedia()) return 0;
else return -1;
}//cmp_double
int cmp_str(const void* a, const void* b) {
Student* pa = (Student*)a;
Student* pb = (Student*)b;
if (pa->getName() > pb->getName()) return 1;
else if (pa->getName() < pb->getName()) return -1;
if (pa->getSurname() > pb->getSurname()) return 1;
else if (pa->getSurname() < pb->getSurname()) return -1;
return 0; 17
}//cmp_str
 Other containers elements
From the initial STL framework new elements appeared as:
-forward_list as a sequential container for Single Linked Lists (SLL), non-contiguous memory
allocation as for list, that it is a Double Linked List (DLL)
[Link]
-unordered_map, unordered_set, as hash associative containers that can be multimap and multiset
-array as a one-dimensional fixed-size container
-bitset as bool array container.

bitset is a class template in the C++ STL that represents a fixed-size sequence of bits. It is defined in
the <bitset> header file. The class provides a set of member functions and overloaded operators to
manipulate the bits.

C++98 introduced a special container called valarray to hold and provide mathematical operations on
arrays efficiently.
It supports element-wise mathematical operations and various forms of generalized subscript operators,
slicing and indirect access.
As compared to vectors, valarray-s are more efficient in certain mathematical operations than vectors.

The declaration of a container is as follows:

Container_type <Type_concrete> c; // container object

The specific Type_concrete (user type, or primitive) must provide the copy constructor and the
overloading of the assign operator (explicit - for classes with attributes as pointers).

Example:
vector < int> tab1(10) ;
vector <float> tab2(20) ; 18
 What are the downsides of using STL in
C++?
• The Alex Stepanov Abstraction penalty: making an
algorithm or data structure completely generic has a
cost that is not supported by a hand-optimized
version that uses additional knowledge.
• There are only some fundamental data structures in
the initial STL as: array, vector, single-linked list,
double-linked list, deque, map, and unordered_map.
• If you need a graph, you’re out of luck.
• If you need a tree, you’re out of luck (even though
map is like a tree under the cover).
• People try hard not to go to the mental effort of coding
up their own data structures, creating a force-fit
situation. They prefer to use by default data
structures.
19
 vector container
• A vector manages its elements in a dynamic array using contiguous memory locations. This allows
random access. Adding and removing items at the end of the array is very fast.
• The structure of a vector looks like this:

A vector is described by a template class with implicit parameters, as follows:

template < typename T, typename Alloc = allocator<T> > class vector //generic template prototype
-T is the type of the elements in the container
-Alloc, class allocator that accepts as default template argument, allocator<T>.
-deque and list classes have the same header template, only the names are different.

In C++, does std::vector<T> call new and delete?

The short answer is: Yes, it does.
The long answer is that std::vector calls std::allocator::allocate and std::allocator::deallocate that in turn call
new and delete, respectively.
However, when you declare a vector, you can specify your own allocator, that will do what you want it to do.
Anyway, specifying an own allocator is something very advanced that is rarely done.

So, for a vector container type, it is sufficient to specify only its type, the allocator being the default provided
by the STL.
vector <int> v ;
vector <bool> b; is a specialization of the vector container, introduced in later versions of C++.

The beauty of std::vector is that it manages memory automatically used when you need an array that can
change size at runtime. But here's the interesting bit - the reserve() function. It's a cheeky little thing that can
boost your efficiency. It pre-allocates memory but doesn't initialize it. Meaning, when you want to add new
elements, there's already room for them. So, no waiting time. 20
 Main vector methods
begin ( ) returns an iterator to the first element
end ( ) returns an iterator after the last element
rbegin ( ) returns an inverse iterator, reverse iterator that points to the last element
in the vector
rend ( ) returns an inverse iterator, reverse iterator that points to the theoretical
element preceding the first element of the vector
cbegin ( ) returns a constant iterator to the first element
cend ( ) returns a constant iterator after the last element
push_back (...) adds an element to the end of the vector
pop_back (...) extracts an element from the end
swap (...) changes two vector elements, and swap ( , ) changes the elements of
two containers
insert ( , ) inserts an element
erase ( , ) delete an item (or more)
size ( ) returns the number of elements in the vector
capacity ( ) gives the capacity (number of elements) before makes a new
reallocation
reserve ( ) allocates in advance space for a number of elements
resize ( , ) resizes a vector
empty ( ) returns True if the vector is empty
[ ] access operator
... 21
 The following example defines an integer value vector, inserts 10
elements in a loop and other 2, and prints the vector elements:
//vector simple example
#include <iostream>
//vector header file
#include <vector>
using namespace std;
constexpr int dim = 10;

int main( ) {
//vector container for integer elements
//declaration
vector<int> coll;
//append elements with values from 1 to dim
for (int i = 1; i <= dim; ++i)
coll.push_back(i);
coll.push_back(dim /2);
coll.push_back(dim /4);
//print all elements separated by a space with a standard for
for (int unsigned i = 0; i < [Link]( ); ++i)
cout << coll[i] << ' ';
cout << endl;
return 0;
}//main

22
 The following example defines an integer value vector,
managed with for-range:
//vector for-range example
#include <iostream>
#include <vector>
//using namespace std;

int main( ) {
std::vector<int> v = { 0, 1, 2, 3, 4, 5 };
for (const int& i : v) // access by left reference to const values
std::cout << i << ' ';
std::cout << '\n';
for (auto i : v) // access by value, the type of i is int
std::cout << i << ' ';
std::cout << '\n';
for (auto&& i : v) // access by right value (forwarding) reference, the type of i is int&
std::cout << i << ' ';
std::cout << '\n';

const auto& cv = v;
for (auto&& i : cv) //access by right value (forward) reference, the type of i is const int&
std::cout << i << ' ';
std::cout << '\n';
}//main

23
 Lvalue Reference (&), Rvalue Reference (&&),
and Forwarding Reference (&&)
• Lvalue Reference (&)
Characteristics:
• Binds to Lvalues (i.e., named objects that persist).
• You can modify the collection via the reference.
• Does not allow moving elements from the container (unless explicitly using std::move on its elements).
• No ownership is transferred.

• Rvalue Reference (&&)

Characteristics:
• Binds to Rvalues (temporary objects).
• Allows moving data out of the container (e.g., using std::move or container methods that support it).
• Implies that the resource is temporary and disposable.
• Ownership can be transferred.

• Forwarding Reference (&&)

Characteristics:

• Also uses the syntax T&&, but T must be a deduced template parameter.
• Can bind to both Lvalues and Rvalues.
• Used with std::forward<T>(arg) to perfectly forward arguments.
• Commonly used in generic code (e.g., wrapper functions or constructors).

Conclusion:
Using && as Rvalue Reference enables by default move semantics, which is more efficient than copying, especially for
large collections like std::vector, std::string, etc. STL algorithms and containers use Rvalue references to optimize
performance by avoiding unnecessary copies. 24
Forwarding references are more flexible depending on the context, being a generalization of Rvalue reference.
 C++ forward references (optional) - [Link]
Forwarding references are a special kind of references that both ignore and preserve the value
category of a function argument, making it possible to forward it by means of forward.
Any code using such a reference for any other purpose than forwarding is actually ignoring Rvalue-
ness and const-ness of the associated parameter.
Forward argument: returns a Rvalue reference to arg if arg is not a Lvalue reference.
If arg is a Lvalue reference, the function returns arg without modifying its type.
Forwarding reference (Universal reference) — The mentioned type is a special type of reference that
can bind anything & everything. Universal reference can mean both Rvalue reference and Lvalue
reference. May facilitate copying, may facilitate moving.
Syntax of forward references is Type&& or auto&&.
When we use template parameter Type or auto, this becomes forward reference. When we know
the parameter type upfront, as we have int&& this is a Rvalue reference.
It means the forward reference is just the generalization of Rvalue reference.
Forwarding references allow a reference to binding to either a Lvalue or Rvalue depending on the
Type. Forward references enable perfect forwarding which means the ability to pass arguments by
maintaining their value category.
//Noncompliant //compliant
#include <utility> #include <utility>
#include <string> #include <string>
#include <iostream> #include <iostream>

template<typename TP> void f(TP&& arg) { template<typename TP> void f(TP&& arg) {
std::string s(arg);//Rvalue reference std::string s(std::forward<TP>(arg));//forward reference
} }

int main() { int main() {

std::string s("test"); std::string s("test");
f(std::move(s)); f(std::move(s));
std::cout << "f:" << s << std::endl; // output is std::cout << "f:" << s << std::endl; // output is "f:"
"f:test" return 0;
return 0; }//main
}//main
25
 The following example analyzes the operators within a vector:
//vector, operators
#include <vector>
#include <iostream>
using namespace std;
constexpr int dim =10;

int main( )
{//vector container for integer elements
unsigned int i;
vector<int> vec1, vec2, vec3;
cout<<"vec1 data: ";
//append elements with values from 1 to dim
for(i=1; i<=dim; ++i)
vec1.push_back(i);
//print all elements separated by a space with a standard for
for(i=0; i<[Link]( ); ++i)
cout<<vec1[i]<<' ';
cout<<endl;
cout<<"vec2 data: ";
//append elements with values 1 to dim 26
for(i=11; i<=2*dim; ++i)
vec2.push_back(i);
//print all elements separated by a space
for(i=0; i<[Link]( ); ++i)
cout<<vec2[i]<<' ';
cout<<endl;
cout<<"vec3 data: ";
//append elements with values 1 to dim
for(i=1; i<=dim; ++i)
vec3.push_back(i);
//print all elements separated by a space
for(i=0; i<[Link]( ); ++i)
cout<<vec3[i]<<' ';
cout<<"\n\n";
cout<<"Operation: vec1 != vec2"<<endl;
if(vec1 != vec2)
cout<<"vec1 and vec2 is not equal."<<endl;
else
cout<<"vec1 and vec2 is equal."<<endl;
cout<<"\nOperation: vec1 == vec3"<<endl;
if(vec1 == vec3)
cout<<"vec1 and vec3 is equal."<<endl;
else
cout<<"vec1 and vec3 is not equal."<<endl; 27
cout<<"\nOperation: vec1 < vec2"<<endl;
if(vec1 < vec2)
cout<<"vec1 less than vec2."<<endl;
else
cout<<"vec1 is not less than vec2."<<endl;
cout<<"\nOperation: vec2 > vec1"<<endl;
if(vec2 > vec1)
cout<<"vec2 greater than vec1."<<endl;
else
cout<<"vec2 is not greater than vec1."<<endl;
cout<<"\nOperation: vec2 >= vec1"<<endl;
if(vec2 >= vec1)
cout<<"vec2 greater or equal than vec1."<<endl;
else
cout<<"vec2 is not greater or equal than vec1."<<endl;
cout<<"\nOperation: vec1 <= vec2"<<endl;
if(vec1 <= vec2)
cout<<"vec1 less or equal than vec2."<<endl;
else
cout<<"vec1 is not less or equal than vec2."<<endl;
return 0;
}//main 28
 vector, swap( ) method for vectors change
//vector, swap( )
#include <vector>
#include <iostream>
using namespace std;

int main( ){
vector <int> vec1, vec2;
vec1.push_back(4);
vec1.push_back(7);
vec1.push_back(2);
vec1.push_back(12);
cout << "vec1 data: ";
for (auto &i: vec1) cout << i << ' ';
cout << endl;
vec2.push_back(11);
vec2.push_back(21);
vec2.push_back(30);
cout << "vec2 data: ";
for (auto &i : vec2) cout << i << ' ';
cout << endl; 29
cout << "The number of elements in vec1 = " << [Link]( ) << endl;
cout << "The number of elements in vec2 = " << [Link]( ) << endl;
cout << endl;
cout << "Operation: [Link](vec2)\n" << endl;
[Link](vec2);//swap vectors
cout << "The number of elements in v1 = " << [Link]( ) << endl;
cout << "The number of elements in v2 = " << [Link]( ) << endl;
cout << "vec1 data: ";
for (auto &i :vec1) cout << i << ' ';
cout << endl;
cout << "vec2 data: ";
for (auto &i :vec2) cout << i << ' ';
cout << endl;
return 0;
}//main

30
 vector, user data example
//Factura.h
constexpr int NL=5;

class Factura {
string factura;
int nrLucrari;
vector<double> preturi;
double pretMediuFacturi;

public:
Factura( ) {
nrLucrari = NL;
factura = "Nespecificat";
}//constructor fara parametrii
Factura(const string f, int nr, vector<double>pret, double p) :
factura{ f }, nrLucrari{ nr }, preturi{ pret }, pretMediuFacturi{ p }{ }//constructor cu parametrii
Factura(const Factura& ot) :
factura{ [Link] }, nrLucrari{ [Link] }, preturi{ [Link] }, pretMediuFacturi{ [Link] }
{ } // constructor de copiere
string getFactura( ) {
return factura;
}
int getNrLucrari( ) {
return nrLucrari;
}
void setFactura(const string f) {
factura = f;
}
void setLucrari(int l) {
nrLucrari = l;
} 31
void setPreturi(vector<double> v) {
preturi = v;
}
const vector <double> getPreturi() {
return preturi;
}
double pret(vector<double> v) {
double p = 0.;
for (const auto f : v) p += f;
return p;
}
void setPretMediu(double p) {
pretMediuFacturi = p;
}
void medie(vector<Factura> v) {
for (auto f : v) [Link](pret([Link]));
}
double TVA(Factura f, int tva) {
double p = pret([Link]);
double q = (tva / 100.) * p;
p = p + q;
return p;
}
};//Factura 32
//main
#include<iostream>
#include <vector>
using namespace std;
#include "Factura.h"

constexpr int dimP = 4;

constexpr int dimL = 4;
constexpr int TVAF = 20;

int main( ) {
vector<Factura> v;//declarare vectorul de facturi
vector<double> p1;//declarare vector de preturi
p1.push_back(15.);
p1.push_back(30.);
p1.push_back(30.);
p1.push_back(45.);
Factura f1;
[Link]("Constructii");
[Link](dimL);
[Link](p1);
vector<double> p2;//declarare vector de preturi
p2.push_back(15.);
p2.push_back(10.);
p2.push_back(20.);
p2.push_back(30.);
Factura f2;
[Link]("Montaj");
[Link](dimL);
[Link](p2); 33
vector<double> p3;//declarare vector de preturi
p3.push_back(15.);
p3.push_back(11.);
p3.push_back(22.);
Factura f3;
[Link]("Amenajari");
[Link](dimL - 1);
[Link](p3);

vector<double> p4;//declarare vector de preturi

p4.push_back(33.);
p4.push_back(44.);
Factura f4;
[Link]("Pavaje");
[Link](dimL - 2);
[Link](p4);

v.push_back(f1);//atasare facturi vectorul de facturi

v.push_back(f2);
v.push_back(f3);
v.push_back(f4);

cout << "\nAfisare obiecte vector facturi:";

for (auto f : v) {
cout << "\nServiciu: " << [Link]( ) << " [Link]: " << [Link]( ) << " Preturi: ";
for (const auto h : [Link]( )) cout << h << " ";
}
cout << "\n---------------------------------------"; 34
double mediu = 0.;
for (auto f : v) mediu = mediu + [Link]([Link]( ));
mediu = mediu / dimP;
cout << "\nPret mediu: " << mediu;
cout << "\n----------------------------------------";
vector<Factura> newvec;
for (int j = 1; j <= dimP; j++) {//sortare desc. dupa pret
Factura mare = v[0];
int i = 0;
int el = 0;
for (auto f : v) {
if ([Link]([Link]( )) > [Link]([Link]( ))) {
mare = f;
el = i; }
i++;
}
newvec.push_back(mare);
[Link]([Link]( ) + el);
}
cout << "\nAfisare sortare descrescatoare dupa pret: ";
for (auto x : newvec)
cout << "\nServiciu: " << [Link]( ) << " Pret factura: " << [Link]([Link]( ));
cout << "\n----------------------------------------------";

Factura newobj{ "Montaj",dimL,p2,20.};

Factura cpyobj = newobj;//apel constructor de copiere
cout << "\nObiectul creat prin copiere din Montaj este, Serviciu: " << [Link]( ) << "
NrLucrari: " << [Link]( ) << " Preturi: ";
for (const auto h : [Link]( )) cout << h << " ";
cout << "\nPretul cu TVA pentru noua factura = " << [Link](cpyobj, TVAF); 35
}//main
 deque containers
• The term deque (pronounced "deck") is an abbreviation for the "two-end
queue". It is a dynamic array that is implemented so that it can grow in both
directions.
• Putting the elements at the end and at the beginning is fast. However,
inserting the middle elements takes time for the elements to move. The deque
structure can be described as follows:

They are similar to vectors but are more efficient in case of insertion and
deletion of elements. Unlike vectors, contiguous storage allocation may not
be guaranteed.
The following example declares a deque of floating-point values, inserts
elements from 1.2 to 12 at the front of the container, and prints all deque
elements:

. 36
#include <iostream>
#include <deque>
using namespace std;
constexpr int dim = 10;

int main( ) {
//deque container for double-point elements declaration
deque<double> elem, elem1;
//insert the elements each at the front
cout << "push_front( )\n";
int i;
for (i = 1; i <= dim; ++i)
elem.push_front(i * (1.2));
//print all elements separated by a space
for (unsigned i = 0; i < [Link](); ++i)
cout << elem[i] << ' ';
cout << endl;
//insert the elements each at the back
cout << "\npush_back( )\n";
for (i = 1; i <= dim; ++i)
elem1.push_back(i * (1.2));
//print all elements separated by a space
for (unsigned i = 0; i < [Link](); ++i)
cout << elem1[i] << ' ';
cout << endl;
return 0; 37
}//main
 deque operations with iterators
//deque, constructors
#include <deque>
#include <iostream>
using namespace std;
constexpr int dim =10;

int main( ){
deque <int>::iterator deq0Iter, deq1Iter, deq2Iter, deq3Iter, deq4Iter, deq5Iter, deq6Iter;
//Create an empty deque deq0
deque <int> deq0;
//Create a deque deq1 with dim elements of default value 0
deque <int> deq1(dim);
//Create a deque deq2 with 7 elements of value 10
deque <int> deq2(7, 10);
//Create a deque deq3 with 4 elements of value 2 and with the
//allocator of deque deq2
deque <int> deq3(4, 2, deq2.get_allocator( ));
//Create a copy, deque deq4, of deque deq2
deque <int> deq4(deq2);
//deque deq5 a copy of the deq4(_First, _Last) range
deq4Iter = [Link]( );
deq4Iter++;
deq4Iter++;
deq4Iter++; 38
deque <int> deq5([Link]( ), deq4Iter);
//Create a deque deq6 by copying the range deq4 (_First, _Last) and the allocator of deque
deq2
deq4Iter = [Link]( );
deq4Iter++;
deq4Iter++;
deq4Iter++;
deque <int> deq6([Link]( ), deq4Iter, deq2.get_allocator( ));
cout<<"Operation: deque <int> deq0\n";
cout<<"deq0 data: ";
for(deq0Iter = [Link]( ); deq0Iter != [Link]( ); deq0Iter++)
cout<<*deq0Iter<<" ";
cout<<endl;
cout<<"\nOperation: deque <int> deq1(dim)\n";
cout<<"deq1 data: ";
for(deq1Iter = [Link]( ); deq1Iter != [Link]( ); deq1Iter++)
cout<<*deq1Iter<<" ";
cout<<endl;
cout<<"\nOperation: deque <int> deq2(7, 3)\n";
cout<<"deq2 data: ";
for(deq2Iter = [Link]( ); deq2Iter != [Link]( ); deq2Iter++)
cout<<*deq2Iter<<" ";
cout<<endl;
39
cout<<"\nOperation: deque <int> deq3(4, 2, deq2.get_allocator( ))\n";
cout<<"deq3 data: ";
for(deq3Iter = [Link]( ); deq3Iter != [Link]( ); deq3Iter++)
cout<<*deq3Iter<<" ";
cout<<endl;
cout<<"\nOperation: deque <int> deq4(deq2);\n";
cout<<"deq4 data: ";
for(deq4Iter = [Link]( ); deq4Iter != [Link]( ); deq4Iter++)
cout<<*deq4Iter<<" ";
cout<<endl;
cout<<"\nOperation1: deq4Iter++...\n";
cout<<"Operation2: deque <int> deq5([Link]( ), deq4Iter)\n";
cout<<"deq5 data: ";
for(deq5Iter = [Link]( ); deq5Iter != [Link]( ); deq5Iter++)
cout << *deq5Iter<<" ";
cout << endl;
cout<<"\nOperation1: deq4Iter = [Link]( ) and deq4Iter++...\n";
cout<<"Operation2: deque <int> deq6([Link]( ), \n"
" deq4Iter, deq2.get_allocator( ))\n";
cout<<"deq6 data: ";
for(deq6Iter = [Link]( ); deq6Iter != [Link]( ); deq6Iter++)
cout<<*deq6Iter<<" ";
cout<<endl;
return 0;
}//main
40
• The other containers have similar properties that can be analyzed separately
for each individual.
• The stack (LIFO) and queue (FIFO) containers use the deque <T>
container as the default adapter.
template <typename T, typename Container = deque<T> > class stack
template <typename T, typename Container = deque<T> > class queue

Sorted queue, priority_queue is so defined:

template <typename T, typename Container = vector<T>, typename
Compare = less<typename Container::value_type> > class priority_queue

For associative sorted containers, the elements in the containers are

referenced by the key and not by their absolute position in the container. Here
we have:
1) set, are containers that store single items in a certain order:

template < typename T, // set::key_type/value_type

typename Compare = less<T>, // set::key_compare/value_compare
typename Alloc = allocator<T> > // set::allocator_type
class set

Compare is the ordering criterion in the set with the default argument, less <T>.
41
• 2) multiset, allows duplicate keys with the same header.
• 3) map, are associative containers that store the elements formed
by a combination of a key value and a mapped value, following a
specific order:
template < typename Key, // map::key_type
typename T, // map::mapped_type
typename Compare = less<Key>, // map::key_compare
typename Alloc = allocator<pair<const Key,T> >
//map::allocator_type
class map

In a map, key values ​are generally used to sort and uniquely identify
the items, while mapped values ​store the associated content to
that key.
Key value types and mapped value may differ, and are grouped into
the value_type member, which is a pair type combining both by:
typedef pair<const Key, T> value_type;

4) multimap is defined with the same header and allows keys with
42
duplicate values.
 Iterators
• Iterators act as intermediates between algorithms and containers,
providing access to objects stored in a container without knowing
the type of the elements.
• They are generalizers of the pointers and allow the unitary
treatment of different types of data.
• They can be used to cross collections of data stored in containers.
• The iterators of a particular collection (container) are defined in the
class associated with the collection, in the form of typedef
constructions:
vector<string>::iterator it;
vector<string>::const_iterator cit;
• Containers have methods that return iterators:
• - begin( ): returns an iterator to the first element
• - end( ): returns an iterator after the last element; this iterator
can be used as a sentinel when marking the collection and is also
called past the end
• Two iterators are considered equal if they indicate the same
element or indicate the value next to the last element (past the
end). The compiler does not check the iterator domains i.e., if two
iterators indicate on the same container or not. 43
• The iterator has the scope operator that precedes it:
vector <int> :: iterator p;
For:
vector <int> vi;//container of vector type
the first occurrence of a value (7) is determined by:
p= find ([Link]( ), [Link]( ), 7) ;
if (p!= [Link]( ){cout<<"Found val. 7 in vi";}
else {cout <<"Not Found val. 7 in vi ";}

Using an iterator is done as follows:

Container_name ::iterator first, last;//declaration

first = Container_name.begin( );//assign
last = Container_name.end( );
or:
Container_name ::iterator first= Container_name.begin( );//init
Container_name ::iterator last= Container_name.end( );
44
 Types of Iterators:
[Link]
[Link]
• Input, InputIterator: Reads an item at a time in the
forward direction.
• Output, OutputIterator: Write an item at a time in the
forward direction (ostream).
• Forward, ForwardIterator: Reads or writes an item at a
time forward (forward_list as a SLL).
• Bidirectional, BidirectionalIterator: Read or write,
forward or backward (list, map, set).
• Random access, RandomAccessIterator: Same
as bidirectional, plus jumps at any distance within the
collection (vector).
• Besides these categories, there are also adapters
iterators that only make backward (reverse) traverses,
insert iterators, iterators that are read-only, etc.
45
 Iterator operators
• We consider that i, j are iterators and n is an integer.
• Operators sharing all types of iterators:
++i Advances a position and returns the new i value
i++ Advances a position and returns the old i value
• Input Iterators:
*i Returns a read-only reference to the element in the position given by i
i == j Returns TRUE if the two iterators are positioned on the same element (or after
the last item in the collection)
i! = j Returns TRUE if i and j are positioned on different elements
• Output Iterators:
*i Returns a reference to the element in the position given by i
i = j Sets for i the same position as for j
• Bidirectional iterators:
--i Withdraw a position and return the new value for i
i-- Withdraw a position and return the old value for i
• Random access iterators:
i + = n Advances n positions, returns the new value for i
i- = n Withdraw n positions, reintroduces the new value for i
i + n Returns an iterator positioned over n elements after i
i – n Returns an iterator positioned over n elements in front of i
i [n] Returns a reference to element n in the collection
46
 Simple iterators example using list container:
//iterator simple example
#include <iostream>
#include <list>
using namespace std;

int main( ) {
//lst, list container for character elements
list<char> lst;
//append elements from 'A' to 'Z'
//to the list lst container
for (char chs = 'A'; chs <= 'Z'; ++chs)
lst.push_back(chs);
//iterate over all elements and print,
//separated by space
list<char>::const_iterator pos;
//for (auto& pos : lst)
//cout << pos << ' ';
for (pos = [Link]( ); pos != [Link]( ); ++pos)
cout << *pos << ' ';
cout << endl;
return 0; 47
}//main
 Simple iterators example using multiset container:
//iterator, multiset example
#include <iostream>
#include <set>
using namespace std;

int main( ){
//multiset container of int data type
multiset<int> tst;
//insert elements
[Link](12);
[Link](21);
[Link](32);
[Link](31);
[Link](9);
[Link](14);
[Link](21);
[Link](31);
[Link](7);
//iterate over all elements and print, separated by space
multiset<int>::const_iterator pos;
//preincrement and predecrement are fast than postincrement and postdecrement.
for(pos = [Link]( ); pos != [Link]( ); ++pos)
cout<<*pos<<' ';
cout<<endl;
return 0;
}//main 48
 Simple iterators example using multimap container:
//iterator, multimap simple example
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main( ){
//type of the collection
multimap<int, string> mmp;
//set container for int/string values ,insert some elements in arbitrary order, notice a value of key 1
[Link](make_pair(5,"learn"));
[Link](make_pair(2,"map"));
[Link](make_pair(1,"Testing"));
[Link](make_pair(7,"tagged"));
[Link](make_pair(4,"strings"));
[Link](make_pair(6,"iterator!"));
[Link](make_pair(1,"the"));
[Link](make_pair(3,"tagged"));
//iterate over all elements and print, element member second is the value
multimap<int, string>::iterator pos;
for(pos = [Link]( ); pos != [Link]( ); ++pos)
cout<<pos->second<<' ';
cout<<endl;
return 0;
}//main

Iterators can be analyzed according to their types, allowed operators, etc.

49
 pair type – Microsoft version
#include <array>
#include <iostream>
#include <iterator>
#include <numeric>
#include <utility>
using namespace std;

template <typename T1, typename T2>

auto sum_and_difference(const T1& a, const T2& b) {
const auto sum = a + b;
const auto difference = a - b;
return make_pair(sum, difference);
}//must be defined before to be used because returns an auto result

int main( ) {
auto p1 = sum_and_difference(42.0, 17.0);
cout << "dsum = " << [Link] << " ddiff = " << [Link] << '\n';
auto p2 = sum_and_difference(42, 17);
cout << "isum = " << [Link] << " idiff = " << [Link] << '\n';

// Creates a 100-element array filled with 0, 1, 2, .. 99.

auto a = array<int, 100>{ };
iota(begin(a), end(a), 0);//⍳ function (represented with the ninth letter of the Greek alphabet, iota)
//is used to create a zero-based array of consecutive, ascending integers of a specified length

auto it = begin(a) + 42;//iterator

auto p3 = sum_and_difference(it, 17);
cout << "*itsum = " << *[Link] << " *itdiff = " << *[Link] << '\n'; 50
}//main
 Algorithms
• STL algorithms are generic member functions
(methods) that operate on containers.
• In order to be able to work with different types of
containers, these methods have no containers as
arguments but only iterators specifying the part or the
containers in their entirety.
• Thus, algorithms can also work on data types that are
not STL containers.
• This makes a decoupling between algorithms and
containers via iterators.
• It is very important that those containers support the
necessary iterators for an algorithm (see supplementary
documentation for containers).
• In this way, any container can be combined with any
type of algorithm. All components work with arbitrary
types, being a good example of the generic programming
concept.
51
Example:
template <typename ForwardIterator> ForwardIterator min_element
(ForwardIterator first, ForwardIterator last);
• This algorithm requires a container that supports at least one
ForwardIterator. The attempt to use an algorithm on a
container that does not provide the necessary iterators leads
to errors, sometimes strange.
• The algorithms are in the <algorithm> library, more than 60
algorithms have been integrated at the beginning, and now
there are approximately 80 algorithms.

52
 Types of Algorithms
• The main types of STL algorithms are:
• Algorithm
– Sorting
– Searching
– Important STL Algorithms
– Useful Array algorithms
– Partition Operations
• Numeric
– valarray class

53
 Simple STL algorithm:
//Algorithm, simple example
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

//predicate, which returns whether an integer is a prime number

bool isPrimeNum(int number);//function used as function_object in find_if

int main( ){
list<int> lst1;
//insert elements from 10 to 20
for(int i=10; i<=20; ++i)
lst1.push_back(i);
//search for prime number
list<int>::iterator pos;
cout<<"The list lst1 data:\n";
for(pos=[Link]( ); pos!=[Link]( ); pos++)
cout << *pos << " ";
cout<<endl<<endl;
54
pos = find_if([Link]( ), [Link]( ),isPrimeNum); //range predicate
if(pos != [Link]( ))//found
cout<<*pos<<" is the first prime number found"<<endl;
else //not found
cout<<"no prime number found"<<endl;
return 0;
}//main

bool isPrimeNum(int number){

//ignore negative sign
number = abs(number);
//0 and 1 are prime numbers
if(number == 0 || number == 1)return true;
//find divisor that divides without a remainder
int divisor;
for(divisor = (number/2); (number%divisor) != 0; --divisor){ }
//if no divisor greater than 1 is found, it is a prime number
return (divisor == 1);
}// isPrimeNum

55
 Types of algorithms
• Sequence operations that do not cause
changes:
-Apply a function to all elements (for_each ...)
-Look for an element that satisfies a condition (find, find_if ...)
-Counts the elements that satisfy a condition (count ...)
-Look for the first mismatch between two sequences (mismatch ...)
-Check whether two sequences are equal (equal ...)
-Look for the first matching of a subsequence in another sequence
(search ...)
• Generalized numerical operations
-Sum all elements of a sequence (accumulate)
-Calculates the scalar product of two sequences (inner_product)
-Calculates partial amounts (partial_sum)
-Calculates a new sequence starting from partial sums in another
sequence (adjacent_difference)
56
 Sequence operations that cause changes:
-Copy a sequence to another sequence (copy ...)
-Interchange values ​or ranges (swap ...)
-Transforms a sequence or two sequences into a new sequence
(transform ...)
-Replace the specified elements (replace ...) and (replace_if ( ))
replace the elements that satisfy a predicate
-Populate a domain with a value (fill, fill_n)
-Populate a field with generated values ​(generated, generated_n),
replaces all, or n elements with those generated
-Delete items (remove ...)
-Delete duplicates (unique, unique_copy)
-Inverse a sequence (reverse, reverse_copy)
-Rotation of elements (rotated, rotate_copy)
-Randomly blend items (random_suffle)
-Partitioning with elements that satisfy a predicate (partition,
stable_partition)

57
 STL sort( ) algorithm
• When the original STL was designed by Alex Stepanov (and friends),
he felt strongly that the algorithms should include not only semantic
constraints, but also performance constraints.
• The sort( ) template should under no circumstance be implemented
using the InsertionSort algorithm. The best guaranteed - O( NlogN )
sorting algorithm at the time was a HeapSort variant, but it was on
average about twice slower than the best QuickSort variants.
• Dave Musser, long-time friend and collaborator of Alex Stepanov (and
also the person who originally implemented std::set and std::map as
associative containers), came up with a scheme that combines
QuickSort and HeapSort (basically switching from the former to the
latter if the QuickSort partitions start to look bad): He called the
resulting algorithm IntroSort. IntroSort involves also InsertSort and
MergeSort. ([Link]
sort/)
• GCC compilers uses a variation of Musser’s IntroSort. This
guarantees a worst-case running time of O(n log n):
• It begins with quicksort and switches to heapsort when the recursion
depth exceeds a level based on the number of elements being sorted.58
 Sorting and associated operations:
-Domain sorting sort (...)
-Placing the element n in the final position that would result from
sorting (nth_element)
-Look for the limits, or position of a value in a sorted sequence
(lower_bound, upper_bound, equal_range, binary_search)
-Interlace two sorted sequences (merge, inplace_merge)
-Set operations on sorted sequences (includes, set_union,
set_intersection, set_difference, set_symmetric_difference)
-Heap operations (push_heap, pop_heap, make_heap, sort_heap)
-Look for the minimum or maximum element (min, max,
min_element, max_element) of two or one sequence
-Determine lexicographic order of two sequences
(lexicographical_compare)
-Generate permutations for a sequence (next_premutation,
prev_permutation) in lexicographical order
59
 Sorting algorithm:
//algorithm, sort( )
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;

//Return whether first element is greater than the second

bool userdefgreater(int elem1, int elem2);//used as function object in sort
constexpr int dim =15;

int main( ){
vector <int> vec1; //container
vector <int>::iterator Iter1; //iterator
int k;
for(k = 0; k <= dim; k++)
vec1.push_back(k);
random_shuffle([Link]( ), [Link]( ));

60
cout<<"Original random shuffle vector vec1 data:\n";
for(Iter1 = [Link]( ); Iter1 != [Link]( ); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
sort([Link]( ), [Link]( ));
cout<<"\nSorted vector vec1 data:\n";
for(Iter1 = [Link]( ); Iter1 != [Link]( ); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
//To sort in descending order, specify binary predicate
sort([Link]( ), [Link]( ), greater<int>( ));
cout<<"\nRe sorted (greater) vector vec1 data:\n";
for(Iter1 = [Link]( ); Iter1 != [Link]( ); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
//A user-defined binary predicate can also be used
sort([Link]( ), [Link]( ), userdefgreater);
cout<<"\nUser defined re sorted vector vec1 data:\n";
for(Iter1 = [Link]( ); Iter1 != [Link]( ); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
return 0;
}//main

bool userdefgreater(int elem1, int elem2)

61
{return elem1 > elem2;}
//main() for same previously example with Student class (slide 14) and STL sort() method
#include <iostream>
#include <algorithm>
using namespace std;

constexpr int dim_note = 3;

#include "Student.h"

bool compareMedia(Student s1, Student s2);

bool compareNameSurname(Student s1, Student s2);
bool compareGroup(Student s1, Student s2);

int main( ) {
int n;
string na, sur;
int group, me[dim_note]{ };
cout << "\nEnter number of students: ";
cin >> n;
Student* tab = new (nothrow) Student[n];//a pointer to an array of dynamic Student objects, that may be used as an array
for (int i = 0; i < n; i++) {
cout << "\nEnter name: ";
cin >> na;
cout << "\nEnter surname: ";
cin >> sur;
cout << "\nEnter group: ";
cin >> group;
for (int i = 0; i < dim_note; i++) {
cout << "\nEnter marks (" << dim_note << ") the " << i + 1 << ": ";
cin >> *(me + i);
}
tab[i] = Student(na, sur, group, me);
}
cout << "\nInitial array: \n";//recommended to overload the << operator
for (int i = 0; i < n; i++)
cout << i + 1 << ". " << tab[i].getName() << " " << tab[i].getSurname() << " Group:" << tab[i].getGroup() << "
Average mark: " << tab[i].getMedia() << endl;
62
 sort(tab, tab + n, compareMedia);
cout << "\nSorted array by media: \n";
for (int i = 0; i < n; i++)
cout << i + 1 << ". " << tab[i].getName() << " " << tab[i].getSurname() << "
Group:" << tab[i].getGroup() << " Average mark: " << tab[i].getMedia() << endl;

sort(tab, tab + n, compareGroup);

cout << "\nSorted array by Group: \n";
for (int i = 0; i < n; i++)
cout << i + 1 << ". " << tab[i].getName() << " " << tab[i].getSurname() << "
Group:" << tab[i].getGroup() << " Average mark: " << tab[i].getMedia() << endl;

sort(tab, tab + n, compareNameSurname);

cout << "\nSorted array by Name & Surname: \n";
for (int i = 0; i < n; i++)
cout << i + 1 << ". " << tab[i].getName() << " " << tab[i].getSurname() << "
Group:" << tab[i].getGroup() << " Average mark: " << tab[i].getMedia() << endl;
}//main

bool compareMedia(Student s1, Student s2) {

return [Link]() < [Link]();
}// compareMedia
bool compareNameSurname(Student s1, Student s2) {
if ([Link]() == [Link]()) return [Link]() < [Link]();
else return [Link]() < [Link]();
}//compareName
bool compareGroup(Student s1, Student s2) {
return [Link]() < [Link]();
}//compareGroup 63
//Sorting Example -STL Objects using Person class
//Person.h

class Person {
string name;
int age;
string favoriteColor;
public:
const string getName( ) { return name; }
int getAge( ) { return age; }
string getFavoriteColor( ) { return favoriteColor; }

static void introdu(vector <Person> &p, int n) {

for (vector<Person>::size_type i = 0; i != n; ++i){
cout << "Person #" << i + 1 << " name: ";
cin >> p[i].name;
cout << "Person #" << i + 1 << " age: ";
cin >> p[i].age;
cout << "Person #" << i + 1 << " favorite color: ";
cin >> p[i].favoriteColor; }
}
};//Person

// Sort Container by name compare function

bool sortByName(Person &lhs, Person &rhs) { return [Link]( ) < [Link]( ); }
// Sort Container by age compare function
bool sortByAge(Person &lhs, Person &rhs) { return [Link]( ) < [Link]( ); }
// Sort Container by favorite color compare function
bool sortByColor(Person &lhs, Person &rhs) { if([Link]( ) < [Link](
)) return true; 64
else return false; }
//main
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#include "Person.h"

int main( ) { int n;

cout << "\nEnter no. of peoples: " << endl;
cin >> n;
// Make a vector that holds n blank Person Objects
vector<Person> people(n);
cout << "\nEnter values\n";
Person::introdu(people, n);
cout << "\nSort by name\n";
sort([Link]( ), [Link]( ), sortByName);
for (Person &n : people)
cout << [Link]( ) << " ";
cout << "\nSort by age\n";
sort([Link]( ), [Link]( ), sortByAge);
for (Person &n : people)
cout << [Link]( ) << " ";
cout << "\nSort by color\n";
sort([Link]( ), [Link]( ), sortByColor);
for (Person &n : people)
cout << [Link]( ) << " ";
return 0; 65
}//main
//main
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#include "Person.h"

int main( ) { int n;

cout << "\nEnter no. of peoples: " << endl;
cin >> n;
// Make a vector that holds n blank Person Objects
vector<Person> people(n);
cout << "\nEnter values\n";
Person::introdu(people, n);
cout << "\nSort by name\n";
sort([Link]( ), [Link]( ), sortByName);
for (Person &n : people)
cout << [Link]( ) << " ";
cout << "\nSort by age\n";
sort([Link]( ), [Link]( ), sortByAge);
for (Person &n : people)
cout << [Link]( ) << " ";
cout << "\nSort by color\n";
sort([Link]( ), [Link]( ), sortByColor);
for (Person &n : people)
cout << [Link]( ) << " ";
return 0; 66
}//main
 STL sort( ) in new C++ compilers
• With C++17, the STL introduced parallel algorithms, which allow
you to leverage multi-core processors for better performance. To
use parallel sorting, you need to include the <execution> header
and specify an execution policy.
• Visual Studio 2022 defaults to C++14 capabilities, which does not
allow for the use of newer features introduced in C++17 and C++20.

• To use these newer features, you’ll need to enable a newer

language standard. Unfortunately, there is currently no way to do
this globally - you must do so on a project-by-project basis.

67
68
//STL sort standard and parallel processing
#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>
#include <chrono>

int main() {
std::vector<int> data(1000000);
std::generate([Link](), [Link](), std::rand);

// Sequential sort
auto start = std::chrono::high_resolution_clock::now();
std::sort([Link](), [Link]());
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration = end - start;
std::cout << "Sequential sort took " << [Link]() << " seconds.\n";

// Parallel sort
std::generate([Link](), [Link](), std::rand); // Reset data
start = std::chrono::high_resolution_clock::now();
std::sort(std::execution::par, [Link](), [Link]());
end = std::chrono::high_resolution_clock::now();
duration = end - start;
std::cout << "Parallel sort took " << [Link]() << " seconds.\n";

return 0;
}//main 69
//STL sequential , parallel and parallel vectorized processing
#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>
#include <chrono>

int main() {
std::vector<int> v = { 4, 2, 3, 1, 5 };
std::vector <int>::iterator i; //iterator

// Sequential sort
auto start = std::chrono::high_resolution_clock::now();
std::sort(std::execution::seq, [Link](), [Link]());
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> durations = end - start;
std::cout << "Sequential sort took " << [Link]() << " seconds.\n";
std::cout<<"\n Sorted vector v is: ";
for (i = [Link](); i != [Link](); i++) std::cout << *i << " ";
std:: cout << std::endl;

// Parallel sort
auto startp = std::chrono::high_resolution_clock::now();
std::sort(std::execution::par, [Link](), [Link]());
auto endp = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> durationp = endp - startp;
std::cout << "Parallel sort took " << [Link]() << " seconds.\n";

// Parallel and vectorized sort

auto startpv = std::chrono::high_resolution_clock::now();
std::sort(std::execution::par_unseq, [Link](), [Link]());
auto endpv = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> durationpv = endpv - startpv;
std::cout << "Parallel and vectorized sort took " << [Link]() << " seconds.\n";
return 0; 70
}//main
• Functional behavior is something that can be called by using brackets and
arguments, e. g.:
function(arg1, arg2); //a function call
• So, if we want the objects to behave in this way, we must make it possible to
call them, using the brackets and the arguments.
• So, all you need to do is to define the operator( ) as overloading operator,
with the appropriate parameter, for example:
class XYZ {
public:
//define "function call" operator
return-value operator( ) (arguments) const;
...
};//XYZ

Now you can use objects in this class to behave as a function and can call:
XYZ foo;
...
//call operator( ) for function object foo
foo(arg1, arg2); //object called as a function

Calling equivalent with:

//call operator( ) for function object foo
[Link]( ) (arg1, arg2); 72
 Base function object example:
//function object example
//PrintSomething.h
//simple function object that prints the passed argument
class PrintSomething
{
public:
void operator( ) (int elem) const {
cout << elem << " ";
}
};// PrintSomething class

//main
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
constexpr int dim =10;
#include "PrintSomething.h"

int main( ){
vector<int> vec;
//insert elements from 1 to dim
for(int i=1; i<=dim; ++i)
vec.push_back(i);
//print all elements
for_each ([Link]( ), [Link]( ), PrintSomething( )); //range operation
cout<<endl; 73
}//main
• The PrintSomething class defines objects for which the operator can call ( )
with an int argument, elem.
• Expression:
PrintSomething( )
• In construction:
for_each([Link]( ), [Link]( ), PrintSomething( ));
• Create a temporary object of this class, which is passed to the for_each( )
algorithm as an argument.

The for_each(… ) algorithm is written as follows:

namespace std{
template <typename Iterator, typename Operation>
Operation for_each(Iterator act, Iterator end, Operation op)
{
while(act != end)
{ //as long as not reached the end
op(*act); //call op( ) for actual element
act++; //move iterator to the next element
}
return op;
74
}//for_each
• The main uses of Function objects are related to data generation, data testing
(predicates) and operations. They are faster than normal functions.
• There are also predefined function objects such as for sorting, or numerical
processing.
• Function objects are generalizations of the concept of function;
• They take the place of pointers to functions from traditional C/C++ programming;
• They are frequently used as the generic parameter of an algorithm to indicate an
operation that is executed for certain elements in the data structure.
Generators
• There are algorithms that go through a domain by calling a function object at each step
and assigning the result to the current element. In this case we have a generator.
Predicates (data testing)
• They are used to test certain conditions. The ( ) bracket must be overloaded to return
something that can be tested.
• Algorithms that have the suffix _if use a function object to test each element for a
condition.
• A simple predicate dereferences a single element for tests and a binary predicate
(BinaryPredicate) deferens two elements to compare them.
• Finding an element that satisfies a predicate can be defined as follows:

vector <int> vi;

vector <int> :: iterator p= find_if ([Link]( ), [Link]( ), Less_than <int> (7));
if (p!= [Link]( ){cout<<"We found val. < 7 in vi";}
else {cout <<"We did not found val. < 7 in vi";} 75
 What are the most common mistakes
developers make when using the Standard
Template Library (STL) in C++?
• Here are some mistakes concerning STL specified by Kurt Guntheroth:
• Assuming that unordered_map is very fast because it is a hash table. In actual
measurements it was only about twice as fast as map on a table of 100,000
strings.
• Using list, map, or deque when they might get better performance out of vector.
• Not providing move assignment operator and move constructor, and not making
these nothrow when defining item types for vector and deque.
• Not looking at other container classes beyond the STL. boost::circular_buffer is
almost as fast as vector, has efficient insertion and deletion at both ends, and
other useful properties. Here is a nifty article about it.
• Searching map and unordered_map twice when you want to put a new entry in
if it isn’t already in. There’s a coding idiom that only searches once.
• Not estimating the size of a vector or string, and reserving space for the
estimated size. This saves a ton of reallocation, creating a noticeable speed
difference. Constant-time growth.
76