Introduction to STL

Introduction to STL

The birth of STL

The Standard Template Library (STL) was conceived and developed primarily by Alexander Stepanov in the early 1980s. He began his work on generic programming and library design while at the Moscow Soviet Academy of Sciences and continued it at Bell Labs in the United States. A pivotal moment came in 1993 when Stepanov, along with Meng Lee at HP Labs, presented the core ideas of what would become the STL to the ISO C++ committee. The committee's enthusiastic reception led to its rapid inclusion and standardization in the C++98 standard. The STL's foundation lies in the principles of generic programming, providing a set of efficient, reusable algorithms and data structures, fundamentally changing how C++ software is developed.

• For a long time, the software industry has sought to establish something reusable.
• The object-oriented and generic programming concepts in C++ aim to enhance reusability.
• In most cases, data structures and algorithms lack a standardized framework, forcing developers into a lot of repetitive work.
• To establish a standard for data structures and algorithms, STL was created.
  ​

Basic concepts of STL

• STL (Standard Template Library, Standard Template Library)
• STL is broadly divided into: container, algorithm, iterator
• Containers and algorithms are seamlessly connected through iterators.
• Almost all STL code uses template classes or template functions.

Six Major Components of STL

STL can be broadly divided into six major components, namely: containers, algorithms, iterators, functors, adapters (also known as adaptors), and allocators.

1. Containers: various data structures such as vector, list, deque, set, map, etc., used to store data.
2. Algorithms: Various commonly used algorithms, such as sort, find, copy, for_each, etc.
3. Iterators serve as the glue between containers and algorithms.
4. Functor: behaves like a function and can serve as a certain strategy for algorithms.
5. Adapter: A thing used to modify the interface of a container, functor, or iterator.
6. Allocator: responsible for the allocation and management of space.

Containers, algorithms, and iterators in the STL.

Container: a place to store things

STL containers implement the most commonly used data structures.

Common data structures: arrays, linked lists, trees, stacks, queues, sets, hash maps, etc.

These containers are divided into two types: sequence containers and associative containers.

Sequence Containers: Emphasize the ordering of values, where each element in a sequence container has a fixed position. Associative containers: Binary tree structures with no strict physical ordering between elements.

Algorithm: A way to solve problems.

A discipline that solves logical or mathematical problems using a finite number of steps is called algorithms (Algorithms).

Algorithms are categorized into:qualitative change algorithms and non-qualitative change algorithms.

Transforming Algorithms: algorithms that modify the content of elements within a range during execution. Examples include copying, replacing, deleting, and so on.

Non-mutating algorithms: refer to operations that do not change the content of elements within a range during the process, such as searching, counting, traversing, finding extreme values, and so on.

Iterator: The glue between containers and algorithms

This is achieved through the implementation of an Iterator pattern.

Each container has its own exclusive iterator.

Iterators are used very similarly to pointers; in the initial learning phase, we can first understand iterators as pointers.

Types of iterators:

The common types of iterators used in containers are bidirectional iterators and random access iterators.

Intro to Containers, Algorithms, and Iterators

After understanding the concepts of containers, algorithms, and iterators in STL, we'll explore the charm of STL using code.

The most commonly used container in STL is Vector, which can be thought of as an array. Below, we will learn how to insert data into this container and traverse it.

vector stores built-in data types

Container: vector

Algorithm: for_each

Iterator: vector<int>::iterator

Example:

#include <vector>
#include <algorithm>

void MyPrint(int val)
{
    cout << val << endl;
}

