استخدام 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، لذا يمكنني فقط معرفة كيفية القيام بذلك بطريقة "bruteforce" في C++، لكنني أعتقد أن مكتبات 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;
}

إنها ليست فكرة رائعة، لأنها ليست بالضبط ما تم طلبه (بفضل هذا النوع)، وما زالت لا تبدو نظيفة حقًا بالنسبة لي.أعتقد أن بعض مرشحات التصفية والتحويلات أو شيء من هذا القبيل يمكن أن يقدم إجابة أكثر وظيفية.

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;
}

---

التوثيق من رؤوس دول مجلس التعاون الخليجي

  /**
   *  @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();
}