自学内容网 自学内容网
自学内容网 > 正文

C++的Find算法用法,

🕗 发布于 2024-12-07 20:23 c++  算法  

在 C++ 中，可以使用 std::map 统计值出现次数为 2 的键。具体步骤如下：

  1. 遍历 std::map，找出所有值为 2 的键。
  2. 使用条件语句检查每个值，符合条件时记录对应键。
#include <iostream>
#include <map>
#include <vector>

int main() {
    // 创建一个 std::map 并插入数据
    std::map<int, int> data = {{1, 2}, {2, 3}, {3, 2}, {4, 1}, {5, 2}};
    
    // 用于存储值为 2 的键
    std::vector<int> keys_with_value_2;

    // 遍历 map
    for (const auto& pair : data) {
        if (pair.second == 2) {
            keys_with_value_2.push_back(pair.first);
        }
    }

    // 输出统计结果
    std::cout << "Keys with value 2:" << std::endl;
    for (int key : keys_with_value_2) {
        std::cout << key << " ";
    }
    std::cout << std::endl;

    return 0;
}

示例运行结果

如果 data 中的内容是 {{1, 2}, {2, 3}, {3, 2}, {4, 1}, {5, 2}}，输出结果为：

Keys with value 2: 1 3 5

关键点

  1. std::map 的有序性：std::map 会根据键自动排序，但这不影响统计值的逻辑。
  2. 复杂度：遍历 std::map 的复杂度为 O(n)，其中 n 为键值对的数量。

如果需要统计这些键的数量，可以直接输出 keys_with_value_2.size()。

在 C++ 中，std::set 是一个有序且不允许重复元素的集合，常用来存储不重复的数据并支持快速查找、插入和删除操作。

以下是关于 std::set 的详细介绍和常用操作：

定义和初始化

#include <iostream>
#include <set>

int main() {
    // 创建一个空的 set
    std::set<int> s;

    // 初始化 set
    std::set<int> s2 = {1, 3, 5, 7};

    // 输出初始化的内容
    for (int x : s2) {
        std::cout << x << " ";
    }
    return 0;
}

主要特点

  1. 有序性：std::set 自动按照键的顺序存储元素（默认升序）。
  2. 唯一性：std::set 不允许存储重复的元素。
  3. 底层实现：std::set 是基于红黑树的有序集合，支持对数时间复杂度的插入、删除和查找操作。

常用操作

1. 插入元素

std::set<int> s; s.insert(5); s.insert(3); s.insert(8); s.insert(3); // 重复插入 3，会被忽略

2. 遍历集合

for (int x : s) { std::cout << x << " "; } // 或使用迭代器 for (auto it = s.begin(); it != s.end(); ++it) { std::cout << *it << " "; }

3. 删除元素

s.erase(3); // 删除元素 3 s.erase(s.begin()); // 删除第一个元素

4. 查找元素

if (s.find(5) != s.end()) {

std::cout << "Found 5" << std::endl; } else { std::cout << "5 not found" << std::endl; }

5. 获取集合大小

std::cout << "Size: " << s.size() << std::endl;

6. 检查集合是否为空

if (s.empty()) { std::cout << "Set is empty" << std::endl; }

更多高级操作

1. 获取范围内的元素
std::set<int> s = {1, 3, 5, 7, 9};
auto itLow = s.lower_bound(3); // 返回指向第一个 >= 3 的迭代器
auto itUp = s.upper_bound(7); // 返回指向第一个 > 7 的迭代器

for (auto it = itLow; it != itUp; ++it) {
    std::cout << *it << " ";
}
2. 合并两个集合
std::set<int> s1 = {1, 3, 5};
std::set<int> s2 = {2, 4, 6};

// 插入另一个集合的所有元素
s1.insert(s2.begin(), s2.end());

for (int x : s1) {
    std::cout << x << " ";
}

