Utilisation de STL / Boost pour rechercher et modifier des éléments correspondants dans un vecteur

Question

Disons que j'ai un vecteur déclaré comme ceci:

struct MYSTRUCT
{
 float a;
 float b;
};

std::vector<MYSTRUCT> v;

Maintenant, je veux trouver tous les éléments de v qui partagent le même a et faire la moyenne de leur b, c'est-à-dire.

Say v contient ces cinq éléments {a, b}: {1, 1}, {1, 2}, {2, 1}, {1, 3}, {2, 2}

Je veux obtenir v [0], v [1], v [3] (où a est 1) et la moyenne b: (1 + 2 + 3) / 3 = 2, et v [2] et v [4] (où a est 2) et moyenne b: (1 + 2) / 2 = 1,5

Ensuite, v ressemblera à ceci: {1, 2}, {1, 2}, {2, 1.5}, {1, 2}, {2, 1.5}

Je ne connais pas très bien STL ou Boost, je ne peux donc que comprendre comment faire cela "bruteforce". C ++, mais je suppose que les bibliothèques STL (for_each?) et Boost (lambda?) peuvent résoudre ce problème de façon plus élégante.

MODIFIER Juste pour référence, voici ma façon (de travail) de la force brute de le faire:

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

En réfléchissant à voix haute, cela peut finir assez bêtement:

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

Hmm. Pas complètement stupide, mais peut-être pas convaincant non plus ...

Answer 2

Esquisse d'une solution:

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

Mais ce n’est pas une bonne idée, car ce n’est pas exactement ce qui a été demandé (grâce au genre), et je ne me sens toujours pas vraiment propre. Je pense que certains filter_iterators et transform_iterators ou quelque chose du genre pourraient éventuellement donner une réponse beaucoup plus fonctionnelle.

Answer 3

Une autre approche, celle-ci n’est pas en place, même si je pense que la complexité temporelle est identique à celle du temps.

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

Encore une fois, c’est une façon légèrement élégante de coder la solution de force brute, et non une belle manière fonctionnelle.

Answer 4

Peut-être une approche de force brute? ...

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;

J'ai testé cela avec les valeurs que vous avez fournies et obtenu le vecteur requis - ce n'est pas exactement optimal, mais je pense que c'est assez facile à suivre (peut-être préférable à un algorithme complexe).

Answer 5

Évitez le style C! C ++ n’est pas conçu pour cela. J'aimerais mettre l'accent sur la clarté et la lisibilité.

#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

Vous pouvez utiliser la & partition; partition " algorithme avec "accumuler".

Exemple

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

Documentation à partir des en-têtes 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

Il semble que le moyen le plus simple consiste à exécuter un foncteur moyennement complexe sur la colonne:

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

En écrivant en C ++, vous devez maintenir un équilibre entre la réutilisabilité (réutiliser par exemple les algorithmes et les structures de données existants) et la lisibilité. onebyone était proche, mais sa solution peut encore être améliorée:

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

Points bonus pour avoir "réutilisable" et "moyenne" réutilisable type.

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