首页 > 编程语言 >STL-算法

STL-算法

时间：2024-01-22 20:14:14浏览次数：41  
标签：std begin end cout STL 算法 vector include

STL-算法

目录

STL的三大组件：容器(container) 算法(algorithm) 迭代器(iterator)。

STL算法部分主要由头文件 <algorithm>,<numeric>,<functional> 组成。要使用 STL中的算法函数必须包含头文件 <algorithm>

查找统计算法

简述 算法名称 功能
统计 count 返回某个元素出现的次数
统计 count_if 返回某个元素（当函数或仿函数的返回值为true）出现的次数
查找 find 根据值查找某个元素
查找 find_if 查找某个元素（当函数或仿函数的返回值为true）
查找 search 查找一个序列出现的位置
查找 search_n 在范围中查找第一个连续n个元素都等价于给定值的子范围的位置
二分查找 binary_search 在有序序列中查找value，找到返回true

统计

std::count 计算一个范围内特定元素的出现次数。

std::vector<int> my_vector = {1, 2, 3, 3, 4, 3};  
int count = std::count(my_vector.begin(), my_vector.end(), 3);  
std::cout << "Count of element 3: " << count << std::endl;

查找

std::find：在一个范围内查找特定元素，返回指向该元素的迭代器。

#include <vector>
#include <algorithm>
#include <iostream>
int main()
{
   std::vector<int> my_vector = {1, 2, 3, 4, 5};
   auto it = std::find(my_vector.begin(), my_vector.end(), 3);
   if (it != my_vector.end())
   {
      std::cout << "found  3 at position: " << std::distance(my_vector.begin(), it) << std::endl;
   }
   else
   {
      std::cout << "Element 3 not found" << std::endl;
   }

   return 0;
}
// found  3 at position: 2

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//查找内置数据类型
void test01()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    //返回一个迭代器，如果没有找到，返回end()
    vector<int>::iterator it = find(v.begin(), v.end(), 5);
    if (it == v.end())
        cout << "没找到" << endl;
    else
        cout << "找到了" << *it << endl;
}
//查找自定义数据类型
class Person
{
public:
    Person(string name,int age)
    {
        this->m_age = age;
        this->m_name = name;
    }
    //重载==运算符，让find知道如何对比Person类型数据
    bool operator==(const Person& p)
    {
        if (p.m_age == this->m_age && p.m_name == this->m_name)
            return true;
        else
            return false;
    }
    string m_name;
    int m_age;
};
void test02()
{
    //准备数据
    Person p1("A", 1);
    Person p2("B", 2);
    Person p3("C", 3);
    Person p4("D", 4);
    Person p5("E", 5);
    //放入容器中
    vector<Person>p;
    p.push_back(p1);
    p.push_back(p2);
    p.push_back(p3);
    p.push_back(p4);
    p.push_back(p5);
    //查找
    Person p6("A", 1);
    vector<Person>::iterator it = find(p.begin(), p.end(), p6);
    //输出，验证结果
    if (it == p.end())
        cout << "没找到" << endl;
    else
        cout << "找到了" << it->m_name << it->m_age << endl;
}
int main()
{
    test01();
    test02();
    return 0;
}

二分查找

std::binary_search 在一个已排序的范围内查找特定元素，如果找到则返回 true。

bool binary_search(iterator beg, iterator end, value);
查找指定的元素，查到返回true，否则返回false
注意：在无序列表中不可用，如果是无序序列，结果未知
beg		//开始迭代器
end		//结束迭代器
value	//查找的元素

#include<iostream>
#include<vector>
#include<algorithm>

std::vector<int> my_vector = {1, 2, 3, 4, 5};  
std::sort(my_vector.begin(), my_vector.end());  
if (std::binary_search(my_vector.begin(), my_vector.end(), 3)) {  
    std::cout << "Element 3 found" << std::endl;  
} else {  
    std::cout << "Element 3 not found" << std::endl;  
}

排序和通用算法

简介 算法名称 功能
排序 sort 以升序重新排列指定范围内的元素
排序 stable_sort 与sort类似，不过保留相等元素之间的顺序关系。
反正 reverse 将指定范围内元素重新反序排序。
随机 random_shuffle 对指定范围内的元素随机调整次序。
合并 merge 合并两个有序序列，存放到另一个序列

