Let’s Make C++ Great Again——set与vector

这篇具有很好参考价值的文章主要介绍了Let’s Make C++ Great Again——set与vector。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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()方法来动态调整数组大小。

总之,在算法模拟题中,vector是一个非常实用的容器类,可以方便地处理动态数组的问题,并且可以根据具体的应用场景进行优化,以提高性能和减少内存开销。文章来源地址https://www.toymoban.com/news/detail-422838.html

到了这里,关于Let’s Make C++ Great Again——set与vector的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题

    更多算法例题链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 什么是迭代器(iterator) 迭代器(iterator)的定义: 迭代器是一种检查容器内元素并遍历元素的数据类型。 迭代器提供对一个容器中的对象的访问方法,并且定义了容器中对象的范围。 容器

    2024年04月14日
    浏览(50)
  • C++ //练习 11.12 编写程序,读入string和int的序列,将每个string和int存入一个pair中,pair保存在一个vector中。

    练习 11.12 编写程序,读入string和int的序列,将每个string和int存入一个pair中,pair保存在一个vector中。 环境:Linux Ubuntu(云服务器) 工具:vim   代码块 运行结果显示如下

    2024年04月10日
    浏览(42)
  • 【C++进阶】使用一个哈希桶封装出unordered_map和uordered_set

    由于要使用一个哈希桶封装出unordered_map和uordered_set,所以要对哈希桶的模版参数进行改造,由于unordered_map是kv模型,而uordered_set是k模型,所以必须在实现哈希桶的时候提供模版,在封装uordered_set和unordered_map时传入不同的模版参数。 还要要修改的是,如果同时封装出,在获得

    2024年02月12日
    浏览(35)
  • pair 是 C++ 标准库中的一个模板类,用于存储两个对象的组合

    pair 是 C++ 标准库中的一个模板类,用于存储两个对象的组合。它位于 utility 头文件中。 pair 类的定义如下: pair 类有两个公共成员变量: first 和 second ,分别用于存储两个对象。成员变量的类型可以是任意类型,包括内置类型、自定义类型和指针类型等。 以下是一个使用

    2024年02月09日
    浏览(43)
  • 【C++】STL——用一个哈希表封装出unordered_map和unordered_set

    根据先前对unordered_map和unordered_set的学习,我们得知其底层是借助哈希表来实现的,接下来我们会使用上篇博客实现的开散列哈希表来模拟实现unordered_map和unordered_set,哈希表源代码链接: Hash/Hash/HashBucket.h · wei/cplusplus - 码云 - 开源中国 (gitee.com) 下面我们对哈希表进行改造,

    2023年04月18日
    浏览(47)
  • 【C++】如何用一个哈希表同时封装出unordered_set与unordered_map

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.哈希桶源码  2.哈希表模板参数的控制 3.字符串作为键值如何映射哈希值

    2024年03月26日
    浏览(51)
  • ES6 全详解 let 、 const 、解构赋值、剩余运算符、函数默认参数、扩展运算符、箭头函数、新增方法,promise、Set、class等等

    ​ ECMAScript 6.0,简称 ES6,是 JavaScript 语言的下一代标准,已经在 2015 年 6 月正式发布了。它的目标,是使得 JavaScript 语言可以用来编写复杂的大型应用程序,成为企业级开发语言 要讲清楚这个问题,需要回顾历史。1996 年 11 月,JavaScript 的创造者 Netscape 公司,决定将 JavaSc

    2024年04月15日
    浏览(46)
  • Make the enclosing method “static“ or remove this set

    sonar安全扫描会报: Make the enclosing method “static” or remove this set.Why is this an issue? 修改成以下方式就可以了:

    2024年02月14日
    浏览(37)
  • 16 标准模板库STL之vector

    基础知识         1、vector和数组有点类似,但它比数组更好用。一般来说,数组的长度是不能动态拓展的,因此就需要考虑长度到底多大合适。长度不能过大,否则浪费内存;也不能过小,否则内存不够。vector正好弥补了这个缺陷,相当于一个可以自动改变数组长度的动

    2023年04月17日
    浏览(52)
  • STL标准模板库 vector容器与迭代器入门

    vector 就是一个连续的数据 C++11 std::vector a ={1,4,2,6,7}; 可以使用花括号来定义 容器的功能就是存储数据 迭代器的功能就是指向数据,并且可以实现前后移动(指针)算法和容器的接口的存在 vector功能是长度可变的数组, 身在栈上 里面的数据存储在堆上 因为栈不可动态扩容

    2023年04月23日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包