示例代码

 

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {4, 2, 8, 6};

    // 插入元素
    s.insert(5);
    s.insert(3);

    // 遍历元素
    std::cout << "Set elements: ";
    for (int x : s) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 查找元素
    if (s.find(3) != s.end()) {
        std::cout << "3 is found in the set" << std::endl;
    } else {
        std::cout << "3 is not found in the set" << std::endl;
    }

    // 删除元素
    s.erase(3);

    // 检查集合大小
    std::cout << "Set size: " << s.size() << std::endl;

    return 0;
}

 

 

 

运行结果
 

Set elements: 2 4 5 6 8 3 is found in the set Set size: 4 
 

总结
 

std::set 是一个非常实用的 STL 容器，适用于需要保持元素唯一且有序的场景。如果需要存储重复元素，可以考虑使用 std::multiset。
 

 

C++算法库中的find如何使用
 

 

在 C++ 中，std::find 是一个用于在容器中查找某个值的通用算法，定义在 <algorithm> 头文件中。它可以用来查找 std::vector、std::list、std::array 等标准容器中的某个值。
 

 

std::find 的用法
 

Iterator find(Iterator first, Iterator last, const T& value); 
 

  •  
    参数说明：
     
  
    1. first 和 last：容器的起始迭代器和结束迭代器，表示查找范围 [first, last)。
    2. value：要查找的值。
  •  
    返回值：
     
  
    • 如果找到值，则返回指向该值的迭代器。
    • 如果未找到值，则返回 last 迭代器。
 

 

使用示例
 

1. 在 std::vector 中查找
 

 

#include <iostream>
#include <vector>
#include <algorithm> // std::find

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 查找值 3
    auto it = std::find(vec.begin(), vec.end(), 3);

    if (it != vec.end()) {
        std::cout << "Found " << *it << " at index " << (it - vec.begin()) << std::endl;
    } else {
        std::cout << "Value not found" << std::endl;
    }

    return 0;
}

 

输出：
 

Found 3 at index 2 
 

 

2. 在 std::list 中查找
 

#include <iostream>
#include <list>
#include <algorithm>

int main() {
    std::list<int> lst = {10, 20, 30, 40, 50};

    // 查找值 30
    auto it = std::find(lst.begin(), lst.end(), 30);

    if (it != lst.end()) {
        std::cout << "Found " << *it << std::endl;
    } else {
        std::cout << "Value not found" << std::endl;
    }

    return 0;
}

 

 

 

输出：
 

Found 30 
 

 

3. 查找字符串中的字符
 

std::find 也可以用来查找字符串中的某个字符。
 

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    std::string str = "hello world";

    // 查找字符 'o'
    auto it = std::find(str.begin(), str.end(), 'o');

    if (it != str.end()) {
        std::cout << "Found '" << *it << "' at index " << (it - str.begin()) << std::endl;
    } else {
        std::cout << "Character not found" << std::endl;
    }

    return 0;
}

 

 

输出：
 

Found 'o' at index 4 
 

 

其他注意事项
 

  1.  
    查找的范围是 [first, last)：
     
  
    • std::find 不会检查 last，因此传递的范围必须有效。
  2.  
    对于自定义类型的查找：
     
  
    • 如果容器中存储的是自定义类型，需要重载 == 运算符，std::find 才能正常工作。
 

 

示例：在自定义类型中查找
 

 

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

struct Point {
    int x, y;

    // 重载 == 运算符
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

int main() {
    std::vector<Point> points = {{1, 2}, {3, 4}, {5, 6}};

    Point target = {3, 4};
    auto it = std::find(points.begin(), points.end(), target);

    if (it != points.end()) {
        std::cout << "Found Point(" << it->x << ", " << it->y << ")" << std::endl;
    } else {
        std::cout << "Point not found" << std::endl;
    }

    return 0;
}

 

 

输出：
 

Found Point(3, 4) 
 

 

性能和复杂度
 

  • 时间复杂度：O(n)，其中 n 是容器中的元素数量。
  • 空间复杂度：O(1)。
 

对于大容器，如果需要频繁查找，可以考虑使用 std::unordered_set 或 std::unordered_map，它们提供平均时间复杂度为 O(1) 的查找性能。
 

 

总结
 