排序

std::sort 对一个范围内的元素进行排序。

#include<iostream>
#include<vector>
#include<algorithm>

std::vector<int> my_vector = {5, 2, 4, 1, 3};  
std::sort(my_vector.begin(), my_vector.end());  
for (auto x : my_vector) {  
    std::cout << x << " ";  
}  
std::cout << std::endl;
//1 2 3 4 5

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void test01()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    //默认升序
    sort(v.begin(), v.end());
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << " " ;
    }
    cout << endl;
    //使用内建函数对象实现降序排列
    sort(v.begin(), v.end(), greater<int>());
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << " ";
    }
}
int main()
{
    test01();
    return 0;
}

随机

random_shuffle(iterator beg, iterator end)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void test01()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    random_shuffle(v.begin(), v.end());
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << " " ;
    }
    cout << endl;
}
int main()
{
    test01();
    return 0;
}

合并

#include<iostream>
#include<vector>
#include<algorithm>

int main() {
    std::vector<int> v1 = {5, 2, 4, 1, 3};  
    std::vector<int> v2 = {5, 2, 4, 1, 3};  
    std::vector<int> v3;
    v3.resize(v1.size() + v2.size());
    std::sort(v1.begin(), v1.end());  
    for (auto x : v1) {  
        std::cout << x << " ";  
    }  
    std::cout << std::endl;
    //1 2 3 4 5

    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    for (auto x : v3) {
        std::cout << x << " ";  
    }  
    std::cout << std::endl;
    //1 2 3 4 5 5 2 4 1 3
  
    return 0;
}

反转

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void Print(int val)
{
    cout << val << " ";
}
void test01()
{
    vector<int>v1;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }
    for_each(v1.begin(), v1.end(), Print);
    cout << endl;
    //反转
    reverse(v1.begin(), v1.end());
    for_each(v1.begin(), v1.end(), Print);
}
int main()
{
    test01();
    return 0;
}

复制替换删除算法

序号 算法名称 功能
拷贝 copy 将容器内指定范围内的元素拷贝到目标容器。
替换 replace 将容器指定范围的旧元素替换为新元素
替换 replace_if 将容器区间内满足条件的元素，替换成新元素
唯一 unique 清除序列中相邻的重复元素
互换 swap 互换两个容器的元素
删除 remove 删除指定范围内所有等于指定元素的元素

复制替换

#include<iostream>
#include<vector>
#include<algorithm> //算法头文件

using namespace std;

struct  Judge_Elem
{
   bool   operator()(int x)     // 判断这个值是否为3
   {
   	return  x == 6 | x== 9;
   }
};

void  Print(int  x)
{
   cout << x << " ";            // 打印元素
}


int main()
{
   	//数据都在容器中
   	vector<int> v = { 1,2,3,4,5,6 };
    vector<int> v_copy(v.size());
    
    copy(v.begin(), v.end(), v_copy.begin());

   	// 替换元素
   	replace(v.begin(), v.end(),3,9);
   	for_each(v.begin(), v.end(), Print);
   	cout << endl;

 
   	// 条件替换元素
   	replace_if(v.begin(), v.end(), Judge_Elem(), 0);
   	for_each(v.begin(), v.end(), Print);
   	cout << endl;

    cout << "----------------------------------------" << endl;
    
}

删除唯一

#include<iostream>
#include<vector>
#include<algorithm> //算法头文件

using namespace std;

void  Print(int  x)
{
   cout << x << " ";            // 打印元素
}
int main()
{
   	//数据都在容器中
   	vector<int> v1 = { 1,3,2,3,4,5,6}; 
   	//删除所有的特定元素，但是不会改变容器的大小，只会将后面的元素往前移动，
   	//并返回删除后最后一个元素的结束位置
   	vector<int>::iterator  itNewEnd=remove(v1.begin(), v1.end(), 3); 

   	//打印
   	for_each(v1.begin(), itNewEnd, Print);
   	cout << endl;   

   	//数据都在容器中
   	vector<int> v2 = { 1,2,3,3,3,4,5,6 };

   	//删除【连续相同元素】，只保留一个，但是不会改变容器的大小，只会将后面的元素往前移动，
   	//并返回删除后最后一个元素的结束位置，类似remove
   	vector<int>::iterator  itNewEnd =	unique(v2.begin(), v2.end());

   	//打印
   	for_each(v2.begin(), itNewEnd, Print);
   	cout << endl;
   
}
// 1 2 4 5 6 
// 1 2 3 4 5 6

