泛型编程

泛型编程是一种编程方法，它允许程序员编写通用的代码，即可适用于不同的数据类型，而不必为每种类型编写不同的代码。这种编程方法的基本思想是将数据类型抽象化，使用泛型来表示数据类型，并在编写代码时使用泛型来代替具体的数据类型。

Java、C#等编程语言都支持泛型编程。在Java中，泛型可以用于类、接口、方法等，可以确保代码的类型安全，并提高代码的重用性和可读性。泛型编程可以用于各种领域，例如集合类、算法实现、

什么是STL

STL是C++标准库中的一个模板库，它提供了一系列的通用数据结构和算法，包括容器、迭代器、算法、函数对象等等。STL 的全称是 Standard Template Library（标准模板库），它是C++程序员经常使用的一个工具箱。STL 的主要目的是提高开发效率和代码质量，使得程序员可以更加便捷地完成常见的操作。

STL发展

STL是一种C++的标准库，用于实现常用的数据结构和算法。它的发展历程可以从以下几个方面来讨论：

  1.早期版本：STL最初由Alexander Stepanov和Meng Lee于1994年开发，最初被称为SGI STL（Silicon Graphics Inc. STL）。它的目的是为了在C++中提供高效的数据结构和算法的实现，大大简化了C++程序的开发。早期版本的STL包含容器、迭代器、算法、函数对象等组件。

  2.标准化：由于STL在C++社区中的广泛应用，它于1998年正式被纳入C++标准库中。这一标准化使得STL更加稳定和可靠，成为C++程序员必备的工具之一。

  3.扩展和优化：随着C++标准的不断更新，STL也不断得到扩展和优化。例如，C++11标准中新增了多线程支持，同时STL也在容器、迭代器、算法等方面得到了进一步扩展和优化。此外，一些开源社区也提供了STL的优化版本，如boost库、Eastl等。

  4.应用领域：STL在软件开发中有广泛的应用，包括游戏开发、图形处理、科学计算、数据挖掘等领域。尤其在高性能和高并发的系统开发中，STL的应用更加广泛。

总的来说，STL的发展历程是一个不断完善和拓展的过程，它为C++程序员提供了强大的工具，极大地提高了程序开发效率和性能。

STL组件

STL（标准模板库）是C++的一个重要组件，它是由一组通用的模板类和函数组成的，并且提供了一些常用的数据结构和算法，如动态数组（vector）、链表（list）、集合（set）、映射（map）、排序、查找等。STL的设计思想是将数据结构和算法进行分离，使得它们可以独立使用和扩展，提高了代码的复用性和可读性。

STL主要包含以下组件：

  1 .容器（Containers）：动态数组（vector）、链表（list）、双端队列（deque）、队列（queue）、堆栈（stack）、集合（set）、映射（map）等。

  2 .迭代器（Iterators）：是一种抽象的数据类型，可用于访问容器中的元素，STL提供了五种迭代器类型，包括输入迭代器（Input Iterator）、输出迭代器（Output Iterator）、前向迭代器（Forward Iterator）、双向迭代器（Bidirectional Iterator）和随机访问迭代器（Random Access Iterator）。

  3 .算法（Algorithms）：STL提供了大量的常用算法，包括排序、查找、合并、去重、计数、查找等等。

  4 .函数对象（Function Objects）：STL中的函数对象是一种封装了函数或函数指针的对象，它可以像函数一样被调用，也可以像对象一样被赋值或传递给其他函数，常用的函数对象有谓词（Predicate）和函数适配器（Function Adapters）。

  5 .适配器（Adaptors）：STL提供了一些适配器，用于将一些数据结构转换为另一些数据结构，包括容器适配器（Container Adaptors）、迭代器适配器（Iterator Adapters）和函数适配器（Function Adapters）。

容器

STL（Standard Template Library）是C++中的一种标准库，它提供了多种容器类型用于存储数据。下面是STL容器的一些常见类型：

   1.vector：可以动态调整大小的数组，支持快速的随机访问和迭代器访问，并且支持在尾部添加或删除元素。

   2.deque：双端队列，支持快速的随机访问和迭代器访问，并且支持在头部和尾部添加或删除元素。

   3.list：双向链表，只支持迭代器访问，并且支持在任意位置添加或删除元素。

   4.set：有序集合，其中每个元素都是唯一的，支持快速的查找和插入操作。

   5.map：有序映射，其中每个元素都有一个唯一的键值对，支持快速的查找和插入操作。

   6.unordered_set：无序集合，其中每个元素都是唯一的，支持快速的查找和插入操作，但元素的顺序是未定义的。

   7.unordered_map：无序映射，其中每个元素都有一个唯一的键值对，支持快速的查找和插入操作，但元素的顺序是未定义的。

以上仅是STL容器的一部分，其中还包括stack、queue、priority_queue等等。不同的容器类型适用于不同的使用场景，需要根据实际情况进行选择。

