Help with template: returning multiset<T>

[luislupe]

I'm trying to build my first template function, but it generates a compile error when lines 21 and 22 are not commented.

What I'm trying to do is to have a template function that can return multiset<int>, multiset<double> or multiset<string> depending on the attribute I want to extracto from the vector.
Each element of vector has several member names of Voice.

Please see:

http://codepad.org/WpLEvSez

Can I build such a template?

The broader problem is this:
I have a database where there are several tables, each with dozens of fields and I want to build a clustering algorithm.
The first step, the one I'm trying to accomplish is to create a multiset of each attribute so that I can build bins and count frequencies of elements for each bin, for chosen attributes.

I'd appreciate any ideas on this, so that I don't have to code many repetitive tasks.

[rubberman]

Multisets are the same as sets, except that they can have multiple instances associated with a single key. They are templates, as you know, but the signature of multiset is not multiset<T>, but multiset<Key_Type, Value_Type, Key_Allocator = Allocator<Key_Type> >. IE, you need at least 2 template arguments when declaring multisets, as in:

multiset<double, double> my_double_mset;
multiset<int, int> my_int_mset;

So, if you wanted a multiset that is keyed on the number of instances of a string, you could do this:

multiset<unsigned, string> counts_of_strings;

Kind of silly examples, but hopefully you get the point.

[Insensus]

What rubberman said is actually wrong.
In a multiset an element's key is itself so you need to specify only one type.

Now I'll try to explain to you why you get this error:
When you use a function that's defined from a template, your compiler will at compile-time create an actual function from your template definition for the required type.
Now because your instantiation happens with an int the multiset inside your function will be a multiset<int> and therefore multiset<int>::insert(const string&) will generate an error even though you will be preventing that statement from ever happening at run-time. Your compiler can't know that and therefore can't compile.

You COULD do this with templates, but then you'd need to create a new specialization for every different type of variable which is pretty much the same amount of work as just making three different functions.

[mike_2000_17]

>>Can I build such a template?

You cannot. The reason this is a problem (and the reason for the errors) is because your function template, when instantiated with int, has to compile, all of it has to compile, including the parts that will not be executed (i.e. parts which insert elements that are not of type T). The compiler tries to compile it but it can't.

There are a few options.

First, you can specialize the function template for each type. As so:

class Voice
{
  public:
    template <typename T>
    std::multiset<T> getAtribDim(const std::vector<Voice>& v, std::string attr);
    int air_time;				// 115
    double charged_amount;			// 864
    std::string id_cell;			// "cell a"
};