互换

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Print
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};
class GreaterFive
{
public:
    bool operator()(const int& val)
    {
        return val > 5;
    }
};
void test01()
{
    vector<int>v1;
    vector<int>v2;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
        v2.push_back(i + 2);
    }
    //交换前
    for_each(v1.begin(), v1.end(), Print());
    for_each(v2.begin(), v2.end(), Print());
    cout << endl;
    //交换后
    swap(v1, v2);
    for_each(v1.begin(), v1.end(), Print());
    for_each(v2.begin(), v2.end(), Print());
}
int main()
{
    test01();
    return 0;
}

生成和异变算法

简述 算法名称 功能
填充 fill 将输入值赋给标志范围内的所有元素
转换 transform 将输入的操作作用与指定范围内的每个元素，并产生一个新的序列
生成 generate 连续调用输入的函数来填充指定的范围 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void  Print(int  x)
{
   cout << x << " ";            // 打印元素
}

class even_by_two
{
private:
	static int _x;      //  注意静态变量   
public:
	int operator()()const
	{
		return _x += 2;
	}
};
int even_by_two::_x = 0; //  初始化静态变量

void test01()
{
    vector<int> v1={1,2,3,4,5,6,7,8,9};
    vector<int> iv(10);

    for_each(v1.begin(), v1.end(), Print);
    cout << endl;
    
    fill(v1.begin(), v1.end(), 9);

    for_each(v1.begin(), v1.end(), Print);
    cout << endl;

    generate(iv.begin(), iv.end(), even_by_two());
    for_each(iv.begin(), iv.end(), Print);
    cout << endl;
    
}   
int main()
{
    test01();
    return 0;
}

数值算法

简述 算法名称 功能
累加 accumulate 计算容器元素累计总和
partial_sum 每个元素值代表指定范围内该位置前所有元素之和
内积 inner_product 内积，对应元素相乘，再求和
adjacent_difference 计算相邻元素的差 
#include <iostream>
#include <vector>
#include <numeric> // 数值算法
#include <iterator> // 定义了ostream_iterator
#include<algorithm>
using namespace std;

void Print(int x){
    cout << x << " ";
};

int main(int argc, char* argv[])
{
	int arr[] = { 1, 2, 3, 4, 5 };
	vector<int> vec(arr, arr + 5);
	vector<int> vec2(arr, arr + 5);
    for_each(vec.begin(), vec.end(), Print);
    cout << endl;
    

	//  accumulate: iterator对标识的序列段元素之和，加到一个由val指定的初始值上。
	int temp;
	int val = 0;
	temp = accumulate(vec.begin(), vec.end(), val);
	cout << "accumulate(val = 0): " << temp << endl;
	val = 1;
	temp = accumulate(vec.begin(), vec.end(), val);
	cout << "accumulate(val = 1): " << temp << endl;

	// inner_product: 对两个序列做内积(对应元素相乘，再求和)并将内积加到一个输入的初始值上。
	// 这里是：1*1 + 2*2 + 3*3 + 4*4 + 5*5
	val = 0;
	temp = inner_product(vec.begin(), vec.end(), vec2.begin(), val);
	cout << "inner_product(val = 0): " << temp << endl;

	// partial_sum: 创建一个新序列，其中每个元素值代表指定范围内该位置前所有元素之和。
	// 第一次，1   第二次，1+2  第三次，1+2+3  第四次，1+2+3+4
	ostream_iterator<int> oit(cout, " "); // 迭代器绑定到cout上作为输出使用
	cout << "ostream_iterator: ";
	partial_sum(vec.begin(), vec.end(), oit);// 依次输出前n个数的和
	cout << endl;
	// 第一次，1   第二次，1-2  第三次，1-2-3  第四次，1-2-3-4
	cout << "ostream_iterator(minus): ";
	partial_sum(vec.begin(), vec.end(), oit, minus<int>());// 依次输出第一个数减去（除第一个数外到当前数的和）
	cout << endl;

	// adjacent_difference: 创建一个新序列，新序列中每个新值代表当前元素与上一个元素的差。
	// 第一次，1-0   第二次，2-1  第三次，3-2  第四次，4-3
	cout << "adjacent_difference: ";
	adjacent_difference(vec.begin(), vec.end(), oit);              // 输出相邻元素差值 后面-前面
	cout << endl;
	// 第一次，1+0   第二次，2+1  第三次，3+2  第四次，4+3
	cout << "adjacent_difference(plus): ";
	adjacent_difference(vec.begin(), vec.end(), oit, plus<int>()); // 输出相邻元素差值 后面-前面 
	cout << endl;

	return 0;
}