  1. std::find 是一个通用的查找算法，适用于所有支持迭代器的容器。
  2. 它使用线性搜索，适合中小型容器。
  3. 对于自定义类型，要确保实现了 == 运算符。
 

在 C++ 中，std::find 通常不适用于 std::map 或 std::unordered_map，因为这些容器存储的是键值对 (std::pair<const Key, Value>)，而不是单一的值。如果要在 std::map 中查找某个键或值，通常需要使用 std::map 提供的专用方法，如 find 或迭代器。
 

 

在 std::map 中查找键
 

std::map 自带的 find 函数更高效（时间复杂度为 O(log n)），可以直接查找键，而不需要用 <algorithm> 中的 std::find。
 

示例：
 

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> m = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 使用 map 自带的 find 函数查找键 2
    auto it = m.find(2);

    if (it != m.end()) {
        std::cout << "Found key: " << it->first << ", value: " << it->second << std::endl;
    } else {
        std::cout << "Key not found" << std::endl;
    }

    return 0;
}

 

 

输出：
 

Found key: 2, value: two 
 

 

使用 std::find_if 查找键
 

如果你必须使用 <algorithm> 中的 std::find 系列函数，可以通过 std::find_if 自定义谓词来查找键。
 

#include <iostream>
#include <map>
#include <algorithm>

int main() {
    std::map<int, std::string> m = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 使用 std::find_if 查找键
    int key_to_find = 2;
    auto it = std::find_if(m.begin(), m.end(), [key_to_find](const std::pair<int, std::string>& p) {
        return p.first == key_to_find; // 比较键
    });

    if (it != m.end()) {
        std::cout << "Found key: " << it->first << ", value: " << it->second << std::endl;
    } else {
        std::cout << "Key not found" << std::endl;
    }

    return 0;
}

 

 

 

在 std::map 中查找值
 

std::map 的设计是以键为主查找值。如果想要查找某个值，则需要遍历整个 map，例如用 std::find_if 来查找。
 

示例：用 std::find_if 查找值
 

 

#include <iostream>
#include <map>
#include <algorithm>

int main() {
    std::map<int, std::string> m = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 使用 std::find_if 查找值 "two"
    auto it = std::find_if(m.begin(), m.end(), [](const std::pair<int, std::string>& p) {
        return p.second == "two";
    });

    if (it != m.end()) {
        std::cout << "Found value: " << it->second << ", key: " << it->first << std::endl;
    } else {
        std::cout << "Value not found" << std::endl;
    }

    return 0;
}

 

 

输出：
 

Found value: two, key: 2 
 

 

查找键值对
 

如果需要查找完整的键值对（std::pair），可以直接使用 std::find：
 

 

#include <iostream>
#include <map>
#include <algorithm>

int main() {
    std::map<int, std::string> m = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 查找键值对 {2, "two"}
    auto it = std::find(m.begin(), m.end(), std::make_pair(2, "two"));

    if (it != m.end()) {
        std::cout << "Found pair: {" << it->first << ", " << it->second << "}" << std::endl;
    } else {
        std::cout << "Pair not found" << std::endl;
    }

    return 0;
}

 

 

输出：
 

Found pair: {2, two} 
 

 

总结
 

  • 查找 键：使用 map::find，效率更高，O(log n)。
  • 查找 值：可以使用 std::find_if 遍历容器。
  • 查找完整的 键值对：可以直接用 std::find。
 

如果需要频繁查找值，建议使用 std::multimap 或维护一个反向映射的辅助数据结构（如 std::unordered_map<Value, Key>）
 

 

auto it = std::find(m.begin(), m.end(), std::make_pair(2, "two")); 
 

auto 的类型
 

it 的类型是 std::map<int, std::string>::iterator，也就是 std::map 的迭代器类型。
 





原文地址：https://blog.csdn.net/m0_74374651/article/details/144300585


免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！









相关文章
















自学内容网



Copyright © 2015-2024