标签: stl-algorithm

我正在开发一个C++应用程序.

我有2个点向量

vector<Point2f> vectorAll;
vector<Point2f> vectorSpecial;  

Point2f已定义 typedef Point_<float> Point2f;

vectorAll有1000点而vectorSpecial有10点.

第一步:

我需要根据vectorAll中的顺序对vectorSpecial中的点进行排序.所以像这样:

For each Point in vectorSpecial
    Get The Order Of that point in the vectorAll
    Insert it in the correct order in a new vector

我可以做一个双循环并保存索引.然后根据索引对点进行排序.然而,当我们有很多点时,这种方法花费的时间太长(例如,vectorAll中的10000个点和vectorSpecial中的1000个点,因此千万次迭代)

有什么更好的方法呢？

第二步:

vectorApecial中的某些点可能在vectorAll中不可用.我需要采取最接近它的点(通过使用通常的距离公式sqrt((x1-x2)^2 + (y1-y2)^2))

这也可以在循环时完成,但如果有人对更好的方法有任何建议,我将不胜感激.

非常感谢您的帮助

如果我想计算从a中检索到的一堆数字的总和std::istream,我可以执行以下操作:

// std::istream & is = ...
int total = std::accumulate(std::istream_iterator<int>(is),
                            std::istream_iterator<int>(),
                            0);

但是,如果我想计算它们的平均值,我需要累积两个不同的结果:

• 总和(std::accumulate)
• 总数(std::distance)

有没有办法"合并"这两种算法并在迭代器范围的单次传递中"并排"运行它们？我想做的事情如下:

using std::placeholders;
int total, count;
std::tie(total, count) = merge_somehow(std::istream_iterator<int>(is),
                                       std::istream_iterator<int>(),
                                       std::bind(std::accumulate, _1, _2, 0),
                                       std::distance);
double average = (double)total / count;

这可能吗？

我正在尝试对此进行相反的操作:

std::ostream outs; // properly initialized of course
std::set<int> my_set; // ditto

outs << my_set.size();
std::copy( my_set.begin(), my_set.end(), std::ostream_iterator<int>( outs ) );

它应该是这样的:

std::istream ins;

std::set<int>::size_type size;
ins >> size;

std::copy( std::istream_iterator<int>( ins ), std::istream_iterator<int>( ins ) ???, std::inserter( my_set, my_set.end() ) );

但是我坚持使用'end'迭代器 - 输入交互器不能使用std :: advance,我也不能使用两个具有相同源的流...

有什么优雅的方法如何解决这个问题？当然我可以用于循环,但也许有更好的东西:)

tl; dr:是否可以有效地在双向链表上实现快速排序？在考虑之前我的理解是,不,不是.

前几天我有机会考虑基本排序算法的迭代器要求.基本的O(N²)非常简单.

• 冒泡排序 - 2个前向迭代器将很好地执行,一个拖动另一个.
• 插入排序 - 2个双向迭代器可以.一个用于无序元素,一个用于插入点.
• 选择排序 - 有点棘手但前向迭代器可以做到这一点.

快速排序

std :: sort中的introsort_loop(如在gnu标准库/ hp(1994)/ silicon graphics(1996)中)要求它是random_access.

__introsort_loop(_RandomAccessIterator __first,
         _RandomAccessIterator __last,
         _Size __depth_limit, _Compare __comp)

正如我所期待的那样.

现在经过仔细检查,我无法找到真正的理由要求快速排序.唯一明确要求random_access_iterators的是std::__median需要计算中间元素的调用.常规的香草快速排序不计算中位数.

分区包括一个检查

 if (!(__first < __last))
    return __first;

对双向传输并不是一个有用的检查.但是,应该可以通过检查前一个分区行程(从左到右/从右到左)来替换它,条件是简单

if ( __first == __last ) this_partitioning_is_done = true;

是否可以仅使用双向迭代器相当有效地实现快速排序？递归深度仍然可以保护.