/*
accumulate(val = 0): 15
accumulate(val = 1): 16
inner_product(val = 0): 55
ostream_iterator: 1 3 6 10 15
ostream_iterator(minus): 1 -1 -4 -8 -13
adjacent_difference: 1 1 1 1 1
adjacent_difference(plus): 1 3 5 7 9
*/

关系集合算法

简述 算法名称 功能
交集 set_intersection 求两个容器的交集
并集 set_union 求两个容器的并集
差集 set_difference 求两个容器的差集

交并集

set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
//求两个容器的交集

beg1	//容器1开始迭代器
end1	//容器1结束迭代器
beg2	//容器2开始迭代器
end2	//容器2结束迭代器
dest	//目标容器开始迭代器

# 返回值为迭代器，指向交集最后一个元素的下一个位置

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void myPrint(int val)
{
    cout << val << " ";
}
void test01()
{
    vector<int>v1={1,2,3,4,5,6,7,8,9};
    vector<int>v2={5,6,7,8,9,10,11,12,13,14};

    for_each(v1.begin(), v1.end(), myPrint);
    cout << endl;
    for_each(v2.begin(), v2.end(), myPrint);
    cout << endl;

    //目标容器需要提前开辟空间，最特殊的情况，大容器包含小容器
    vector<int>v3;
    v3.resize(min(v1.size(), v2.size()));
    //取交集
    vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    for_each(v3.begin(), itEnd, myPrint);
    cout << endl;
    //如果不用返回的itEnd，会把0也给打印出来
    for_each(v3.begin(), v3.end(), myPrint);
}
int main()
{
    test01();
    return 0;
}


set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
//求两个容器的并集

beg1	//容器1开始迭代器
end1	//容器1结束迭代器
beg2	//容器2开始迭代器
end2	//容器2结束迭代器
dest	//目标容器开始迭代器

# 返回值为迭代器，指向并集最后一个元素的下一个位置

vector<int>v4;
v4.resize(v1.size() + v2.size());
vector<int>::iterator ituEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v4.begin());
for_each(v4.begin(), ituEnd, myPrint);

实践操作

Vector中去重

对于STL去重，可以使用中提供的unique()函数。

unique()函数用于去除相邻元素中的重复元素（所以去重前需要对vector进行排序），只留下一个。返回去重后的尾地址。

unique()并不会删除vector中的元素，只是将重复元素替换为之后的元素，vector的大小并不会改变。

所以之后还需要调用erase()函数，删除之后的元素。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
    vector<int> nums;
    for (int i = 0; i < 10; i++)
        nums.push_back(i % 8);

    cout << "before sort..." << endl;
    for (size_t i = 0; i < nums.size(); i++)
        cout << nums[i] << "  ";
    cout << endl;

    cout << "after sort..." << endl;
    sort(nums.begin(), nums.end());
    for (size_t i = 0; i < nums.size(); i++)
        cout << nums[i] << "  ";
    cout << endl;

    auto iter = unique(nums.begin(), nums.end());
    cout << "before unique() size:" << nums.size() << "\nafter unique() size:" << nums.size() << endl;
    nums.erase(iter, nums.end());
    for (size_t i = 0; i < nums.size(); i++)
        cout << nums[i] << "  ";
    cout << endl;

    getchar();
    return 0;
}

参考资料

https://juejin.cn/post/7301496834232614951?from=search-suggest#heading-24

