使用 STL/Boost 查找和修改向量中的匹配元素

Question

假设我有一个这样声明的向量：

struct MYSTRUCT
{
 float a;
 float b;
};

std::vector<MYSTRUCT> v;

现在，我想找到 v 中共享相同 a 的所有元素，并对它们的 b 求平均值，即

说 v 包含这五个元素 {a, b}: {1, 1}， {1, 2}, {2, 1}, {1, 3}, {2, 2}

我想得到 v[0], v[1], v[3] (其中 a 为 1) 和平均值 b ：(1 + 2 + 3)/3 = 2，v[2]和v[4]（其中a为2）和平均值b：(1+2)/2 = 1.5

之后v将如下所示：{ 1, 2}, {1, 2}, {2, 1.5}, {1, 2}, {2, 1.5}

我对 STL 或 Boost 不太熟悉，所以我只能弄清楚如何做到这一点C++ 中的“bruteforce”方式，但我猜测 STL（for_each？）和 Boost（lambda？）库可以更优雅地解决这个问题。

编辑仅供参考，这是我的（工作）强力方法：

for(int j = 0; j < tempV.size(); j++)
{
    MYSTRUCT v = tempV.at(j);
    int matchesFound = 0;

    for(int k = 0; k < tempV.size(); k++)
    {
        if(k != j && v.a == tempV.at(k).a)
        {
            v.b += tempV.at(k).b;
            matchesFound++;
        }
    }

    if(matchesFound > 0)
    {
        v.b = v.b/matchesFound;
    }

    finalV.push_back(v);
}

Answer 1

只是大声思考，这可能会变得相当愚蠢：

struct Average {
    Average() : total(0), count(0) {}
    operator float() const { return total / count; }
    Average &operator+=(float f) {
        total += f;
        ++count;
    }
    float total;
    int count;
};

struct Counter {
    Counter (std::map<int, Average> &m) : averages(&m) {}
    Counter operator+(const MYSTRUCT &s) {
         (*averages)[s.a] += s.b;
         return *this;
    }
    std::map<int, Average> *averages;
};

std::map<int, Average> averages;
std::accumulate(v.begin(), v.end(), Counter(averages));
BOOST_FOREACH(MYSTRUCT &s, v) {
    s.b = averages[s.a];
}

嗯。不完全愚蠢，但也许也不引人注目......

Answer 2

解决方案的草图：

sort(v.begin(), v.end());
vector<MYSTRUCT>::iterator b = v.begin(), e = v.end();
while (b != e) {
    vector<MYSTRUCT>::iterator m = find_if(b, e, bind(&MYSTRUCT::a, _1) != b->a);
    float x = accumulate(b, m, 0.f, _1 + bind(&MYSTRUCT::b,_2)) / (m-b);
    for_each(b, m, bind(&MYSTRUCT::a, _1) = x);
    b = m;
}

不过，这不是一个很好的解决方案，因为它不完全是所要求的（感谢排序），而且对我来说仍然感觉不太干净。我认为一些filter_iterators和transform_iterators或其他东西可能会给出更加函数式的答案。

Answer 3

另一种方法，虽然我认为它在时间复杂性方面渐近相同，但这种方法并不到位。

typedef map<float, vector<float>> map_type;
map_type m;
BOOST_FOREACH(MYSTRUCT const &s, v) {
    m[s.a].push_back(s.b);
}
BOOST_FOREACH(map_type::reference p, m) {
    float x = accumulate(p.second.begin(), p.second.end(), 0.0f) / p.second.size();
    p.second.assign(1, x);
}
BOOST_FOREACH(MYSTRUCT &s, v) {
    s.b = m[s.a].front();
}

不过，这只是一种稍微优雅的暴力解决方案编码方式，而不是一种很好的函数式方式。

Answer 4

也许是一种蛮力方法？...

struct MYAVG
{
    int count;
    float avg;  
};