类型成员

STL中的类型成员是指类型别名，这些类型别名被定义在各个STL组件中，用于简化代码和提高可读性。以下是一些常用的STL类型成员：

1.value_type：表示容器中元素的类型。

2.allocator_type：表示容器使用的内存分配器的类型。

3.difference_type：表示两个迭代器之间的距离所使用的类型。

4.size_type：表示容器的大小的类型。

5.key_type：表示关联容器中键的类型。

6.mapped_type：表示关联容器中值的类型。

7.pointer：表示指向容器中元素的指针类型。

8.reference：表示容器中元素的引用类型。

9.iterator：表示容器的迭代器类型。

10.const_iterator：表示容器的只读迭代器类型。

11.reverse_iterator：表示容器的反向迭代器类型。

12.const_reverse_iterator：表示容器的只读反向迭代器类型。

适配器

STL（Standard Template Library）适配器是一项功能强大的编程技术，用于将一种容器类型适配到另一种容器类型上。STL适配器允许开发人员轻松地使用不同类型的容器，而无需更改代码或重新编写算法。

常见的STL适配器包括：

1.迭代器适配器：将一个迭代器转换为另一个迭代器，例如反向迭代器、插入迭代器和流迭代器。

2.容器适配器：将一种容器类型适配成另一种容器类型，例如stack、queue和priority_queue。

3.函数适配器：将一种函数类型适配成另一种函数类型，例如bind和mem_fn。

STL适配器的优点在于可以提高代码的可重用性和可维护性，同时简化了开发人员的工作。

STL迭代器

STL迭代器是一种用于遍历和访问STL容器（如vector、list等）中元素的对象。它类似于指针，但比指针更灵活。迭代器有不同的类型，每种类型对应不同的容器类型，如输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器等。迭代器可以实现容器中元素的添加、删除、修改和查询操作，使得对于任何STL容器的操作都可以写成通用的代码。使用迭代器可以避免直接操作容器而引起的风险，同时也提高了代码的可复用性和可维护性。

STL算法

STL（Standard Template Library）是一种C++语言的标准库，其中包含了很多常用的数据结构和算法。STL中的算法库提供了很多种算法，可以用来处理各种数据结构，例如数组、列表、栈、队列等等。以下是STL中常用的算法：

1.查找算法：find、find_if、binary_search等

2.排序算法：sort、stable_sort、partial_sort等

3.操作算法：copy、swap、reverse等

4.数值算法：accumulate、inner_product、partial_sum等

5.集合算法：merge、set_union、set_intersection等

6.变异算法：transform、replace、remove等

7.分类算法：partition、stable_partition、is_sorted等

STL算法库的使用非常方便，只需要include相应的头文件就可以了，如#include。STL算法的时间复杂度和空间复杂度均已经得到了优化，因此在面对大规模数据处理时，使用STL算法库可以大大提高程序的效率。

顺序容器

STL顺序容器是指能够按照元素的顺序存储和访问元素的容器，包括以下几种：

1.vector：动态数组，支持在末尾添加和删除元素，也支持随机访问。

2.deque：双端队列，支持在两端添加和删除元素，也支持随机访问。

3.list：双向链表，支持在任意位置添加和删除元素，但不支持随机访问。

4.forward_list：单向链表，支持在任意位置添加和删除元素，但不支持随机访问。

5.array：静态数组，固定大小，不支持添加和删除元素，但支持随机访问。

这些容器都是通过模板类实现的，可以存储各种类型的元素。它们都提供了一些常用的操作方法，如访问元素、添加和删除元素、查找元素等。开发者可以根据具体的需求选择合适的容器进行使用。

向量vector

向量（vector）是指在数学中，一个由数量（也可称为标量）组成的有序组，常用于表示物理量的大小和方向。常见的向量表示方式为箭头表示法，箭头的长度表示数量的大小，箭头的方向表示向量的方向。

向量可以进行加法、减法、数量乘法和点乘等运算，在三维空间中向量可以表示为一个由三个实数组成的有序组。向量在物理学、工程学、计算机科学、经济学等领域都有广泛的应用。

双端队列

双端队列（Double-ended Queue，缩写为Deque）是一种具有队列和栈的性质的数据结构。它支持在两端进行插入和删除操作，因此可以从队列和栈两个方向来操作数据。在双端队列中，可以在队列的头部和尾部添加或删除元素。

双端队列同样支持队列的先进先出（FIFO）特性，因此可以作为一个队列来使用。同时，由于它支持栈的后进先出（LIFO）特性，因此也可以作为一个栈来使用。

在Python中，双端队列可以通过标准库collections中的deque类来实现。它支持的操作包括从队列头部和尾部进行添加和删除操作，以及队列元素的访问、查找、计数和翻转等。

双端队列实现

