STL / Boostを使用して、ベクトル内の一致する要素を見つけて変更する
https://stackoverflow.com/questions/1406995
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
次のように宣言されたベクターがあるとします：
struct MYSTRUCT
{
float a;
float b;
};
std::vector<MYSTRUCT> v;
今、同じaを共有するvのすべての要素を見つけて、それらのbを平均したい、つまり
Say vには、{a、b}の5つの要素が含まれています：{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);
}
解決
声を出して考えてみると、これはかなりばかげているかもしれません：
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];
}
うーん。完全にばかげているわけではありませんが、おそらく魅力的でもありません...
他のヒント
ソリューションのスケッチ：
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か何かがもっと機能的なスタイルの答えを与える可能性があると思います。
別のアプローチ、これはインプレースではありませんが、時間の複雑さに関して漸近的には同じだと思います。
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();
}
しかし、これは、ブルートフォースソリューションをコーディングするためのちょっとエレガントな方法であり、機能的なスタイルの良い方法ではありません。
おそらく総当たり攻撃のアプローチ？...
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;
指定した値でこれをテストし、必要なベクトルを取得します-最適ではありませんが、従うのは非常に簡単だと思います（複雑なアルゴリズムよりも望ましい場合があります）。
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;
}
「パーティション」を使用できます。アルゴリズムと「累積」
例
#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)
コレクションに対して適度に複雑なファンクターを実行するのが最も簡単な方法のようです：
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; }
};
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();
}
再利用可能な「平均」を持つことに対するボーナスポイントタイプ。
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();
}
所属していません StackOverflow
