C++容器中实用的查找功能

C++标准中std提供了几种容器,它们包括顺序容器,比如vector, list, deque, queue, stack等,关联容器 ,比如map, set等,其中使用频率比较高的容器是vecotor向量容器、map键值对容器,我们经常会使用这两个容器来存储数据,然后根据不同的场景来查找获取容器内的值。而本文接下来将说明从这两类容器中快速查找获取数据的方法。

一、vector容器查找功能

vector容器自身没有提供查找函数,这里借助标准模版库algorithm提供的find,  使用的时候需要包含该头文件。

1、首先定义vector容器变量,然后存入数据,接着遍历打印容器内的所有数据,最后调用algorithm提供的函数find从vector向量中查找数据,algorithm提供的函数find需要输入三个入参数,第一个参数是容器开始查找的迭代器变量,第二个变量是容器结束查找的迭代器变量,第三个参数是需要查找的数据。

#include <vector>
#include <algorithm>

// 定义vecotor,然后存入数据
std::vector<std::string> vec_str;
vec_str.push_back("abc");
vec_str.push_back("def");
vec_str.push_back("fhj");
vec_str.push_back("123");
vec_str.push_back("456");

// 遍历打印vector容器内的数据
std::vector<std::string>::iterator iter = vec_str.begin();
for(iter = vec_str.begin(); iter != vec_str.end(); iter++)
{
    LOG(INFO) << *iter;
}
LOG(INFO) << "======";

// 调用find函数查找,内容为“def”的信息
iter = find(vec_str.begin(),vec_str.end(), "def");
if (iter != vec_str.end())
{
    LOG(INFO) << "find info: " << *iter;
}
LOG(INFO) << "======";

2、运行程序,输出的内容如下图所示,容器内存在需要查找的数据,返回迭代器变量,我们根据迭代器变量输出数据内容

二、map容器查找功能

map容器自身提供了查找功能,同时它也支持使用标准模版库algorithm提供的find函数。

1、首先定义map容器变量,写入数据,再遍历输出容器内的数据,接着调用map容器自身提供的find函数来查找key为2的数据,返回迭代器变量,然后根据这个迭代器变量输出键值,接下来调用algorithm提供的find函数,需要注意的是第三个参数输入的是迭代器的取值,最后也是返回迭代器变量。

#include <map>
#include <algorithm> 

// 首先定义map容器变量,写入数据
std::map<int, std::string> map_str;
map_str[1] = "aa";
map_str[2] = "bb";
map_str[3] = "cc";

// 遍历输出容器内的所有内容
std::map<int, std::string>::iterator iter_map;
for(iter_map = map_str.begin(); iter_map != map_str.end(); iter_map++)
{
    LOG(INFO) << "key: " << iter_map->first <<" value "<< iter_map->second;
}
LOG(INFO) << "======";

// 调用map容器自身提供的find函数,查找key为2的数据
iter_map = map_str.find(2);
if (iter_map != map_str.end())
{
    LOG(INFO) << "key: " << iter_map->first <<" value: "<< iter_map->second;
}
LOG(INFO) << "======";

// 调用algorithm提供的find函数来查找数据,注意find的第三个参数输入的是迭代器的取值
std::map<int, std::string>::iterator iter_map_ret;
iter_map_ret = find(map_str.begin(), map_str.end(), *iter_map);
if (iter_map_ret != map_str.end())
{
    LOG(INFO) << "result, key: " << iter_map_ret->first <<" value: "<< iter_map_ret->second;
}

2、运行程序,输出的内容如下图所示

三、键自定义的map容器查找功能

map容器使用过程中,有时候为了程序的可维护性以及降低代码的复杂度,需要自定义类作为map的键,在这种场景下,上面的查找方法是否也能够生效呢?接下来让我们进行验证。

1、首先自定义类JKeyPair来作为map的key,  如果自定义对象要作为map的键,那么需要重载operator<运算符,而如果要使用algorithm中的find,需要重载operator==运算符

#include <iostream>