双端队列（Double Ended Queue，简称Deque）是一种可以从两端添加、删除元素的线性数据结构。双端队列可以看作是栈和队列的结合体，支持在队列头和队列尾进行插入和删除操作。

双端队列的实现可以用数组或链表来实现。以下是使用数组实现的双端队列示例代码：

class Deque:
    def __init__(self):
        self.items = []
    def add_front(self, item):
        """在队头添加元素"""
        self.items.insert(0, item)
    def add_rear(self, item):
        """在队尾添加元素"""
        self.items.append(item)
    def remove_front(self):
        """在队头删除元素"""
        if self.is_empty():
            return None
        return self.items.pop(0)
    def remove_rear(self):
        """在队尾删除元素"""
        if self.is_empty():
            return None
        return self.items.pop()
    def is_empty(self):
        """判断队列是否为空"""
        return len(self.items) == 0
    def size(self):
        """返回队列大小"""
        return len(self.items)

在上述代码中，我们使用 Python 的内置列表作为底层数据结构来实现双端队列。具体实现方式如下：

add_front 方法使用 list.insert() 在队头添加元素。

add_rear 方法使用 list.append() 在队尾添加元素。

remove_front 方法使用 list.pop(0) 删除队头元素。

remove_rear 方法使用 list.pop() 删除队尾元素。

is_empty 方法通过 len() 判断队列是否为空。

size 方法通过 len() 返回队列大小。

这是双端队列的基本实现，稍加修改即可用链表实现。

列表list

C++中的列表（list）是一个双向链表，它是一个STL标准库提供的容器类型，可以在程序中使用。列表可以存储多个元素，可以在任意位置插入或删除元素，也可以对其进行遍历。

以下是列表的一些常用操作：

1. 1.创建列表：可以使用默认构造函数或者将另一个列表作为参数传递给构造函数。

#include <list>
using namespace std;
list<int> mylist; // 创建一个空列表
list<int> mylist2(mylist); // 将 mylist 复制给 mylist2

2. 2.插入元素：可以在列表任意位置插入元素。

mylist.push_back(10); // 在列表尾部插入元素
mylist.push_front(20); // 在列表头部插入元素
list<int>::iterator it = mylist.begin();
advance(it, 2); // 将迭代器移动到第3个元素后面
mylist.insert(it, 30); // 在第3个元素后面插入元素

3. 3.删除元素：可以删除列表的任意一个元素或者一段元素。

mylist.pop_back(); // 删除列表尾部的元素
mylist.pop_front(); // 删除列表头部的元素
list<int>::iterator it = mylist.begin();
advance(it, 2); // 将迭代器移动到第3个元素
mylist.erase(it); // 删除第3个元素
mylist.erase(mylist.begin(), mylist.end()); // 删除整个列表中的元素

4. 4.遍历列表：可以使用迭代器来遍历列表中的元素。

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

以上是常用的一些操作，除此之外，列表还提供了许多其他的操作，如排序、翻转等。

c++关联容器

C++关联容器是一种按照键值对存储元素的容器，其中每个元素都有一个唯一的键值。常见的关联容器包括map、multimap、set和multiset。

map和multimap用于存储键值对，其中map中键值对的键是唯一的，而在multimap中键可以重复出现。set和multiset用于存储唯一的键值，其中set中键是唯一的，而在multiset中键可以重复出现。

关联容器的常见操作包括插入、删除、查找和遍历。插入操作可以使用insert()函数，删除操作可以使用erase()函数，查找操作可以使用find()函数，遍历操作可以使用迭代器实现。关联容器还支持排序、计数和范围查找等高级操作。

关联容器是C++语言中常用的容器之一，适用于需要快速查找和按键排序的场景。

c++map

C++ 中的 map 是一种关联式容器，它将键映射到值。每个键只能对应一个值。map 内部按照一定的顺序存储键值对，通过键可以快速查找对应的值。

map 的使用需要包含头文件 map。以下是一些常用的 map 操作：

1.插入元素：使用 insert() 函数或 [] 运算符，用键值对的形式插入元素。

map<int, string> myMap;
myMap.insert(pair<int, string>(1, "apple"));
myMap[2] = "banana";

2.查找元素：使用 find() 函数查找指定键所对应的值，如果找到返回迭代器，否则返回 map::end 迭代器。

auto it = myMap.find(1);
if (it != myMap.end()) {
   cout << it->second << endl;
}

3.删除元素：使用 erase() 函数删除指定键所对应的键值对。

myMap.erase(1);

4.遍历元素：使用迭代器遍历整个 map。

for (auto it = myMap.begin(); it != myMap.end(); ++it) {
   cout << it->first << " " << it->second << endl;
}

map 内部使用红黑树实现，因此插入、删除、查找操作的时间复杂度均为 O(log n)。需要注意的是，因为 map 内部存储的是键值对，因此在使用迭代器遍历时需要使用 it->first 和 it->second 访问键和值。