이글의 한글판은 다음 링크를 따라 가시면 됩니다.
C++이야기 스물여덟번째: map container에 STL algorithm적용하기
Have you ever applied STL algorithms to a map container? As you know, a map is a container in which you can store key&value pairs and typically you may want to apply STL algorithms to values, not pairs because you may be more interested in values than key&value pairs. But STL algorithms and standard functors are not written with this difference in mind. So it’s a common practice to define a new adaptor class when applying STL algorithms to a map container. In this article, I’d like to explain you why to define an adaptor class and how to avoid that using boost::bind().
Given a class as follows,
class Elem {
public:
Elem() : m_name(), m_val() {}
Elem(const string& name, int val) : m_name(name), m_val(val) {}
const string& GetName() const
{
return m_name;
}
int GetValue() const
{
return m_val;
}
void SetValue(int val)
{
m_val = val;
}
void Print() const
{
cout << GetName() << “‘s value ==> ” << GetValue() << endl;
}
private:
string m_name;
int m_val;
};
let’s add several pairs to a map<string, Elem>.
// the ‘m’ container refers to this map afterwards
map<string, Elem> m;
m[“1”] = Elem(“1”, 1);
m[“2”] = Elem(“2”, 2);
m[“3”] = Elem(“3”, 3);
m[“4”] = Elem(“4”, 4);
m[“5”] = Elem(“5”, 5);
Let’s assume that you want to get Elem object’s values. You would write the following code fragment to achieve that.
// First, you define a vector<int> which stores Elem object’s values
vector<int> vi(m.size());
// Run a for loop over the map iterator
for (map<string, Elem>::iterator it = m.begin(); it != m.end(); ++it)
{
vi.push_back(it->second.GetValue());
}
You who are familiar with the STL don’t want to leave the code as above because you can make the code more concise, if you use STL algorithm. The less code, the better software. right? Then you decide to use transform() algorithm instead of the handcrafted for loop.
#include <algorithm>
#include <functional>
……
vector<int> vi(m.size());
// We should use mem_fun_ref instead of mem_fun because
//’m’ is a map of <string, Elem> pairs, not <string, Elem*>
transform(m.begin(), m.end(), vi.begin(), mem_fun_ref(&Elem::GetValue));
Do you expect the above code fragments compiles and works? Unfortunately not! because transform() expects pair<string, Elem> object, not Elem object. Let’s see more carefully transform() algorithm itself to better understand why compliation error happens
// Extract the core part of the algorithm to explain it
template<typename _InputIterator, typename _OutputIterator,
typename _UnaryOperation>
_OutputIterator
transform(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _UnaryOperation __unary_op)
{
for ( ; __first != __last; ++__first, ++__result)
*__result = __unary_op(*__first);
return __result;
}
As you can see the algorithm dereferences ‘first’ iterator and I passes the map<string, Elem>::iterator, then *first is pair<string, Elem> object, not Elem object.
This leads us to the thought that we need an adaptor which calls Elem::GetValue given pair<string, Elem> object. How about defining the adaptor as follows?
struct ElemGetValueAdaptor {
int operator()(const pair<string, Elem>& p) {
return p.second.GetValue();
}
};
You can call transform() algorithm with the above class as follows
transform(m.begin(), m.end(), vi.begin(), ElemGetValueAdaptor());
Up to now, the situation is manageable. Let’s assume now you need to Elem::Print(). Then what would you do? You may want to define another adaptor class for Elem::Print().
struct ElemPrintAdaptor {
void operator()(const pair<string, Elem>& p) {
p.second.Print();
}
};
And then, you call for_each() algorithm.
for_each(m.begin(), m.end(), vi.begin(), ElemPrintAdaptor());
Now you can easily guess that whenever you need to call a member function for each element of map container, you need to define an adaptor class and the pattern of the adaptor class is very similar to each other. If you have N member functions defined for a class, then you may need to define N adaptor classes when object of the class is stored in a map container.
Typically, if we encounter a sort of patterned code, we start to think how to remove them. The creative lazyness in your deep mind drives you to do this. right? I can easily guess you come up with templates
template <typename R>
struct ElemAdaptor {
// GetValue() and Print() are const member functions
typedef R (Elem::*MemFunType)() const;
ElemAdaptor(MemFunType mf) : m_mf(mf) {}
R operator()(const pair<string, Elem>& p) {
return (p.second.*m_mf)();
}
private:
MemFunType m_mf;
};
With this template define, you can call transform() and for_each() as follows
transform(m.begin(), m.end(), vi2.begin(), ElemAdaptor<int>(&Elem::GetValue));
for_each(m.begin(), m.end(), ElemAdaptor<void>(&Elem::Print));
But this template can’t cover Elem::SetValue(int) because it has an agument and is not an const member function. You can define generic member function adaptor which can deal with various member functions only after much much much efforts.
On top of that, what if ‘m’ is either the container of Elem*, the container of Elem& ? Additionaly const or volatile can be added to the object. I guarantee that it will be very very very difficult to define an adaptor template which can deal with great diversities.
What do you gonna do with this problem? To give up? or invent a template? Both are not recommended. boost::bind and boost’ placeholder are the ones which you can use, encountering this problem. boost::bind can deal with the diversities which I mentioned. With boost::bind(), you can write the code with the exact same functionalities as follows
// boost::bind
#include <boost/bind.hpp>
using namespace std;
using namespace boost;
……
transform(
m.begin(), m.end(), vi2.begin(),
bind(&Elem::GetValue, bind(&map<string, Elem>::value_type::second, _1))
);
for_each(
m.begin(), m.end(),
bind(&Elem::Print, bind(&map<string, Elem>::value_type::second, _1))
);
Let’s start with inner bind(), that is bind(&map<string, Elem>::value_type::second, _1) ‘_1’ is the placeholder and it makes code fragments a functor which accept an agument in place of the placeholder. boost supports up to 9 placeholders which is represented as _1, _2, _3, …, and _9. If we give a pointer to a member variable as the first argument of boost::bind() and object as the second argument(_1 in this example), then we can get a reference to the member variable. So the inner bind gives us a reference to the Elem object. Compared to ElemAdaptor::operator(p) implementation, this has same effect to p.second.
With this knowledge, we can understand that outer bind means bind(Elem_mem_func_ptr, Elem_obj). if we give a pointer to a member(regardless that it is either a pointer to a member variable or a member function), bind tries to interpret the second argument as an object(or a reference or a pointer to it) and creates a functor which calls the member function or accesses the member variable. The outer bind has the same effect to (Elem_obj.*Elem_mem_func_ptr)() or (Elem_obj->*Elem_mem_func_ptr)().
bind can be applied to a member function with arguments. For example, you can call Elem::SetValue(10) to each element of ‘m’ container as follows.
for_each(
m.begin(), m.end(),
bind(&Elem::SetValue, bind(&map<string, Elem>::value_type::second, _1), 10)
);
You should give SetValue()’s argument value as the third argument of bind().
Putting it altogether, if you want to apply STL algorithm to a map container, then you can use the following pattern.
#include <boost/bind.hpp>
using namespace boost;
bind(&ClassName::mem_func_name, bind(&map<keytype,
ClassName>::value_type::second, _1), arg1, arg2, …, arg9)
I hope this post make your C++ programming work easier.
Yesarang's Blog 