wordpress 无法下载主题,WordPress搜索优化工具,常州 做网站,网络平台怎么搭建网站一.简介
std::vector 的底层实现通常基于动态数组#xff08;dynamic array#xff09;#xff0c;它是一种连续分配的内存块#xff0c;允许元素的快速随机访问。下面是 std::vector 的一些关键特点和底层实现细节#xff1a; 连续内存块#xff1a;std::vector 内部使…一.简介
std::vector 的底层实现通常基于动态数组dynamic array它是一种连续分配的内存块允许元素的快速随机访问。下面是 std::vector 的一些关键特点和底层实现细节 连续内存块std::vector 内部使用一块连续的内存块来存储其元素这使得元素的随机访问非常高效因为可以通过指针算术运算来访问元素。 动态大小std::vector 允许动态地增加或减少其大小。当元素数量达到内部分配的容量时std::vector 会重新分配更大的内存块并将元素复制到新的内存块中。这种自动内存管理使得向量的大小可以根据需要进行调整而不需要手动管理内存。 容量和大小std::vector 有两个重要的属性即容量capacity和大小size。 容量是 std::vector 当前内部分配的内存块的大小通常大于或等于大小。当向量的大小超过容量时会触发内存重新分配容量会增加。大小是 std::vector 中实际存储的元素数量。 动态内存分配std::vector 使用 new 和 delete 运算符或 malloc 和 free 函数取决于具体实现来动态分配和释放内存。当需要重新分配内存时它会为新的内存块分配内存然后将元素从旧的内存块复制到新的内存块最后释放旧内存。 异常安全std::vector 的实现通常会提供异常安全性这意味着如果在内存重新分配过程中发生异常不会导致数据丢失或内存泄漏。这是通过使用临时副本和交换技术来实现的。 迭代器std::vector 提供了迭代器iterator来遍历元素迭代器通常是指针的封装可以用于访问 std::vector 中的元素。 内存效率由于 std::vector 的元素存储在连续的内存块中它在内存访问上具有很好的局部性这有助于提高内存访问效率。
总之std::vector 是一个非常灵活和高效的容器它提供了动态数组的功能使得元素的访问和管理变得非常方便。虽然 std::vector 的大小可以动态增长但由于内存重新分配的开销如果需要频繁插入或删除元素可能需要考虑其他容器类型如 std::list 或 std::deque它们可以更高效地支持插入和删除操作。 扩展
动态数组Dynamic Array是一种数据结构它是一个连续分配的内存块用于存储具有相同数据类型的元素。动态数组的大小可以动态增长或缩小以适应元素的插入和删除操作。
以下是动态数组的主要特点和操作 连续内存块动态数组的元素存储在一块连续的内存块中这意味着元素的地址在内存中是连续的这有助于快速随机访问元素。通过索引访问元素的时间复杂度是 O(1)。 动态大小动态数组允许在运行时动态增加或减少其大小。这意味着您可以向数组中添加元素或从数组中删除元素而不需要预先知道数组的大小。这种动态大小的特性使得动态数组非常灵活。 内存分配当向动态数组添加元素并且没有足够的内存容量时动态数组会自动分配更大的内存块将现有元素复制到新的内存块中并释放旧的内存块。这个过程称为重新分配re-allocation。 时间复杂度动态数组的插入和删除操作的时间复杂度取决于插入或删除的位置。在末尾进行插入和删除操作通常是最高效的时间复杂度为 O(1)因为不需要移动元素。在数组中间进行插入或删除操作可能需要移动后续元素时间复杂度为 O(n)。 容量和大小动态数组具有容量capacity和大小size两个重要属性。 容量是动态数组内部分配的内存块的大小通常大于或等于大小。大小是动态数组中实际存储的元素数量。 迭代器动态数组通常提供迭代器iterator可以用于遍历数组中的元素。
动态数组是一种非常常见和有用的数据结构它具有灵活性和高效性的优点。 二.运用场景
std::vector 是 C 标准库提供的一个动态数组容器它在许多不同的场景中都非常有用。以下是一些常见的 std::vector 的运用场景 动态数组std::vector 是一种动态数组它可以根据需要自动增加或减少大小。这使得它成为存储不确定数量元素的首选选择而不需要预先知道数组的大小。 数据收集std::vector 适用于收集大量数据例如从文件、网络或用户输入中读取的数据。您可以使用 push_back() 方法轻松添加新数据。 容器替代std::vector 可以替代 C 数组因为它提供了更多的功能和安全性。与 C 数组不同std::vector 知道自己的大小而且可以动态调整大小。 迭代访问如果需要通过索引或迭代器访问元素并且需要快速随机访问能力std::vector 是一个很好的选择。它的时间复杂度为 O(1)。 栈和队列虽然 std::vector 主要设计用于随机访问但它也可以用作栈先进后出或队列先进先出。使用 push_back() 和 pop_back() 方法可以将其用作栈而使用 push_back() 和 erase() 可以将其用作队列。 算法和数据处理std::vector 与标准库中的各种算法结合使用可以用于各种数据处理任务例如排序、查找、筛选、转换等。 高性能计算在需要高性能的数值计算领域std::vector 通常用于存储大量数值数据例如图形处理、科学计算、模拟等。 游戏开发在游戏开发中std::vector 常用于存储游戏对象、粒子、动画帧等。 数据传输std::vector 可以用于数据传输例如从文件读取数据到向量然后将向量传递给其他处理模块。
需要注意的是虽然 std::vector 在许多情况下非常有用但在某些特定情况下其他容器类型例如 std::list、std::deque、std::set、std::map 等可能更适合特定的数据结构和操作。因此在选择容器类型时需要根据具体的需求和性能要求进行权衡和选择。 三.写个比较器
方法一直接静态函数
#includeiostream
#includevector
#includealgorithm
using namespace std;
static bool cmp(const pairint, int a, const pairint, int b) {if (a.first b.first) return a.second b.second;return a.first b.first;
}
void display(vectorpairint,intans) { for (auto it : ans) cout it.first it.second\t; }
int main() {vectorpairint, intans { {1,2},{5,3},{2,5},{2,1},{7,2} };display(ans);cout endl;sort(ans.begin(), ans .end(), cmp);display(ans);return 0;
}方法二写入结构体
#includeiostream
#includevector
#includealgorithm
using namespace std;
struct cmp {bool operator()(const pairint,inta,const pairint,intb) {if (a.first b.first) return a.second b.second;return a.first b.first;}
};
void display(vectorpairint,intans) { for (auto it : ans) cout it.first it.second\t; }
int main() {vectorpairint, intans { {1,2},{5,3},{2,5},{2,1},{7,2} };display(ans);sort(ans.begin(), ans .end(), cmp());cout ---------- endl;display(ans);return 0;
}在使用的时候cmp() 表示实例化对象要是不想实例化对象怎么办呢这个时候我们可以把比较操作定义成静态成员函数这样就可以通过这个结构体的名称来调用这个函数而不需要实例化对象。
#includeiostream
#includevector
#includealgorithm
using namespace std;
struct numcmp {static bool cmp(const pairint, int a, const pairint, int b) {if (a.first b.first) return a.second b.second;return a.first b.first;}
};
void display(vectorpairint,intans) { for (auto it : ans) cout it.first it.second\t; }
int main() {vectorpairint, intans { {1,2},{5,3},{2,5},{2,1},{7,2} };display(ans);cout endl;sort(ans.begin(), ans .end(), numcmp::cmp);display(ans);return 0;
}区别
这两种写法在功能上是等效的它们都可以用于自定义比较操作以对pair或其他数据结构进行排序。然而它们之间有一些细微的区别和优劣势 可读性使用函数指针或函数对象结构体中的operator()来定义比较操作通常更易于理解和阅读。函数名可以明确指示比较的目的而不需要查看结构体的成员。 灵活性将比较操作封装在结构体中函数对象方式通常更灵活因为你可以在结构体中存储额外的状态或配置以影响比较的行为。这对于实现不同的排序方式很有用。 命名冲突如果你有多个不同的比较操作并且它们需要在不同的上下文中使用将它们放入结构体中可以避免函数名冲突的问题因为每个结构体都有自己的作用域。函数指针方式可能需要更多的命名空间管理。 语法函数指针方式更紧凑但在语法上可能略显繁琐。函数对象方式需要创建一个结构体并在排序函数中使用括号运算符来调用这可能看起来有点冗长。
总的来说选择哪种方式取决于你的需求和个人偏好。如果你只需要一个简单的比较操作函数指针可能更合适。但如果你需要更复杂的比较逻辑或者希望更好地组织和封装比较操作那么使用函数对象结构体中的operator()可能更好。