void test01() {

    //创建vector容器对象，并且通过模板参数指定容器中存放的数据的类型
    vector<int> v;
    //向容器中放数据
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    //每一个容器都有自己的迭代器，迭代器是用来遍历容器中的元素
    //v.begin()返回迭代器，这个迭代器指向容器中第一个数据
    //v.end()返回迭代器，这个迭代器指向容器元素的最后一个元素的下一个位置
    //vector<int>::iterator 拿到vector<int>这种容器的迭代器类型

    vector<int>::iterator pBegin = v.begin();
    vector<int>::iterator pEnd = v.end();

    //第一种遍历方式：
    while (pBegin != pEnd) {
        cout << *pBegin << endl;
        pBegin++;
    }

    
    //第二种遍历方式：
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    //第三种遍历方式：
    //使用STL提供标准遍历算法  头文件 algorithm
    for_each(v.begin(), v.end(), MyPrint);
}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Vectors for Storing Custom Data Types

A std::vector in C++ can hold elements of any data type, including custom-defined structures or classes. To use a custom type with a vector, you must ensure the type has a default constructor if you plan to resize the vector or use methods like push_back.

Here is a basic example:

#include <iostream>
#include <vector>
#include <string>

// Define a custom data structure
struct Student {
    std::string name;
    int id;
};

int main() {
    // Declare a vector that stores Student objects
    std::vector<Student> classList;

    // Add elements to the vector
    classList.push_back({"Alice", 1001});
    classList.push_back({"Bob", 1002});
    classList.push_back({"Charlie", 1003});

    // Access and print elements
    for (const auto& student : classList) {
        std::cout << "Name: " << student.name << ", ID: " << student.id << std::endl;
    }

    // You can also use other vector operations
    classList.pop_back(); // Remove the last element
    std::cout << "Size after pop_back: " << classList.size() << std::endl;

    return 0;
}

Key Points:

• Vectors manage their own memory, so they grow dynamically as you add elements.
• The custom type (here, Student) can be a struct, class, or even another complex type.
• You can initialize vector elements using aggregate initialization (as shown) or by providing a constructor for your custom type.
• Remember that operations like push_back may require copying elements, so consider implementing move semantics for efficiency with larger objects.

Learning objective: Store custom data types in a vector and print and output them

Example:

#include <vector>
#include <string>

//自定义数据类型
class Person {
public:
    Person(string name, int age) {
        mName = name;
        mAge = age;
    }
public:
    string mName;
    int mAge;
};
//存放对象
void test01() {

    vector<Person> v;

    //创建数据
    Person p1("aaa", 10);
    Person p2("bbb", 20);
    Person p3("ccc", 30);
    Person p4("ddd", 40);
    Person p5("eee", 50);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);
    v.push_back(p5);

    for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
        cout << "Name:" << (*it).mName << " Age:" << (*it).mAge << endl;

    }
}

//放对象指针
void test02() {

    vector<Person*> v;

    //创建数据
    Person p1("aaa", 10);
    Person p2("bbb", 20);
    Person p3("ccc", 30);
    Person p4("ddd", 40);
    Person p5("eee", 50);

    v.push_back(&p1);
    v.push_back(&p2);
    v.push_back(&p3);
    v.push_back(&p4);
    v.push_back(&p5);

    for (vector<Person*>::iterator it = v.begin(); it != v.end(); it++) {
        Person * p = (*it);
        cout << "Name:" << p->mName << " Age:" << (*it)->mAge << endl;
    }
}

int main() {

    test01();
    
    test02();


    return 0;
}

Running/Observing the results: After running, the example will print variable values or addresses; address values depend on the runtime environment, so focus on observing the relative positioning and pointer changes of similar objects.

Vector containers nesting containers

Learning Objective: Containers nested within containers, we will traverse and output all the data.

Example:

#include <vector>

//容器嵌套容器
void test01() {

    vector< vector<int> >  v;

    vector<int> v1;
    vector<int> v2;
    vector<int> v3;
    vector<int> v4;

    for (int i = 0; i < 4; i++) {
        v1.push_back(i + 1);
        v2.push_back(i + 2);
        v3.push_back(i + 3);
        v4.push_back(i + 4);
    }

    //将容器元素插入到vector v中
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);
    v.push_back(v4);

    for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++) {

        for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++) {
            cout << *vit << " ";
        }
        cout << endl;
    }

}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.