1

我想要的：在另一个迭代器（我们称之为基迭代器）之后的下一个元素的迭代器，它的字典序大于（>）该基迭代器指向的元素（也就是说，如果我有一个'a'，其余的是[c,d,a,b] 我想要 b，或者更确切地说是 b) 的迭代器。我不知道可用于此的 <algorithm> 函数，因此如果您愿意，我将“手动”进行操作。

我认为我可以做到这一点：运行这个 lambda 并在集合上进行某种累积：

[mism.first](it_t acc, it_t el) 
{ 
    if(*el > *mism.first) { 
        return iter_min(acc,el); 
    } 
    return acc; 
}

（当 *a<=*b 时，iter_min(a,b) 是 a，mism.first 被称为“基本迭代器”）。但是由于累积适用于值而不是迭代器，所以我不能。迭代器有类似的东西吗？如果不是，你会说我应该写它（我不认为我会过度锻炼自己）还是我只是以“错误”的方式去做（顺便说一句，我最终会交换迭代器指向的元素。我知道这听起来很像next_permutation，但是虽然我所做的与排列有很大关系，但这并不是我想要的）？

4

3 回答 3

2

The easiest possibility I see is to create a range that can be iterated consisting of with successive iterators from [base, end). This is possible with the Boost.Iterators counting_iterator, but should be fairly easy to implement even without boost.

Your proposed lambda would then work almost as is:

some_iterator base = ..., end = ...;
some_iterator the_next_least_thing =
  std::accumulate(boost::make_counting_iterator(base),
                  boost::make_counting_iterator(end),
                  end,
                  [=](some_iterator acc, some_iterator cur) { 
                     return (*cur > *base && (acc == end || *cur < *acc)) ? cur : acc });
于 2012-10-18T22:02:13.183 回答
1

要查找大于基数的第一个std::find_if元素，您可以尝试使用lambda 谓词，如果指向的当前元素大于基迭代器指向的元素，则返回 true。由于 lambda 不幸不是多态的，因此您需要使用指定类型std::iterator_traits（以便它也适用于指针）。

要找到大于基数的最小元素，您需要进行线性扫描，重复查找剩余列表中大于基数的第一个元素，然后检查它是否小于当前最小值。每次更新最小值时，也会将迭代器增加到当前最小值，这样您只需在剩余部分中寻找下一个候选者。这使得这个算法O(N)在元素的数量上N。

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

template<typename FwdIt>
FwdIt first_larger(FwdIt first, FwdIt last, FwdIt base)
{
    typedef typename std::iterator_traits<FwdIt>::value_type T;

    return std::find_if(first, last, [=](T const& elem) {
         return elem > *base;
    });
}

template<typename FwdIt>
FwdIt first_larger(FwdIt first, FwdIt last)
{
    return first_larger(first, last, first);
}

template<typename FwdIt>
FwdIt min_larger(FwdIt first, FwdIt last)
{
    typedef typename std::iterator_traits<FwdIt>::value_type T;
    auto min = last;
    auto found = false;

    for(auto it = first; it != last; ++it) {
         auto m = first_larger(it, last, first);         
         if (m == last) break;         
         it = min = m;
         found = true;        
    }
    return found? min : last;
}

int main()
{
    std::array<int,11> arr = {{ 54, 314, 5, 7, 1, -1, 0, 14, 9, 8, 6 }};

    auto b = &arr[3]; 
    auto f = first_larger(b, arr.end());
    auto m = min_larger(b, arr.end());

    std::cout << *b << "\n"; // 7
    if(f != arr.end()) std::cout << *f << "\n"; // 14
    if(m != arr.end()) std::cout << *m << "\n"; // 8 

    return 0;
}

您可能可以将其概括为一个函数

template<typename FwdIt, typename Pred, typename Cmp>
FwdIt min_element_if(FwdIt first, FwdIt last, Pred pred, Cmp cmp)
{
    // return iterator to smallest element satisfying Predicate
}

和其他设置Cmp等于等的重载operator<。不幸的是，STL 不包含更基本算法的这种组合。您可以查看Boost.Iterator以使用过滤器适配器

 // equivalent to min_element_if(first, last, pred)
 min_element(boost::make_filter_iterator(first, last, pred),
             boost::make_filter_iterator(last, last, pred));
于 2012-10-18T20:00:15.353 回答
1

使用 find_if，提供你的 iterator+1 作为起点：

bool mycomp (char c1, char c2)
{ return lexicographical_compare(*c1,*c1,*c2,*c2); }    

vector<char>::iterator nextBigger = find_if(it+1,end,mycomp)

改编自std lib 的 lexicographic_compare 例程和find_if。

于 2012-10-18T22:20:31.237 回答