Skip to content

Wiki

Introduction to STL

About 8 min read

Existing English translations were reused. 1 current source blocks remain in Simplified Chinese, without triggering paid translation.

1.Introduction to STL

1.1.The Birth of STL

  • For a long time, the software community has hoped to establish something reusable

  • C++'sobject-orientedandgeneric programmingideas, with the goal ofimproving reusability

  • In most cases, data structures and algorithms have lacked a standard, forcing people to undertake a great deal of repetitive work

  • To establish a standard for data structures and algorithms, there was bornSTL

    ​

1.2.Basic Concepts of STL

  • STL (Standard Template Library,Standard Template Library)
  • Broadly speaking, STL is divided into:containers, algorithms, and iterators.
  • Containersandalgorithmsare seamlessly connected throughiterators.
  • Almost all STL code uses template classes or template functions.

1.3.Six Major Components of STL

STL is broadly divided into six major components, namely:containers, algorithms, iterators, functors, adapters, 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: act as the glue between containers and algorithms.
  4. Functors: behave similarly to functions and can serve as a certain strategy for algorithms.
  5. Adapters: something used to modify the interface of a container, functor, or iterator.
  6. Allocators: responsible for space allocation and management.

1.4.Containers, algorithms, and iterators in the STL

**Container:** A place for storing things

STLcontainersare simplysome of the most widely used data structuresimplemented

Common data structures: arrays, linked lists, trees, stacks, queues, sets, mapping tables, etc.

These containers are divided intosequential containersandassociative containers, two types:

​ Sequential containers: Emphasize the ordering of values; each element in a sequential container has a fixed position. Associative containers: Binary tree structure; there is no strict physical sequential relationship between elements.

**Algorithm:** The solution to a problem

A finite sequence of steps to solve a logical or mathematical problem; this discipline is called Algorithms.

The algorithms are divided into:mutating algorithmsandnon-mutating algorithms.

Mutating algorithms: refer to operations that modify the contents of elements within a range during computation. For example, copy, replace, remove, and so on.

Non-mutating algorithms: refer to operations that do not change the contents of elements within a range during computation, such as search, count, traversal, finding extremes, and so on.

**Iterator:** The adhesive between containers and algorithms

Provide a method that enables sequential access to the individual elements of a container without exposing the container's internal representation.

Each container has its own dedicated iterator.

The use of iterators is very similar to pointers; at the beginner stage, we can first understand iterators as pointers.

Iterator types:

种类 功能 支持运算
输入迭代器 对数据的只读访问 只读，支持++、==、！=
输出迭代器 对数据的只写访问 只写，支持++
前向迭代器 读写操作，并能向前推进迭代器 读写，支持++、==、！=
双向迭代器 读写操作，并能向前和向后操作 读写，支持++、--，
随机访问迭代器 读写操作，可以以跳跃的方式访问任意数据，功能最强的迭代器 读写，支持++、--、[n]、-n、<、<=、>、>=

The iterator types commonly found in containers are bidirectional iterators and random access iterators.

1.5.Introduction to Container Algorithms and Iterators

After understanding the concepts of containers, algorithms, and iterators in STL, let's use code to experience the charm of STL.

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

1.5.1.Vector stores built-in data types

Container: vector

Algorithm: for_each

Iterator: vector<int>::iterator

Example:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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;
}

Operation result:

10
20
30
40
10
20
30
40

10
20
30
40

1.5.2.Storing custom data types in Vector

Learning objective: store custom data types in a vector and print the output

Example:

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

using namespace std;

//自定义数据类型
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;
}

Operation result:

Name:aaa Age:10
Name:bbb Age:20
Name:ccc Age:30
Name:ddd Age:40
Name:eee Age:50
Name:aaa Age:10
Name:bbb Age:20
Name:ccc Age:30
Name:ddd Age:40
Name:eee Age:50

1.5.3.Vector container nesting container

Learning objective: containers nested within containers; we will traverse and output all data.

Example:

#include <iostream>
#include <vector>

using namespace std;

//容器嵌套容器
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;
}

Operation result:

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7