STLs I
Agenda
1. Introduction
○ What is an Algorithm?
○ What is a Data Structure (Container)?
○ Components of Data Structure
○ Components of C++ STL
2. Sequential containers
○ Array
■ Array Properties
○ Vector
■ Vector Properties
■ Vector Constructors
■ Vector Common Operations
■ Vector Common Operations (Shared on all STL containers)
■ Vector Traversing
○ Deque
■ Deque Properties
■ Deque Common Operations
3. Comparison between some Containers
Introduction
STLs (Standard Template Libraries) are a set of tools that assist with
implementing a wide range of data structures and algorithms in C++
programming. Before we dive into the details of STL and its components, it's
important to understand the most significant benefits of using STL which is the
availability of data structures and algorithms.
● What is an Algorithm?
An algorithm is a step-by-step procedure that describes how to solve a
problem or perform a task. Think of it as a recipe for solving a problem.
Just as a recipe tells you how to prepare a meal, an algorithm tells you
how to solve a problem. To create an algorithm, you need to first identify
the problem you want to solve. You then need to break the problem down
into smaller, more manageable steps. Each step should be clear and
unambiguous so that anyone following the algorithm can understand what
they need to do. Once you have identified the steps, you can start to
implement the algorithm. It's important to test the algorithm to make sure
it works as expected and to refine it as necessary. One of the most
important things to keep in mind when creating an algorithm is to make it
as efficient as possible. This means finding the fastest and most effective
way to solve the problem.
● What is a data structure (Container)?
When we solve a problem or develop a program, we usually need to
collect data from the user as input. To manipulate this data effectively, we
first need to store it in memory. However, if the user provides millions of
integers, we cannot create millions of variables to store the input. This is
where data structures come into play. They define a set of rules for
organizing and storing the data, ensuring that it is readily available for
processing at a later stage. Without a well-defined data structure,
accessing or modifying the input data effectively would be difficult.
Additionally, data structures enable us to optimize memory usage by
allocating only the required amount of memory to store the data.
Ultimately, using data structures allows us to process input data more
efficiently, leading to faster and more effective program execution.
● Components of Data Structures
Data structures typically consist of four components:
1. Data values: The representation of the actual information being
stored.
2. Relations: The links between the data values.
3. Operations: The allowable manipulations on the data.
4. Constraints: The valid limitation (Size of the data that could be
stored) of the data structure.
One example of data structures is Arrays, they are an important data
structure in programming and are widely used and provided in many
programming languages. However, there are many other data structures
that support a variety of algorithms and applications. While these data
structures are significant, their implementation can be challenging. To
simplify this process, the developers of C++ have included common data
structures as part of the C++ Standard Template Libraries (STL). With the
STL, we can access a set of Black Box (pre-defined) data structures and
algorithms, making it easier for us to solve complex problems efficiently.
Overall, Data structures serve as tools to store and manipulate the data
(Containers) that are utilized in specific algorithms to address problem
requirements. They are not the solution to the problem in its entirety, but
rather a part of it. The choice of data structure will rely heavily on the
problem being solved and the operations that must be carried out on the
data. Choosing the appropriate data structure would help us to optimize
the performance, resulting in a more efficient and effective solution.
However, no data structure is perfect, each comes with its own set of pros
and cons. Selecting the wrong one can cause our program to run too
slowly or use too much memory, but fortunately, we will learn together
how to pick the ideal data structure that satisfies the problem
requirements.
● Components of C++ STL
There are three main components of the C++ STL:
1. Containers: The data structures
2. Algorithms: Common algorithms to be used with the data
structures (Sort function, find function, etc.)
3. Iterators: Provide a means for accessing and traversing data stored
in the data structure.
We can say that STL is a set of C++ template classes to provide common
programming data structures and functions.
We now have a solid foundation that enables us to dive deeper into the
topic. Our next step is to examine specific containers and their
corresponding iterators to gain a more comprehensive understanding.
C++ provides a variety of containers that can be used to store and
manipulate data. These containers are implemented as classes and
templates that provide a variety of operations for manipulating the
elements they contain. Here are the main containers available in C++:
○ Sequential Containers.
○ Container Adaptors.
○ Associative Containers.
○ Unordered Containers.
Sequential containers
Sequence containers are a type of container that stores elements in a linear
sequence. This means that elements are stored in the order they were inserted,
and they can be accessed by their position in the container.
Sequential containers are divided into:
● Array
● Vector
● Deque
● Array
int arr[3];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
Is an array considered a data structure? Yes, it is considered a data structure
because an array is a collection of elements of the same data type stored in
contiguous memory locations. It provides random access to its elements using
an index or a subscript, making it a very basic and fundamental data structure.
Arrays are used extensively in programming for storing and manipulating data
efficiently and are a fundamental building block for more complex data
structures.
Unfortunately, the number of operations applicable to arrays is limited due to
their fixed (static) size. Assuming we have an array of size 100 and we want to
add a new element, we would need to initialize a new array with a size of 101,
copy the old 100 elements, and add the new element at index 100 (0-based).
Erasing follows the same criteria. When searching for a specific element in the
array, since arrays do not order the elements, we need to iterate through each
element one by one to find the target, resulting in a time complexity of O(n).
Although other data structures offer better time complexity for these
operations, they come with their own disadvantages, such as the lack of random
access. Therefore, we can see that random access is the most important feature
of arrays.
Array Properties:
Property Array
Size Fixed
Random Access Yes
Search O(N)
Insert NO/new array O(N)
Erase NO/new array O(N)
● Vector
#include <vector>
vector <type> name;
vector <int> v;
A vector is similar to an array, but it offers some additional advantages,
such as the ability to remove or insert an element from the end with a
complexity of O(1). To be more accurate, adding an element to a vector
takes amortized O(1) time. Actually, sometimes when we add an element,
it takes O(1) time, while at other times it takes O(n) time. However, the
number of times it takes O(1) time is much greater than the number of
times it takes O(n) time. Therefore, if we calculate the total number of
operations performed on the vector and divide it by the number of
operations, it will be approximately 2-3 operations, which is considered a
constant time complexity of O(1).
Now, let's discuss the advantages and disadvantages of vectors. The first
advantage is that vectors are dynamic, unlike arrays, which are fixed in
size. Additionally, vectors maintain the random-access property, meaning
that search time is the same as an array. However, when it comes to
insertion and deletion, the time complexity is O(1) when performed from
the end, but O(n) when performed from other positions.
Vector Properties:
Property Vector
Size Dynamic
Random Access Yes
Search O(N)
Insert:
● Front O(N)
● Back O(1)
● Middle O(N)
Erase:
● Front O(N)
● Back O(1)
● Middle O(N)
Vector Constructors:
vector<double> v; // Empty vector
vector<long long> v(5); // Vector
of size 5, initialised with zeros
vector<int> v(5,3); // Vector of
size 5, initialised with threes
Vector Common Operations:
vector<int> v(1, 1);
v.push_back(2);
v.push_back(3);
v.pop_back();
cout << v[0]; // prints 1
v[1] = 11;
cout << v[1]; // prints 11
v = {10, 20, 30, 40, 50};
v.erase(v.begin() + 3);
v.insert(v.begin()+3,100);
Vector Common Operations (Shared on all STL containers)
vector<int> v1(2, 10);
v1.push_back(20);
cout << v1.size(); // prints 3
v1.clear(); // clears the vector
v1.push_back(10);
vector<int> v2(2, 20);
v1.swap(v2);
cout << v1[0]; // prints 20
cout << v2[0]; // prints 10
🞿 VI: Don’t use the swap(x, y) method
v1.swap(v2); //O(1)
swap(v1, v2); //implementation goes like this:
vector<int> temp = v1; //O(n)
v1 = v2; //O(n)
v2 = temp; //O(n)
v1.swap(v2); // swaps the addresses (i.e. the containers
exchange references to their data) of two vectors rather than
swapping each element one by one which is done in constant
time O(1).
Vector Traversing:
vector<int> v = {10, 20, 30, 40, 50};
Iterating through the elements of a vector is a common operation, and
there are several methods to accomplish this task. In the following code
examples, we will explore these methods and highlight the most
frequently used ones among them.
Common Ways:
// array method
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
// range-based method
for (int elem: v)
cout << elem << " ";
Note: Iterators are like pointers. So, to access the value inside them we
need to de-reference using an asterisk (*it).
// forward iterator method
vector<int>::iterator it = v.begin();
while (it != v.end()) {
cout << *it << " ";
it++;
}
// prints: 10 20 30 40 50
// reverse iterator method
vector<int>::reverse_iterator it = v.rbegin();
while(it != v.rend()){
cout << *it << " ";
it++;
}
// prints: 50 40 30 20 10
● Deque
#include <deque>
deque <type> name;
deque <int> d;
A Deque is similar to a vector, but it offers some additional advantages,
which is the ability to remove or insert an element from the beginning
with a complexity of O(1). To be more accurate, adding an element to a
deque’s beginning or end takes amortized O(1) time. (Just the same way
vector works)
Deque Properties:
Property Deque
Size Dynamic
Random Access Yes
Search O(N)
Insert:
● Front O(1)
● Back O(1)
● Middle O(N)
Erase:
● Front O(1)
● Back O(1)
● Middle O(N)
Deque Common Operations:
deque<int> d(2, 2);
d.pop_back();
d.push_back(3);
d.push_front(1);
d.pop_front();
cout << d[0]; // prints 2
d[1] = 11;
cout << d[1]; // prints 11
As we have mentioned before, deque is similar to vector but with two
extra functionalities which are push_front() and pop_front(). Therefore,
there is no need to repeat the discussion as the same concepts apply to
both data structures.
Comparison between some Containers
Property Array Vector Deque
Size Static Dynamic Dynamic
Random
Yes Yes Yes
access
NO/ Back: O(1) Front/Back: O(1)
Insert
new array O(N) Other: O(N) Other: O(N)
NO/ Back: O(1) Front/Back: O(1)
Erase
new array O(N) Other: O(N) Other: O(N)
Ordering Ordered Ordered Ordered
Used when Used when
frequent frequent
Used when storing
insertion/deletion insertion/deletion
Usage data with a static
in the middle or is required in
size is required
random access is front/back or
needed middle
Note: The "ordering" row indicates whether the container preserves the order in
which elements were inserted.