NB.我还没有尝试过实际的实现.

我一直在寻找到<algorithm>的fill和fill_n功能,以及他们给我似乎做同样的事情,但只是有不同的定义.

这是真的,如果不是,它们有什么不同？

他们描述的措辞似乎是差不多的(我在从MSDN阅读fill_n和fill).

如果它们相同,那么可以使用这两种功能有什么好处？

它只是给开发人员更多的选择,还是比另一个更快？

我在N3485 25.3.1 [alg.copy]中查看了C++标准,它定义了4种算法:

• copy
• copy_backward
• copy_if
• copy_n

在描述中copy,有这个注释25.3.1 [alg.copy]/3:

要求:结果不应在[first,last]范围内

也就是说,copy当范围重叠(类似于memcpy)时,并不总是正常工作.

copy_backward并且copy_if有类似的语言禁止重叠范围(分别为25.3.1 [alg.copy]/14和25.3.1 [alg.copy]/8).

但是,没有这样的禁令copy_n,也没有copy_n_backward.这是否意味着copy_n当范围重叠时做正确的事情？

(MSVC++的实现copy_n似乎委托给了std::memmove,所以我知道它在MSVC++ 2013上是安全的.但是如果标准暗示的话,我不想依赖它)

我有一个名为Graph的C++类,它有一个算法方法for_each_node().我可以把它变成一个模板,像这样:

template <class UnaryFunction>
UnaryFunction Graph::for_each_node (UnaryFunction f)
{
     /* ... */
}

或者使用std :: function,如下所示:

typedef std::function<void (Node&)> ForEachNodeFunc;

ForEachNodeFunc Graph::for_each_node (ForEachNodeFunc f)
{
     /* ... */
}

标准算法,例如std :: for_each,使用第一种方法,而一些库,例如gtkmm(它是GTK +的C++绑定),将函数作为包含它们的对象的函数指针.

每个选项有哪些优点和缺点？我不知道该选哪个.应该影响选择的是什么:我的Graph类是一个类模板,或者算法方法或速度要求预计会使用多少个不同的函数？

为什么_n版本的copy,fill并且generate已经在C++ 11中提供了,为什么只有这些算法呢？

为什么有些STL算法提供了额外的'_if'功能而不是重载它？

// example:
find(beg, end, val);
find_if(beg, end, pred);

难道他们只是重载这些算法而不是制作额外的_if功能吗？

我有一个可以简化为基本的并行代码:

#include <algorithm>
#include <vector>

struct TKeyObjPtr;

class TObj
{
public:
  virtual void Calculate(TKeyObjPtr const &) = 0;
};

struct TKeyObjPtr
{
  int Key;
  TObj *ObjPtr;
};

void Calculate(std::vector<TKeyObjPtr> const &KeyObjPtrVec)
{
  #pragma omp parallel for
  for (auto It1= KeyObjPtrVec.begin(); It1!=KeyObjPtrVec.end(); ++It1)
    for (auto It2= It1+1; It2!=KeyObjPtrVec.end() && It2->Key==It1->Key; ++It2)
      It1->ObjPtr->Calculate(*It2);
}

我想通过使用c ++ 17并行算法来实现代码的现代化.不幸的是,我在重写这么简单的代码时遇到了麻烦.

一个选项将使用boost::counting_iterator:

void Calculate(std::vector<TKeyObjPtr> const &KeyObjPtrVec)
{
  std::for_each(std::execution::par_unseq,
    boost::counting_iterator<std::size_t>(0u),
    boost::counting_iterator<std::size_t>(KeyObjPtrVec.size()),
    [&KeyObjPtrVec](auto i)
      {
        for (auto j= i+1; j<KeyObjPtrVec.size() && KeyObjPtrVec[j].Key==KeyObjPtrVec[i].Key; ++j)
          KeyObjPtrVec[i].ObjPtr->Calculate(KeyObjPtrVec[j]); …