Using STL / Boost to find and change related elements in a vector

Question

Let's say I have a vector declared as follows:

struct MYSTRUCT { float a; float b; }; std::vector<MYSTRUCT> v; 

Now I want to find all elements of v that have the same a, and average them b, i.e.

Say v contains these five elements {a, b}: {1, 1}, {1, 2}, {2, 1}, {1, 3}, {2, 2}

I want to get v [0], v [1], v [3] (where a is 1) and the average value of b: (1 + 2 + 3) / 3 = 2, v [2] and v [4] ( where a is 2) and the average value of b: (1 + 2) / 2 = 1.5

Then v will look like this: {1, 2}, {1, 2}, {2, 1.5}, {1, 2}, {2, 1.5}

I am not very familiar with STL or Boost, so I can only figure out how to do this with "brute force" in C ++, but I assume that the STL (for_each?) And Boost (lambda?) Libraries can solve this more elegantly .

EDIT For reference only, here is my (working) way to iterate over:

 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 && va == tempV.at(k).a) { vb += tempV.at(k).b; matchesFound++; } } if(matchesFound > 0) { vb = vb/matchesFound; } finalV.push_back(v); } 

Answer 1

Just out loud, it can end up pretty stupid:

 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)[sa] += sb; 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) { sb = averages[sa]; } 

Hm. Not really stupid, but maybe not attractive ...

Answer 2

Solution sketch:

 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)) / (mb); for_each(b, m, bind(&MYSTRUCT::a, _1) = x); b = m; } 

This is not very cool, since it is not quite what was requested (thanks), and is still not very clean for me. I think some filter_iterators and transform_iterators or something can give a much more functional answer.

Answer 3

Another approach, this one is not in place, although I consider it to be temporary complex asymptotically the same.

 typedef map<float, vector<float>> map_type; map_type m; BOOST_FOREACH(MYSTRUCT const &s, v) { m[sa].push_back(sb); } 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) { sb = m[sa].front(); } 

Again, this is just a slightly elegant way of coding a brute force solution, rather than a nice functional style.

Answer 4

Perhaps a brute force approach? ...

 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; 

I tested this with the values ​​you provided and get the required vector. This is not entirely optimal, but I think it is quite easy to accomplish (maybe more preferable for a complex algorithm).

Answer 5

Avoid C-style! This is not what C ++ is for. I would like to emphasize clarity and readability.

 #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[sa] += sb; ++result.count[sa]; 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(sa, average[sa]); } 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

You can use the "partition" algorithm along with "accumulate".

Example

 #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 header documentation

  /** * @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 @pi in the range @p [first,middle) and false for each @pi * 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

When writing C ++, you must maintain a balance between reuse (e.g. reuse existing algorithms and data structures) and readability. onebyone was close, but its solution can be further improved:

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

Bonus points for the ability to reuse the "average" type.

Answer 8

It seems the easiest way is to run a moderately complex functor over colelction:

 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 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 ax != 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(); }