set
在C++中,set是一个标准的关联容器,它使用红黑树数据结构来存储元素,并保证元素按照一定的顺序排列。set中的元素是唯一的,不能重复。
set容器提供了一系列方法,包括插入元素、删除元素、查找元素、遍历元素等,可以方便地实现对元素的操作。
常用的set方法:
-
insert(val)
:将元素val插入到set中。 -
erase(val)
:从set中删除值为val的元素。 -
find(val)
:在set中查找值为val的元素,并返回指向该元素的迭代器。 -
size()
:返回set中元素的个数。 -
begin()
:返回指向set中第一个元素的迭代器。 -
end()
:返回指向set中最后一个元素之后位置的迭代器,通常用于遍历set中的元素。 -
empty()
:判断set是否为空,如果为空则返回true,否则返回false。 -
clear()
:清空set中的所有元素。 -
count(val)
:返回set中值为val的元素的个数,因为set中元素不重复,所以返回值只能是0或1。 -
lower_bound(val)
:返回一个指向第一个不小于val的元素的迭代器。 -
upper_bound(val)
:返回一个指向第一个大于val的元素的迭代器。 -
equal_range(val)
:返回一个迭代器对,其中第一个迭代器指向set中第一个等于val的元素,第二个迭代器指向set中第一个大于val的元素。
set实现去重的例子:
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> myset;
myset.insert(10);
myset.insert(20);
myset.insert(30);
myset.insert(20);
myset.insert(40);
cout << "Set contains " << myset.size() << " elements: ";
for (auto it = myset.begin(); it != myset.end(); it++) {
cout << *it << " ";
}
cout << endl;
return 0;
}
Set contains 4 elements: 10 20 30 40
set还支持自定义比较函数,可以根据不同的需求来定义元素之间的比较方式,例如按照字符串长度进行排序等。
自定义比较函数的例子,按照字符串长度从小到大排序:
#include <iostream>
#include <set>
#include <string>
using namespace std;
struct cmp {
bool operator() (const string& a, const string& b) const {
return a.length() < b.length();
}
};
int main() {
set<string, cmp> myset;
myset.insert("apple");
myset.insert("banana");
myset.insert("pear");
myset.insert("orange");
cout << "Set contains " << myset.size() << " elements: ";
for (auto it = myset.begin(); it != myset.end(); it++) {
cout << *it << " ";
}
cout << endl;
return 0;
}
Set contains 4 elements: pear apple banana orange
可以看到,程序根据字符串长度从小到大排序了元素。
总之,set是一个非常有用的容器,可以方便地实现对元素的操作,并且保证元素无重复。在实际的编程中,我们可以根据不同的需求来灵活地使用set容器。
在算法模拟题中,set容器通常用于实现集合的概念,即存储一些元素,同时保证元素无重复。在模拟一些实际场景时,例如计算两个集合的交集、并集等操作时,set容器可以很方便地实现这些操作。
使用set容器求两个集合的交集的例子:
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> A = {1, 2, 3, 4, 5};
set<int> B = {2, 4, 6, 8};
set<int> C;
for (auto it = A.begin(); it != A.end(); it++) {
if (B.count(*it)) {
C.insert(*it);
}
}
cout << "A: ";
for (auto it = A.begin(); it != A.end(); it++) {
cout << *it << " ";
}
cout << endl;
cout << "B: ";
for (auto it = B.begin(); it != B.end(); it++) {
cout << *it << " ";
}
cout << endl;
cout << "C: ";
for (auto it = C.begin(); it != C.end(); it++) {
cout << *it << " ";
}
cout << endl;
return 0;
}
A: 1 2 3 4 5
B: 2 4 6 8
C: 2 4
可以看到,程序使用set容器实现了对两个集合求交集的操作。
除了求交集、并集等操作外,set容器还可以用于对元素进行排序、去重等操作。在进行算法模拟题时,我们可以根据实际需要灵活地使用set容器,以实现对元素的操作和处理。
vector
vector是C++标准库中的一个容器类,用于存储元素的动态数组,可以实现自动扩容、快速随机访问等功能。下面介绍一些vector的基本用法。
创建vector对象
可以通过以下方式来创建一个vector对象:
#include <vector>
using namespace std;
vector<int> v; // 创建一个空的vector对象
可以在创建时指定初始大小和初始值:
vector<int> v1(10); // 创建一个大小为10的vector对象,每个元素的值为0
vector<int> v2(10, 1); // 创建一个大小为10的vector对象,每个元素的值为1
vector<int> v3{1, 2, 3}; // 创建一个包含3个元素的vector对象,值分别为1、2、3
vector<int> v4 = {4, 5, 6}; // 与v3等价
插入和删除元素
可以使用push_back()方法在vector的末尾插入一个元素:
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
也可以使用insert()方法在指定位置插入一个元素:
vector<int> v{1, 2, 3};
v.insert(v.begin() + 1, 4); // 在下标为1的位置插入元素4
可以使用pop_back()方法删除vector末尾的一个元素:
vector<int> v{1, 2, 3};
v.pop_back();
也可以使用erase()方法删除指定位置的一个或多个元素:
vector<int> v{1, 2, 3};
v.erase(v.begin() + 1); // 删除下标为1的元素
v.erase(v.begin() + 1, v.end() - 1); // 删除下标为1到末尾前一个位置的元素
访问元素
可以使用下标运算符[]或at()方法来访问vector中的元素,下标从0开始:
vector<int> v{1, 2, 3};
int x = v[0]; // x的值为1
int y = v.at(1); // y的值为2
也可以使用迭代器来访问vector中的元素:
vector<int> v{1, 2, 3};
for (auto it = v.begin(); it != v.end(); it++) {
cout << *it << " "; // 输出1 2 3
}
获取vector的大小和容量
可以使用size()方法获取vector中元素的个数:
vector<int> v{1, 2, 3};
int n = v.size(); // n的值为3
可以使用capacity()方法获取vector中能够容纳的元素个数:
vector<int> v{1, 2, 3};
int m = v.capacity(); // m的值为3
需要注意的是,vector的实际大小和容量可能不一致,因为vector会动态调整大小和容量以适应元素的增减。
检查vector是否为空
可以使用empty()方法检查vector是否为空:
vector<int> v{1, 2, 3};
if (v.empty()) {
cout << "vector is empty" << endl;
} else {
cout << "vector is not empty" << endl;
}
访问vector的首尾元素
可以使用front()方法和back()方法分别访问vector的第一个和最后一个元素:
vector<int> v{1, 2, 3};
int x = v.front(); // x的值为1
int y = v.back(); // y的值为3
修改vector的大小
可以使用resize()方法修改vector的大小,如果新的大小比原来的大小小,则会删除多余的元素,如果新的大小比原来的大小大,则会添加默认值的元素:
vector<int> v{1, 2, 3};
v.resize(5); // v的大小变为5,多余的元素的值为0
v.resize(2); // v的大小变为2,多余的元素被删除
清空vector
可以使用clear()方法清空vector中的所有元素:
vector<int> v{1, 2, 3};
v.clear(); // v中的元素被清空
交换vector
可以使用swap()方法交换两个vector对象:
vector<int> v1{1, 2, 3};
vector<int> v2{4, 5, 6};
v1.swap(v2); // v1和v2中的元素被交换
需要注意的是,使用swap()方法可以在不需要额外的内存空间的情况下交换两个vector对象,因此可以有效避免内存泄漏的问题。
vector的迭代器
vector的迭代器可以用来遍历vector中的元素,可以使用begin()方法和end()方法分别获取指向第一个元素和最后一个元素之后位置的迭代器:
vector<int> v{1, 2, 3};
for (auto it = v.begin(); it != v.end(); it++) {
cout << *it << " "; // 输出1 2 3
}
需要注意的是,vector的迭代器不是指针类型,但是可以通过解引用*运算符来访问迭代器指向的元素。
vector的性能
vector的性能在大多数情况下都非常好,可以达到常数时间复杂度。但是,由于vector的动态扩容需要重新分配内存并复制元素,因此在频繁增加元素的情况下,可能会导致性能下降。此外,vector的内存分配可能不是连续的,这也可能会影响性能。
自定义vector元素类型
vector可以存储任何类型的元素,包括内置类型、自定义类型、指针等。如果要存储自定义类型的元素,需要定义一个适当的构造函数和析构函数。
例如,假设我们有一个自定义类型Person,其中包含姓名和年龄两个字段:
#include <string>
using namespace std;
class Person {
public:
Person(const string& name, int age) : name_(name), age_(age) {}
string name() const { return name_; }
int age() const { return age_; }
private:
string name_;
int age_;
};
然后可以定义一个vector来存储Person类型的元素:
vector<Person> v;
v.push_back(Person("Alice", 20));
v.push_back(Person("Bob", 30));
需要注意的是,如果Person类中包含指针等动态分配内存的成员变量,需要自定义拷贝构造函数和赋值运算符,以确保正确地复制和释放内存。
使用emplace_back()方法
emplace_back()方法可以在vector的末尾直接构造新的元素,而不是先创建一个临时对象再复制到vector中,从而可以避免不必要的拷贝操作,提高性能。
例如,假设我们有一个vector来存储Person类型的元素,可以使用emplace_back()方法来添加新的元素:
vector<Person> v;
v.emplace_back("Alice", 20);
v.emplace_back("Bob", 30);
需要注意的是,emplace_back()方法的参数应该与元素类型的构造函数所需的参数匹配。
使用reserve()方法
reserve()方法可以预先分配一定数量的内存空间,以避免在添加大量元素时反复进行动态内存分配和复制操作,从而提高性能。
例如,假设我们需要存储一百万个int类型的元素,可以使用reserve()方法预先分配内存空间:
vector<int> v;
v.reserve(1000000);
for (int i = 0; i < 1000000; i++) {
v.push_back(i);
}
需要注意的是,reserve()
方法只会预先分配内存空间,而不会改变vector的大小,因此需要在添加元素之前使用reserve()方法。
使用std::move()函数
std::move()函数可以将一个对象的所有权转移给另一个对象,从而避免不必要的拷贝操作,提高性能。
例如,假设我们有一个vector,需要将其中的元素移动到另一个vector中:
vector<Person> v1;
vector<Person> v2;
// 添加元素到v1中
v2.reserve(v1.size());
for (auto& p : v1) {
v2.push_back(std::move(p));
}
v1.clear(); // 清空v1
需要注意的是,使用std::move()
函数需要确保被移动的对象不再使用,否则可能会出现未定义的行为。
总之,vector是一个非常实用的容器类,在处理动态数组的问题时非常方便。需要注意的是,在使用vector时需要了解其高级特性,并结合具体的应用场景进行优化,以提高性能和减少内存开销。
vector在算法模拟题中
在算法模拟题中,vector是一个非常实用的容器类,可以方便地处理动态数组的问题。以下是一些常见的算法模拟题中使用vector的场景:
存储动态数组
在模拟数组操作时,可以使用vector来存储动态数组。例如,假设需要实现一个队列,可以使用vector来存储队列中的元素:
vector<int> q; // 定义一个vector来存储队列中的元素
q.push_back(1); // 添加元素到队列末尾
q.push_back(2);
q.push_back(3);
int x = q.front(); // 获取队列头部元素
q.erase(q.begin()); // 删除队列头部元素
模拟栈操作
在模拟栈操作时,也可以使用vector来存储栈中的元素。例如,假设需要实现一个栈,可以使用vector来存储栈中的元素:
vector<int> s; // 定义一个vector来存储栈中的元素
s.push_back(1); // 添加元素到栈顶
s.push_back(2);
s.push_back(3);
int x = s.back(); // 获取栈顶元素
s.pop_back(); // 删除栈顶元素
实现动态规划
在动态规划问题中,通常需要定义一个二维数组来存储状态。可以使用vector来实现这个二维数组,并使用resize()方法来动态调整数组大小。例如,假设需要实现一个最长公共子序列问题的动态规划算法,可以使用vector来存储状态:
string s1 = "ABCBDAB";
string s2 = "BDCABA";
vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1));
for (int i = 1; i <= s1.size(); i++) {
for (int j = 1; j <= s2.size(); j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int ans = dp[s1.size()][s2.size()]; // 最长公共子序列的长度
需要注意的是,使用vector来实现二维数组时,应该将数组定义为vector<vector>
类型,并使用resize()
方法来动态调整数组大小。文章来源:https://www.toymoban.com/news/detail-422838.html
总之,在算法模拟题中,vector是一个非常实用的容器类,可以方便地处理动态数组的问题,并且可以根据具体的应用场景进行优化,以提高性能和减少内存开销。文章来源地址https://www.toymoban.com/news/detail-422838.html
到了这里,关于Let’s Make C++ Great Again——set与vector的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!