/// 类的定义
class JKeyPair
{
public:
    JKeyPair(const std::string &strName, int iIndex);
    ~JKeyPair();

    std::string GetName(void);
    int GetIndex(void);

    // 自定义map中的key,需要重载operator<运算符(一定要记得加上const, 否则调用出错)
    bool operator<(const JKeyPair &rhs) const;

    // 自定义map中的key,使用algorithm中的find,需要重载operator==运算符(一定要记得加上const, 否则调用出错)
    bool operator==(const JKeyPair& rhs) const;
private:
    std::string m_strName;
    int m_iIndex;
};


/// 类的实现
JKeyPair::JKeyPair(const std::string &strName, int iIndex)
    :m_strName(strName),m_iIndex(iIndex)
{}

JKeyPair::~JKeyPair()
{}

std::string JKeyPair::GetName(void)
{
    return m_strName;
}

int JKeyPair::GetIndex(void)
{
    return m_iIndex;
}

bool JKeyPair::operator<(const JKeyPair &rhs) const
{
    if (m_iIndex < rhs.m_iIndex)
    {
        return true;
    }
    else if ((m_iIndex ==  rhs.m_iIndex)
             && (m_strName < rhs.m_strName))
    {
        return true;
    }
    return false;
}


bool JKeyPair::operator==(const JKeyPair& rhs) const
{
    if ((m_iIndex ==  rhs.m_iIndex)
            && (m_strName == rhs.m_strName))
    {
        return true;
    }
    return false;
}

2、验证调用map自身提供的find函数,其测试代码如下图所示

// 定义map容器变量,key是自定义类型,然后写入数据
std::map<JKeyPair, std::string> map_info;
JKeyPair key_pair_1("one", 1);
map_info[key_pair_1] = "value_one";
JKeyPair key_pair_2("two", 2);
map_info[key_pair_2] = "value_two";
JKeyPair key_pair_3("three", 2);
map_info[key_pair_3] = "value_three";

// 循环遍历容器内数据
std::map<JKeyPair, std::string>::iterator iter;
for(iter = map_info.begin(); iter != map_info.end(); iter++)
{
    JKeyPair key_pair = iter->first;
    LOG(INFO) << "name : " << key_pair.GetName();
    LOG(INFO) << "index : " << key_pair.GetIndex();
    LOG(INFO) << "value : " << iter->second;
}
LOG(INFO) << "======";

// 通过调用map自身提供的函数find,来查找键为key_pair_2的数据
iter = map_info.find(key_pair_2);
if (iter != map_info.end())
{
    LOG(INFO) << "find, value : " << iter->second;
}

3、从运行的结果看,使用自定义对象作为key值,map容器提供的find函数能够正确运行,并且从实际操作过程中,可以得出,map容器提供的find函数,自定义对象不需要重载operator==运算符。

4、接着再验证algorithm中的find,从实际操作过程中,自定义对象需要重载operator==运算符,测试代码段如下图所示,其中find中第三个参数是上一步骤中调用map自身的find返回的迭代器变量

// 使用alogrithm提供的find来查找map容器的数据
std::map<JKeyPair, std::string>::iterator iter_map_key;
iter_map_key = std::find(map_info.begin(), map_info.end(), *iter);
if (iter_map_key != map_info.end())
{
    JKeyPair key_pair = iter_map_key->first;
    LOG(INFO) << "result, self key: " << key_pair.GetName()  << "/" << key_pair.GetIndex()
              <<" value: "<< iter_map_key->second;
}

5、运行后打印的结果信息看,能够正确调用algorithm中的find来查找map中的数据

四、总结

到这里,我们已经将容器vector,map的查找功能介绍完成。接下来梳理总结。vector容器自身没有提供查找函数,因此,需要调用algorithm中的find来快速查找数据。map容器自身既提供了查找函数,也支持使用algorithm中的find来快速查找数据。而自定义对象作为map容器的键的情况下,如果需要支持上面的场景,那么自定义类需要重载operator<和operator==运算符。

发表评论

电子邮件地址不会被公开。 必填项已用*标注