目录结构
1. STL概念
1.2 常见容器
1.3 六大组件
2. STL容器之vector
1. vector
2. 基本用法示例
3. STL容器之map
1. map
2. 基本用法示例
1. STL概念
C++中的STL是指标准模板库的缩写。STL提供了一组通用的模板类和函数,用于实现常见的数据结构和算法,如向量(vector)、链表(list)、栈(stack)、队列(queue)、映射(map)等,以及包括排序、搜索、算法等在内的各种算法操作。
1.2 常见容器
- vector:动态数组,支持快速随机访问。
- list:双向链表,支持高效插入和删除操作。
- stack:栈,后进先出(LIFO)数据结构。
- queue:队列,先进先出(FIFO)数据结构。
- map:映射,键-值对的关联容器。
1.3 六大组件
容器(Containers):容器是STL的核心组件之一,提供了各种数据结构,如向量(vector)、链表(list)、双端队列(deque)、栈(stack)、队列(queue)、映射(map)等。容器用于存储和组织数据,不同类型的容器适用于不同的数据访问和操作需求。
算法(Algorithms):STL包含了一系列通用算法,用于操作容器中的数据,例如排序、查找、复制、变换等。这些算法是高度优化的,可适用于不同类型的容器,使开发人员能够更轻松地进行常见操作。
迭代器(Iterators):迭代器是用于访问容器中元素的通用接口。它们提供了统一的方法来遍历容器,并使算法能够与不同类型的容器一起使用,而不需要了解底层容器的细节。
仿函数(Function Objects):仿函数是可调用对象,它们在STL中用于执行特定操作,如排序或变换。STL提供了一些内置的仿函数,同时也允许开发人员定义自己的仿函数,以满足特定需求。
适配器(Adapters):适配器是用于修改或扩展容器和迭代器行为的组件。STL中包括一些适配器,如栈适配器(stack adapter)和队列适配器(queue adapter),它们基于其他容器提供了不同的接口。
配置器(Allocators):配置器用于管理内存分配和释放,以支持容器的底层数据结构。STL提供了默认的配置器,同时也允许开发人员自定义配置器以满足特定的内存管理需求。
2. STL容器之vector
1. vector
std::vector 是 C++ 标准库提供的一个动态数组容器,它可以自动扩展和收缩,使其非常适合存储和管理可变数量的元素。
2. 基本用法示例
2.1 包含头文件
#include <vector>
2.2 创建一个空的 std::vector
std::vector<int> myVector;
2.3 向 std::vector
中添加元素
myVector.push_back(42);
myVector.push_back(23);
myVector.push_back(17);
2.4 访问 std::vector
中的元素
int firstElement = myVector[0];
int secondElement = myVector[1];
2.5 获取 std::vector
的大小
int size = myVector.size();
2.6 遍历 std::vector
中的元素
for (int i = 0; i < myVector.size(); i++) {
std::cout << myVector[i] << " ";
}
2.7 使用范围循环遍历 std::vector
for (int value : myVector) {
std::cout << value << " ";
}
2.8 插入元素到指定位置
myVector.insert(myVector.begin() + 1, 100); // 在第二个位置插入值为100的元素
2.9 删除元素
myVector.erase(myVector.begin() + 1); // 删除第二个元素
2.10 清空 std::vector
myVector.clear();
2.11 示例程序
创建了一个 std::vector
,向其中添加、插入、删除元素,并最后清空了 std::vector
。
#include <iostream>
#include <vector>
int main() {
// 创建一个空的 std::vector,用于存储整数
std::vector<int> myVector;
// 向 std::vector 中添加一些整数元素
myVector.push_back(42);
myVector.push_back(23);
myVector.push_back(17);
// 遍历并打印 std::vector 中的元素
for (int value : myVector) {
std::cout << value << " ";
}
std::cout << std::endl;
// 在第二个位置插入值为100的元素
myVector.insert(myVector.begin() + 1, 100);
// 再次遍历并打印 std::vector 中的元素
for (int value : myVector) {
std::cout << value << " ";
}
std::cout << std::endl;
// 删除第二个元素
myVector.erase(myVector.begin() + 1);
// 再次遍历并打印 std::vector 中的元素
for (int value : myVector) {
std::cout << value << " ";
}
std::cout << std::endl;
// 清空 std::vector
myVector.clear();
// 打印 std::vector 的大小(应该为0)
std::cout << "Vector size: " << myVector.size() << std::endl;
return 0;
}
2.12 std::vector
的简化版源码示例
该简化的 MyVector
类模拟了 std::vector
的基本功能,包括动态数组的管理、元素的添加、访问和扩容等。
#include <iostream>
#include <stdexcept>
template <typename T>
class MyVector {
private:
T* data; // 存储元素的数组
size_t size; // 当前元素数量
size_t capacity; // 数组容量
public:
// 构造函数
MyVector() : data(nullptr), size(0), capacity(0) {}
// 析构函数
~MyVector() {
delete[] data; // 释放内存
}
// 返回元素数量
size_t Size() const {
return size;
}
// 添加元素到尾部
void PushBack(const T& value) {
if (size == capacity) {
// 如果容量不足,扩展数组
if (capacity == 0) {
capacity = 1; // 初始容量为1
} else {
capacity *= 2; // 容量翻倍
}
T* newData = new T[capacity];
for (size_t i = 0; i < size; ++i) {
newData[i] = data[i];
}
delete[] data;
data = newData;
}
data[size] = value; // 添加元素
size++;
}
// 访问元素
T& operator[](size_t index) {
if (index < size) {
return data[index];
} else {
throw std::out_of_range("Index out of range");
}
}
};
int main() {
MyVector<int> myVector;
myVector.PushBack(42);
myVector.PushBack(23);
myVector.PushBack(17);
for (size_t i = 0; i < myVector.Size(); i++) {
std::cout << myVector[i] << " ";
}
return 0;
}
3. STL容器之map
1. map
在C++的STL(标准模板库)中,
std::map
是一种关联式容器,用于存储键-值对。它按照键的顺序进行排序,并且具有快速查找功能。
2. 基本用法示例
1. 包含头文件
#include <map>
2. 创建一个空的 std::map
std::map<std::string, int> myMap;
3. 向 std::map
中插入键值对
myMap["Alice"] = 25;
myMap["Bob"] = 30;
myMap["Charlie"] = 35;
4. 访问 std::map
中的值
int age = myMap["Alice"];
5. 使用迭代器遍历 std::map
中的键值对
for (const auto& pair : myMap) {
std::cout << "Name: " << pair.first << ", Age: " << pair.second << std::endl;
}
6. 检查 std::map
中是否包含特定的键
if (myMap.find("Alice") != myMap.end()) {
std::cout << "Alice is in the map." << std::endl;
}
7. 示例程序示例程序创建了一个 std::map
,向其中添加键值对,访问键值对的值,并检查特定的键是否存在。
#include <iostream>
#include <map>
#include <string>
int main() {
// 创建一个空的 std::map,用于存储名字和年龄的关联关系
std::map<std::string, int> myMap;
// 向 std::map 中插入键值对
myMap["Alice"] = 25;
myMap["Bob"] = 30;
myMap["Charlie"] = 35;
// 使用迭代器遍历 std::map 中的键值对
for (const auto& pair : myMap) {
std::cout << "Name: " << pair.first << ", Age: " << pair.second << std::endl;
}
// 访问特定键的值
int age = myMap["Alice"];
std::cout << "Alice's age is " << age << std::endl;
// 检查特定键是否存在于 std::map 中
if (myMap.find("Alice") != myMap.end()) {
std::cout << "Alice is in the map." << std::endl;
}
return 0;
}
以下是 std::map
的简化版源码示例,用于说明其基本工作原理。
std::map
是 C++ 标准库提供的关联容器,它实际上是一个基于红黑树的有序关联容器,用于存储键值对,并能够按键的排序顺序进行访问。这个简化的 MyMap
类模拟了 std::map
的一些基本功能,包括插入和查找键值对。在实际的 std::map
实现中,还包括了红黑树平衡操作等,以确保高效的键值对查找和维护有序性。
#include <iostream>
#include <string>
template <typename Key, typename Value>
class MyMap {
private:
struct Node {
Key key;
Value value;
Node* left;
Node* right;
Node* parent;
bool isRed; // 红黑树节点颜色标志
};
Node* root; // 根节点
// 插入节点的内部辅助函数
void InsertNode(Node*& node, const Key& key, const Value& value) {
if (node == nullptr) {
node = new Node{key, value, nullptr, nullptr, nullptr, true};
// 红黑树插入后需要修复
// (在实际的 std::map 实现中,这里包括了平衡操作,以确保树的平衡性)
} else {
if (key < node->key) {
InsertNode(node->left, key, value);
} else if (key > node->key) {
InsertNode(node->right, key, value);
} else {
// 如果键已存在,更新值
node->value = value;
}
}
}
// 查找节点的内部辅助函数
Node* FindNode(const Key& key, Node* node) {
if (node == nullptr || key == node->key) {
return node;
}
if (key < node->key) {
return FindNode(key, node->left);
} else {
return FindNode(key, node->right);
}
}
public:
MyMap() : root(nullptr) {}
// 插入键值对
void Insert(const Key& key, const Value& value) {
InsertNode(root, key, value);
}
// 查找键对应的值
Value Find(const Key& key) {
Node* node = FindNode(key, root);
if (node != nullptr) {
return node->value;
} else {
// 返回默认值,可以根据需求修改
return Value();
}
}
};
int main() {
MyMap<std::string, int> myMap;
myMap.Insert("Alice", 25);
myMap.Insert("Bob", 30);
myMap.Insert("Charlie", 35);
int age = myMap.Find("Alice");
std::cout << "Alice's age is " << age << std::endl;
return 0;
}