// first pass - calculate averages
for ( vector < MYSTRUCT >::iterator first = v.begin(); 
      first != v.end(); ++first )
{
    MYAVG myAvg;
    myAvg.count = 1;
    myAvg.avg = first->b;

    if ( mapAvg.find( first->a ) == mapAvg.end() )
        mapAvg[ first->a ] = myAvg;
    else
    {
        mapAvg[ first->a ].count++;
        mapAvg[ first->a ].avg = 
            ( ( mapAvg[ first->a ].avg * ( mapAvg[ first->a ].count - 1 ) ) 
                + myAvg.avg ) / mapAvg[ first->a ].count;
    }
}

// second pass - update average values
for ( vector < MYSTRUCT >::iterator second = v.begin(); 
      second != v.end(); ++second )
    second->b = mapAvg[ second->a ].avg;

我已经用您提供的值对此进行了测试并获得了所需的向量 - 这并不完全是最佳的，但我认为它很容易遵循（可能比复杂的算法更可取） 。

Answer 5

避免C风格！这不是 C++ 的设计目的。我想强调清晰度和可读性。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <vector>

#include <boost/assign/list_of.hpp>

using namespace std;
using namespace boost::assign;

struct mystruct
{
  mystruct(float a, float b)
    : a(a), b(b)
  { }

  float a;
  float b;
};

vector <mystruct> v =
  list_of ( mystruct(1, 1) ) (1, 2) (2, 1) (1, 3) (2, 2);

ostream& operator<<(
  ostream& out, mystruct const& data)
{
  out << "{" << data.a << ", " << data.b << "}";
  return out;
}

ostream& operator<<(
  ostream& out, vector <mystruct> const& v)
{
  copy(v.begin(), v.end(),
       ostream_iterator <mystruct> (out, " "));
  return out;
}

struct average_b
{
  map <float, float> sum;
  map <float, int> count;

  float operator[] (float a) const
  {
    return sum.find(a)->second / count.find(a)->second;
  }
};

average_b operator+ (
  average_b const& average,
  mystruct const& s)
{
  average_b result( average );

  result.sum[s.a] += s.b;
  ++result.count[s.a];

  return result;
}

struct set_b_to_average
{
  set_b_to_average(average_b const& average)
    : average(average)
  { }

  mystruct operator()(mystruct const& s) const
  {
    return mystruct(s.a, average[s.a]);
  }

  average_b const& average;
};

int main()
{
  cout << "before:" << endl << v << endl << endl;

  transform(v.begin(), v.end(),
            v.begin(), set_b_to_average(
              accumulate(v.begin(), v.end(), average_b())
            ));

  cout << "after:" << endl << v << endl << endl;
}

Answer 6

您可以将“分区”算法与“累积”一起使用。

示例文档

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

struct test
{
    float a;
    float b;

    test(const float one, const float two)
        : a(one), b(two)
    {
    }
};

struct get_test_a {
    float interesting;

    get_test_a(const float i)
        : interesting(i)
    {
    }

    bool operator()(const test &value) const
    {
        static const float epi = 1e-6;
        return value.a < interesting + epi &&
            value.a > interesting - epi;
    }
};

struct add_test_b {
    float operator()(const float init, const test &value) const
    {
        return init + value.b;
    }
};