https://blog.csdn.net/u014779536/article/details/116380670 详细

https://www.cnblogs.com/linuxAndMcu/p/10264339.html

https://www.cnblogs.com/BeyondAnyTime/archive/2012/05/27/2520532.html

标签：std,begin,end,cout,STL,算法,vector,include
From： https://www.cnblogs.com/tian777/p/17980865

相关文章

  • STL-list链表
    STL-list链表目录STL-list链表初始化创建添加删除元素遍历迭代参考函数参考资料STL-list容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。这意味着，list容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。list容器中各个元素的......
  • STL-stack和queue堆栈和队列
    STL-stack和queue堆栈和队列目录STL-stack和queue堆栈和队列堆栈和队列特性堆栈主要操作构造函数主要操作栈顶插入和删除大小相关简单案例队列的主要操作构造函数大小相关索引访问入队/出队优先队列priority_queue初始化构造小顶堆自定义结构体排序参考资料堆栈和队列特性stack......
  • STL-vector向量
    STL-vector向量目录STL-vector向量1.头文件2.构造函数3.索引存取元素4.遍历元素4.capacity相关5.插入元素6.删除元素7.排序和翻转8.底层原理9.特殊记忆函数总结参考资料vector数组是一个能存放任意数据类型（类，结构，普通变量类型等）的动态数组，在数据结构中就相当于顺序储存的线性......
  • STL-deque双端队列
    STL-deque双端队列目录STL-deque双端队列创建初始化插入元素删除元素遍历容器函数总览deque和vector参考资料deque是double-endedqueue的缩写，又称双端队列容器，可以对其两段的数据进行操作，因为它没有capacity属性，因此不会像vector那样”旧空间不足而重新配置一块更大空间，然后......
  • STL-Set集合
    STL-Set集合目录STL-Set集合导入构造插入删除查找元素遍历元素成员方法multisetunordered_set参考资料set集合unordered_set无序集合set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。set不允许两个元素有相同的键值。不允许出现相同的两个se......
  • STL-map/unordered_map映射
    STL-map/unordered_map映射目录STL-map/unordered_map映射1.构造初始化2.数据插入3.数据查找4.迭代器遍历5.删除和清空6.成员方法7.multimap8.unordered_map9.unordered_multimap10.底层原理11.总结12.参考资料键值对容器Map映射是一种类似于字典的数据结构。它是（键，值）对的序......
  • 基于项目的协同过滤推荐算法(Item-Based Collaborative Filtering Recommendation Alg
    前言协同过滤推荐系统，包括基于用户的、基于项目的息肉通过率等，今天我们读一篇基于项目的协同过滤算法的论文。今天读的论文为一篇名叫《基于项目的协同过滤推荐算法》(Item-BasedCollaborativeFilteringRecommendationAlgorithms)。摘要Recommendersystemsapplyknowledg......
  • 优化Elastic Load Balancing负载均衡算法的实战指南
    在AWS中，ElasticLoadBalancing（ELB）服务是实现负载均衡的关键组件，而TargetGroups则用于管理和路由传入的流量。本篇博文将深入介绍如何通过Boto3（AWSSDKforPython）和ELBv2API来优化TargetGroup的负载均衡算法，以提高系统性能。我们将实现将所有符合条件的TargetGroup的负载均衡......
  • 聚类算法笔记【零基础数模系列】
    聚类算法前言作为数模小白，看了很多讲解新概念新模型的文章，这些文章往往要么讲的很浅不讲原理只讲应用，让人知其然不知其所以然。要么讲的很深小白看不懂，同时总是忽略关键部分，经常性引入陌生概念让初学者疑惑，因此有了本文，任何能熟练掌握线性代数知识且逻辑思维能力尚可的人都可以......
  • C++U6-03-最短路算法4-floyd算法
    B站复习视频：1、https://www.bilibili.com/video/BV1Fj411d71S/?spm_id_from=333.999.0.02、https://www.bilibili.com/video/BV1RK4y1d7ct?p=1&vd_source=5c960e1ede940bc5cab8ed42c8bdc937学习目标 floyd算法Floyd算法是一种用于找到图中所有节点对之间最短路径的动态规划......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99