标签: stl-algorithm

我很好奇如何std:next_permutation实现,所以我提取了gnu libstdc++ 4.7版本并清理了标识符和格式以生成以下演示...

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

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
        ++i;
        if (i == end)
                return false;

        i = end;
        --i;

        while (true)
        {
                It j = i;
                --i;

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin) …

我一直在尝试在C++中找到两个std :: set之间的交集,但我一直收到错误.

我为此创建了一个小样本测试

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

int main() {
  set<int> s1;
  set<int> s2;

  s1.insert(1);
  s1.insert(2);
  s1.insert(3);
  s1.insert(4);

  s2.insert(1);
  s2.insert(6);
  s2.insert(3);
  s2.insert(0);

  set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end());
  return 0;
}

后一个程序不生成任何输出,但我希望有一个新的集合(让我们称之为s3)具有以下值:

s3 = [ 1 , 3 ]

相反,我得到错误:

test.cpp: In function ‘int main()’:
test.cpp:19: error: no matching function for call to ‘set_intersection(std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>)’

我从这个错误中理解的是,没有定义set_intersection接受Rb_tree_const_iterator<int>参数.

此外,我想该std::set.begin()方法返回这种类型的对象,

有没有更好的方法std::set在C++中找到两个的交集？最好是内置功能？

非常感谢!

当想要执行一个副本(1. doable with copy_if)但是从一个容器值到一个指向这些值的指针容器(2.可行transform)时,就出现了一个用例.

可用的工具,我不能做到这一点,在不到两个步骤:

#include <vector>
#include <algorithm>

using namespace std;

struct ha { 
    int i;
    explicit ha(int a) : i(a) {}
};

int main() 
{
    vector<ha> v{ ha{1}, ha{7}, ha{1} }; // initial vector
    // GOAL : make a vector of pointers to elements with i < 2
    vector<ha*> ph; // target vector
    vector<ha*> pv; // temporary vector
    // 1. 
    transform(v.begin(), v.end(), back_inserter(pv), 
        [](ha &arg) { return &arg; }); 
    // 2. 
    copy_if(pv.begin(), pv.end(), …

两者都可用于将函数应用于一系列元素.

在高层次上:

• std::for_each 忽略函数的返回值,并保证执行的顺序.
• std::transform 将返回值赋给迭代器,并不保证执行的顺序.

你什么时候喜欢使用那个？有任何微妙的警告吗？

我一直想知道为什么你不能使用本地定义的类作为STL算法的谓词.

在问题:接近STL算法,lambda,本地类和其他方法,BubbaT提到" 由于C++标准禁止将本地类型用作参数 "

示例代码:

int main() {
   int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   std::vector<int> v( array, array+10 );

   struct even : public std::unary_function<int,bool>
   {
      bool operator()( int x ) { return !( x % 2 ); }
   };
   std::remove_if( v.begin(), v.end(), even() ); // error
}

有谁知道标准中的限制在哪里？禁止当地类型的理由是什么？

编辑:从C++ 11开始,使用本地类型作为模板参数是合法的.

根据std :: shufle上的cppreference.com参考站点,在c ++ 14中不推荐使用以下方法:

template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );

为什么我们不再能够在不传递第三个参数的情况下调用以下函数？

std::random_shuffle(v.begin(),v.end()); //no longer valid in c++14

看起来好像不同的功能减速具有默认参数设置.这背后的原因是什么？是否添加了某种替代方案？

STL算法在C++中非常有用.但有一点令我烦恼的是,他们似乎缺乏可组合性.

例如,假设我有一个vector<pair<int, int>>并且想要将其转换为vector<int>仅包含second该对的成员.这很简单:

std::vector<std::pair<int, int>> values = GetValues();
std::vector<int> result;

std::transform(values.begin(), values.end(), std::back_inserter(result),
    [] (std::pair<int, int> p) { return p.second; });

或者我想过滤vector那些first成员是偶数的对.也很简单:

std::vector<std::pair<int, int>> values = GetValues();
std::vector<std::pair<int, int>> result;

std::copy_if(values.begin(), values.end(), std::back_inserter(result),
    [] (std::pair<int, int> p) { return (p.first % 2) == 0; });

但如果我想同时做两件事呢？没有transform_if算法,并且使用两者transform并且copy_if似乎需要分配临时vector来保存中间结果:

std::vector<std::pair<int, int>> values = GetValues();
std::vector<std::pair<int, int>> temp;
std::vector<int> result;

std::copy_if(values.begin(), values.end(), std::back_inserter(temp),
    [] (std::pair<int, int> …

从标准 来看std::includes:

返回:trueif [first2, last2)为空或者范围中的每个元素[first2, last2)都包含在范围内[first1, last1).false否则返回.

^{注意:由于这是在[alg.set.operations]下,因此必须对范围进行排序}

从字面上看,如果我们让,R1=[first1, last1)并且R2=[first2, last2),这是在评估:

?a?R2 a?R1

但是,这不是实际评估的内容.for R1={1}和R2={1,1,1},std::includes(R1, R2)返回false:

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

int main() {
    std::vector<int> a({1});
    std::vector<int> b({1,1,1});

    // Outputs 'false'
    std::cout << std::boolalpha
        << std::includes(a.begin(), a.end(), b.begin(), b.end()) << '\n';
}

^{住在Wandbox上}

这是令人惊讶的.我用libstdc ++和libc ++验证了它,但是我认为这不是标准库实现中的一个错误,因为它是算法库的一部分.如果这不是std::includes应该运行的算法,那是什么？

当我想知道如何实现C++标准库中的算法时,我总是看看http://en.cppreference.com/w/cpp/algorithm,这是一个很好的来源.但有时我不理解一些实现细节,我需要解释为什么某些特定的方式.例如,在实现中std::copy_n,为什么第一次赋值是在循环之外进行的,因此循环以1？开头？

template< class InputIt, class Size, class OutputIt>
OutputIt copy_n(InputIt first, Size count, OutputIt result)
{
    if (count > 0) {
        *result++ = *first;
        for (Size i = 1; i < count; ++i) {
            *result++ = *++first;
        }
    }
    return result;
}

另外:您是否知道可以解释可能的算法实现的站点？

Today, I arrived at a situation, where I have a vector of tuples, where the tuples might contain several entries. Now I wanted to convert my vector of tuples to a vector of objects, such that the entries of the tuples will exactly match the uniform initialization of my object.

The following code does the job for me, but it is a bit clumsy. I'm asking myself if it might be possible to derive a generic solution that can construct …