int main(int argc, char **argv)
{
    using std::partition;
    using std::accumulate;
    using std::distance;
    typedef std::vector<test> container;

    container myContainer;

    // Say 'myVector' contains these five elements {a, b}:
    // {1, 1}, {1, 2}, {2, 1}, {1, 3}, {2, 2}
    myContainer.push_back(test(1, 1));
    myContainer.push_back(test(1, 2));
    myContainer.push_back(test(2, 1));
    myContainer.push_back(test(1, 3));
    myContainer.push_back(test(2, 2));

    // I want to get v[0], v[1], v[3] (where a is 1) and
    // average b: (1 + 2 + 3)/3 = 2,
    // and v[2] and v[4] (where a is 2) and average b: (1+2)/2 = 1.5
    const container::iterator split = 
        partition(myContainer.begin(), myContainer.end(),
                  get_test_a(1));

    const float avg_of_one =
        accumulate(myContainer.begin(), split, 0.0f, add_test_b())
        / distance(myContainer.begin(), split);

    const float avg_of_others =
        accumulate(split, myContainer.end(), 0.0f, add_test_b())
        / distance(split, myContainer.end());

    std::cout << "The 'b' average of test values where a = 1 is "
              << avg_of_one << std::endl;

    std::cout << "The 'b' average of the remaining test values is "
              << avg_of_others << std::endl;

    return 0;
}

---

gcc 标头中的

  /**
   *  @brief Move elements for which a predicate is true to the beginning
   *         of a sequence.
   *  @ingroup mutating_algorithms
   *  @param  first   A forward iterator.
   *  @param  last    A forward iterator.
   *  @param  pred    A predicate functor.
   *  @return  An iterator @p middle such that @p pred(i) is true for each
   *  iterator @p i in the range @p [first,middle) and false for each @p i
   *  in the range @p [middle,last).
   *
   *  @p pred must not modify its operand. @p partition() does not preserve
   *  the relative ordering of elements in each group, use
   *  @p stable_partition() if this is needed.
  */
  template<typename _ForwardIterator, typename _Predicate>
    inline _ForwardIterator
    partition(_ForwardIterator __first, _ForwardIterator __last,
          _Predicate   __pred)

  /**
   *  @brief  Accumulate values in a range with operation.
   *
   *  Accumulates the values in the range [first,last) using the function
   *  object @a binary_op.  The initial value is @a init.  The values are
   *  processed in order.
   *
   *  @param  first  Start of range.
   *  @param  last  End of range.
   *  @param  init  Starting value to add other values to.
   *  @param  binary_op  Function object to accumulate with.
   *  @return  The final sum.
   */
  template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
    inline _Tp
    accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
           _BinaryOperation __binary_op)

Answer 7

似乎最简单的方法是在集合上运行一个中等复杂的函子：

struct CountAllAverages {
    typedef std::pair<float, unsigned> average_t;
    std::map<float, average_t> averages;
    void operator()(mystruct& ms) {
        average_t& average = averages[ms.a];
        average.second++;
        average.first += ms.b;
    }
    float getAverage(float a) { return averages[a].first/averages[a].second; }
};

Answer 8

编写C++ 时，您应该在可重用性（例如重用现有算法和数据结构）和可读性之间保持平衡。 onebyone 很接近，但他的解决方案可以进一步改进：

template<class T>
struct average {
  T total;
  int count;
  mutable bool calculated;
  mutable T average_value;

  average & operator+=(T const & value) {
    total += value;
    ++count;
    calculated = false;
  }

  T value() const {
    if(!calculated) {
      calculated = true;
      average_value = total / count;
    }
    return average_value;
  }
};


std::map< float, average<float> > averages;
BOOST_FOREACH(MYSTRUCT &element, v) {
  averages[element.a] += element.b;
}

BOOST_FOREACH(MYSTRUCT &element, v) {
  element.b = averages[element.a].value();
}

拥有可重用的“平均”类型的奖励积分。

Answer 9

struct MYSTRUCT { 
    float x;
    float y;

    operator float() const { return y; }
};

class cmp { 
    float val;
public:
    cmp(float v) : val(v) {}      
    bool operator()(MYSTRUCT const &a) { return a.x != val; }
};

float masked_mean(std::vector<MYSTRUCT> const &in, MYSTRUCT const &mask) { 
    std::vector<float> temp;
    std::remove_copy_if(in.begin(), in.end(), std::back_inserter(temp), cmp(mask.x));
    return std::accumulate(temp.begin(), temp.end(), 0.0f) / temp.size();
}