template <>
std::multiset<int> Voice::getAtribDim<int>(const std::vector<Voice>& v, std::string attr);
{
  std::multiset<int> satrib;		//multiset
  for (std::vector<Voice>::const_iterator ci = v.begin(); ci != v.end(); ++ci) {
    if (attr == "air_time") {
      satrib.insert(ci->air_time);		//int member name
    } else if(//... for any other int-type attributes..
  }
  return satrib;
}


template <>
std::multiset<std::string> Voice::getAtribDim<std::string>(const std::vector<Voice>& v, std::string attr);
{
  std::multiset<std::string> satrib;		//multiset
  for (std::vector<Voice>::const_iterator ci = v.begin(); ci != v.end(); ++ci) {
    if (attr == "id_cell") {
      satrib.insert(ci->id_cell);		//string member name
    } else if(//... for any other string-type attributes..
  }
  return satrib;
}

//similarly for double and whatever else you have.

When you "call" the function template, it will instantiate only the appropriate specialization, and won't have trouble compiling it because all your inserts are of consistent type.

The other solution, which I think is much better, is to use a pointer to data member instead of the string to identify which attribute to use. And doing so, you can deduce the return parameter from the passed parameter (type of the pointer to member). Here is an example:

class Voice
{
  public:
    template <typename T>
    std::multiset<T> getAtribDim(const std::vector<Voice>& v, T Voice::*attr)
    {
      std::multiset<T> satrib;		//multiset
      for (std::vector<Voice>::const_iterator ci = v.begin(); ci != v.end(); ++ci)
        satrib.insert((*ci).*attr);
      return satrib;
    }
    int air_time;				// 115
    double charged_amount;			// 864
    std::string id_cell;			// "cell a"
};

//and the calling code becomes:
//..
  //get air_time
  multiset<int> m = voice.getAtribDim(vvoice, &Voice::air_time); //notice, no need for <int>
//..

>>The broader problem

Consider, maybe, the Boost.Multi-Index library. This is especially dedicated to sorting a single array according to several different attributes and be able to iterate through them in different orders.

[luislupe]

>>Can I build such a template?
The other solution, which I think is much better, is to use a pointer to data member instead of the string to identify which attribute to use. And doing so, you can deduce the return parameter from the passed parameter (type of the pointer to member). Here is an example:

class Voice
{
  public:
    template <typename T>
    std::multiset<T> getAtribDim(const std::vector<Voice>& v, T Voice::*attr)
    {
      std::multiset<T> satrib;		//multiset
      for (std::vector<Voice>::const_iterator ci = v.begin(); ci != v.end(); ++ci)
        satrib.insert((*ci).*attr);
      return satrib;
    }
    int air_time;				// 115
    double charged_amount;			// 864
    std::string id_cell;			// "cell a"
};

//and the calling code becomes:
//..
  //get air_time
  multiset<int> m = voice.getAtribDim(vvoice, &Voice::air_time); //notice, no need for <int>
//..

Thank you very much for this suggestion. It works! I guess we just have to get around language type rules in a very smart way that a beginner like myself is not aware of.

No my battle will be to change

std::multiset<T> getAtribDim(const std::vector<Voice>& v, T Voice::*attr)

to something like this:

std::multiset<T> getAtribDim(const std::vector<Q>& v, T Q::*attr)

so that I can move getAtribDim to an ancestor class, common to the several similar classes I created to get the attributes from tables in the db.

[mike_2000_17]

>>I can move getAtribDim to an ancestor class

Don't. This is a very clear case in which you should be using a free function, not a class member function. It is more scalable that way (like all standard <algorithm> functions).

I suggest you just make it a free function:

template <typename ForwardIter, typename T>
std::multiset<T> getAttribSet(ForwardIter first, ForwardIter last, 
                              T (typename std::iterator_traits<ForwardIter>::value_type)::*attr) {
  std::multiset<T> result;
  std::copy(first, last, std::inserter(result,result.end()));
  return result;
};

[luislupe]

>>I can move getAtribDim to an ancestor class

Don't. This is a very clear case in which you should be using a free function, not a class member function. It is more scalable that way (like all standard <algorithm> functions).

I suggest you just make it a free function:

template <typename ForwardIter, typename T>
std::multiset<T> getAttribSet(ForwardIter first, ForwardIter last, 
                              T (typename std::iterator_traits<ForwardIter>::value_type)::*attr) {
  std::multiset<T> result;
  std::copy(first, last, std::inserter(result,result.end()));
  return result;
};

I thank you for this suggestion. I understand the idea behind it.
1. There are two template parameters (ForwardIter and T)
2. `T` is supposed to mean `int` or `string` and is used to aknowledge the compiler about the type of the attribute and of the multiset.
3. Elements from `first` to `last` will be inserted into the multiset `result`.

But line nr. 3 is a little complex for me. Would you mind explaining it with some detail?
I'll try from right to left:
a. Like your previous suggestion `*attr` dereferences to the value of attribute to be called as a reference.
b. `typename std::iterator_traits<ForwardIter>::value_type`?? And the `::` before `*attr`? Why `value_type::*attr`?
c. The value of all the expression is of type `T`.

Another thing I don't understand: Elements from `vvoice`, from beginning to end will be inserted in multiset `result`. But how does it turn out that elements inserted are the ones dereferenced by `*attr` in

std::copy(first, last, std::inserter(result,result.end()));

?

After including `algorithm` or `iterator` (which is correct?) g++ can't compile the template.
`error: expected ',' or '...' before '::' token`

I should be calling the function as:

vector<Voice> vvoice;
multiset<int> m = getAttribSet(vvoice.begin(), vvoice.end(), &Voice::air_time;

Is this correct?

[rubberman]

Multisets are the same as sets, except that they can have multiple instances associated with a single key. They are templates, as you know, but the signature of multiset is not multiset<T>, but multiset<Key_Type, Value_Type, Key_Allocator = Allocator<Key_Type> >. IE, you need at least 2 template arguments when declaring multisets, as in:

multiset<double, double> my_double_mset;
multiset<int, int> my_int_mset;

So, if you wanted a multiset that is keyed on the number of instances of a string, you could do this:

multiset<unsigned, string> counts_of_strings;

Kind of silly examples, but hopefully you get the point.

Doh! I think that was a "senior moment" - thinking of multimap<KT,VT> instead of multiset<T>... My bad - and sorry for the confusion it may have caused.

[mike_2000_17]

For Line 3 (the last param of the function), here is a detailed explanation:

First, consider the following simple statement:

Foo Bar::*attr;

This statement declares a pointer-to-data-member. In the above, it declares a pointer with name 'attr', which points to a data member of 'Bar' which is of type 'Foo'. Here are a few declarations of the same kind of syntax that you may be more familiar with:

//A function pointer:
int (*fptr)(int, double); //fptr points to a function taking (int,double) -> int.
//A function pointer type:
typedef int (*fptr_t)(int, double); //fptr_t is the type of functions pointers (int,double) -> int.
//A member-function pointer (or pointer-to-member-function):
//mfptr points to a function taking (int,double) -> int, and which is a non-static member of class MyClass:
int (MyClass::*mfptr)(int, double);
//similarly, as a type:
typedef int (MyClass::*mfptr_t)(int,double); //type of mfptr (above).

//then, a pointer-to-data-member:
int MyClass::*mdptr; //mdptr is a pointer to a member of MyClass, with type int.
//similarly for the type:
typedef int MyClass::*mdptr_t; //type of mdptr (above).

So, by substitution, in your example, attr is a pointer-to-data-member to a member of class std::iterator_traits<ForwardIter>::value_type , which is of type T.

Now, for the std::iterator_traits<ForwardIter>::value_type . I guess you understand that this will be the class that your iterators will dereference to (i.e. your Voice class). By now, you should also understand its place and function in the declaration of the pointer-to-data-member (see above). So, all that remains is the std::iterator_traits business. This is just the standard way, in C++, to extract information about the iterator. Traits are a very well known and used technique in generic programming. Normally, all STL iterators have nested type definitions to allow you to extract the types related to it, like value_type (what the iterator "points to"), reference_type (what they dereference to), pointer_type (what kind of pointer type they would correspond to), etc. The purpose of these type definitions is to allow you to do the kind-of things like in that code I posted. The problem is, some things can act as iterators without having those type definitions, like a normal pointer. Traits are used to allow you to specify these type definition externally such that normal pointers can be used as if they were STL iterators. And that's the point of that little weird piece of syntax (e.g. for STL iterators, this becomes equivalent to ForwardIter::value_type , but it will also work for pointers, which obviously don't have nested type definitions).

About the typename , I'm sorry, I thought that a typename was required there, but apparently not. BTW, the typename keyword is used to explicitly tell the compiler that a nested identifier of a class template is a type identifier (i.e. typename), when the class template is used with a template argument of the enclosing template. I know, that's a mouth-full, but it just means that when having types of templates of template arguments, you need to disambiguate for the compiler, because it will have trouble doing so on its own. For obvious reasons, I thought it was needed here, but apparently not (the use of typename is a bit weird, I often have to take them out or put some in to make things work). Sorry.

About this line:

std::copy(first, last, std::inserter(result,result.end()));

I'm sorry. I wrote the example too fast and forgot about extracting the attribute. You need to replace it with:

for(;first != last; ++first)
    result.insert((*first).*attr);

Ok, so, as redemption, here is a fully working program:

#include <iostream>
#include <string>
#include <set>
#include <vector>

#include <algorithm>

struct Person {
  int ID;
  std::string name;
  Person(int aID, const std::string& aName) : ID(aID), name(aName) { };
};


template <typename ForwardIter, typename T>
std::multiset<T> getAttribSet(ForwardIter first, ForwardIter last, 
                              T std::iterator_traits<ForwardIter>::value_type::*attr) {
  std::multiset<T> result;
  for(;first != last; ++first)
    result.insert((*first).*attr);
  return result;
};


int main() {
  std::vector<Person> v;
  v.push_back(Person(4,"Bob"));
  v.push_back(Person(3,"Joe"));
  v.push_back(Person(7,"Bill"));
  v.push_back(Person(0,"Frank"));
  v.push_back(Person(8,"Tom"));

  std::multiset<int> s_id = getAttribSet(v.begin(), v.end(), &Person::ID);
  for(std::multiset<int>::iterator it = s_id.begin(); it != s_id.end(); ++it)
    std::cout << *it << std::endl;
  std::cout << std::endl;

  std::multiset<std::string> s_name = getAttribSet(v.begin(), v.end(), &Person::name);
  for(std::multiset<std::string>::iterator it = s_name.begin(); it != s_name.end(); ++it)
    std::cout << *it << std::endl;
  std::cout << std::endl;
  
  return 0;
};