在集合或列表中按顺序查找缺失的数字

Question

如果a std::set或std::list包含一系列自然数(1,2,3 ......).标准库中是否有一个函数可以找到丢失的数字？

Answer 1

你可以std::mismatch()使用一系列自然数.为了节省空间,我认为boost::counting_iterator这里的作品很奇妙:

#include <iostream>
#include <list>
#include <boost/iterator/counting_iterator.hpp>
int main()
{
    std::list<int> l = {1,2,3,4,6,7,8,9};
    auto i = mismatch(l.begin(), l.end(), boost::counting_iterator<int>(1));
    if(i.first==l.end())
            std::cout << "no missing numbers\n";
    else
            std::cout << "the first missing number is " << *i.second << '\n';

}

测试运行:

~ $ g++ -std=c++0x -pedantic -Wall -Wextra -o test test.cc
~ $ ./test
the first missing number is 5