C++

Forum

 
templates and mulit dimensional vectors

philrosenberg (6)
Hi

I'm trying to write a function or set of functions that will find the minimum value of a multi dimensional std::vector with any number of dimensions.
I'd like to have the function templated so that it works with any type or class that can use the < operator.

The code I'm trying is
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
template<classs U,class T>
U min(const std::vector<T> &v)
{
   if(v.size()==0) return std::numeric_limits<U>::quiet_NaN;
   U result=min<U>(v[0])
   for(size_t i=1; i<v.size(); ++i)
   {
      U newmin=min<U>(v[i]);
      result=newmin<result?newmin:result;
   }
   return result;
}

template<class T>
T min(const std::vector<T> &v)
{
   if(v.size()==0) return std::numeric_limits<T>::quiet_NaN;
   T result=min<T>(v[0])
   for(size_t i=1; i<v.size(); ++i)
   {
      result=v[i]<result?v[i]:result;
   }
   return result;
}


I thought the second declaration of the function would be a specialization of the first, but when I try to use this code (MSVC++2008) as follows
1
2
3
 
vector < vector <double> > myvect
//some code to fill myvect with numbers
double mymin=min<double>myvect;

I get a compiler error saying there is an ambiguous call to overloaded function.

Does anyone know how I can acheive my aims here?

Cheers
Phil
helios (17560)
There's one thing I don't get: is there any case where the minimum of a vector of T would be of a type other than T?
hamsterman (4538)
You have functions U min(std::vector<T>&) and T min(std::vector<T>&). How do you expect the compiler to tell which one to use?
To be honest, I don't know how to do this. I can't think of a good way to tell whether T is a number or a vector (bad ways include restricting numeric (comparable) types to the built in ones or even using typeid.name() and searching for "std::vector" in it). Though even then C++ should have problems understanding what U was.

@helios
What is there not to get? If vector<int>, he wants to find the smallest int in it. If vector<vector<...<int>...> he wants to map min on each element and build a vector<int> form the results (and search it, of course).
Last edited on
helios (17560)
And for 3 dimensions? And 4?

If I really wanted to do this, I'd do it like this:
1
2
3
4
5
6
7
8
9
10
 
template <typename T>
T min(const std::vector<T> &);

template <typename R,typename T>
R min2(const std::vector<T> &); //inside it calls min()

template <typename R,typename T1,typename T2>
R min3(const std::vector<T2> &); //inside it calls min2()

//ad nauseam
I think it's totally retarded, though; starting from using nested vectors.
Galik (2254)
That's kind of an interesting problem. I have a kind of solution but I am not sure if its exactly what you are looking for. Also it's not heavily tested but it seems to work:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
#include <vector>
#include <iostream>

template<typename T>
T vmax(const std::vector<T>& v)
{
	T t = T();
	for(size_t i = 0; i < v.size(); ++i)
	{
		if(v[i] > t) t = v[i];
	}
	return t;
}

template<typename T>
T vmin(const T& v)
{
	return v;
}

template<typename T>
T vmin(const std::vector<T>& v)
{
	T t = vmax(v);
	for(size_t i = 0; i < v.size(); ++i)
	{
		if(vmin(v[i]) < vmin(t)) t = v[i];
	}
	return t;
}

int main()
{
	std::vector<int> v;

	v.push_back(3);
	v.push_back(9);
	v.push_back(7);

	std::cout << vmin(v) << '\n';

	std::vector<std::vector<int> > vv;

	v.clear();
	v.push_back(3);
	v.push_back(9);
	v.push_back(7);

	vv.push_back(v);

	v.clear();
	v.push_back(12);
	v.push_back(1);
	v.push_back(7);

	vv.push_back(v);

	v.clear();
	v.push_back(2);
	v.push_back(5);
	v.push_back(3);

	vv.push_back(v);

	std::cout << vmin(vmin(vv)) << '\n';

	std::vector<std::vector<std::vector<int> > > vvv;

	vv.clear();
	v.clear();
	v.push_back(3);
	v.push_back(9);
	v.push_back(7);

	vv.push_back(v);

	v.clear();
	v.push_back(12);
	v.push_back(10);
	v.push_back(7);

	vv.push_back(v);

	v.clear();
	v.push_back(2);
	v.push_back(5);
	v.push_back(3);

	vv.push_back(v);

	vvv.push_back(vv);

	vv.clear();
	v.clear();
	v.push_back(5);
	v.push_back(6);
	v.push_back(9);

	vv.push_back(v);

	v.clear();
	v.push_back(8);
	v.push_back(7);
	v.push_back(3);

	vv.push_back(v);

	v.clear();
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);

	vv.push_back(v);

	vvv.push_back(vv);

	std::cout << vmin(vmin(vmin(vvv))) << '\n';
}
 
3
1
2


Requires that the most enclosed type has a default constructor, operator<() and operator>() defined.
hamsterman (4538)
While I agree that this isn't needed, I feel like this should be possible to do in a better way..
Here this is done for int:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#include <iostream>
#include <vector>

int min (int i){ return i; }

template <typename T>
int min (std::vector<T>& v) {
   int res = min(v[0]);
   for (int i = 1; i < v.size(); i++)
      if (min(v[i]) < res) res = min(v[i]);
   return res;
}

int main(){
   std::vector< std::vector< int > > v;
   int a[] = {10, 20, 30};
   v.push_back( std::vector<int>( a, a+3 ) );
   int b[] = {6, 5, 7, 2};
   v.push_back( std::vector<int>( b, b+4 ) );
   int c[] = {5, 50, 10};
   v.push_back( std::vector<int>( c, c+3 ) );

   std::cout << min( v );
   std::cin.get();
}

If something so simple for int can't be done for T, you could say that there is a problem.

edit:
@Galik, I did not expect that to work. Why would C++ match the second function before the first? Does it have a rule to start with the least general ones?
Also, your use of max and push_backs is slightly silly.
Last edited on
helios (17560)
Why would C++ match the second function before the first? Does it have a rule to start with the least general ones?
Isn't it a partial specialization?
Last edited on
hamsterman (4538)
Oh right..
philrosenberg (6)
Okay I think I've cracked it, or at least come close.
I was resigned to using the method that I already knew and that hamsterman suggested and to simply write a specialization for every built in type, but then had a closer look at Galik's code and had a read around. I think my initial try was a partial specialisation (or maybe not a specialisation at all), because both were functions of a std::vector<T>. A bit of reading (there's not a lot of resources about this on the web) indicated partial specialisations can only be performed on class templates not function templates. Galik's code is a full specialisation because the type used in the second function (vector<T>) is more specialised that the first (T).

Whith a bit of fiddling I came up with this

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include<vector>
template<class T>
inline T vmin(const T &v)
{
   return v;
}

template<class U, class T>
U vmin(const std::vector<T>& v)
{
   U result=vmin<U>(v[0]);
   for(size_t i=1; i<v.size(); ++i)
   {
      U newmin=vmin<U>(v[i]);
      if(newmin < result) result=newmin;
   }
   return result;
}

int main()
{
   std::vector< std::vector <int> > myvector;

   //some code to allocat vector

  //get the smallest int in the vector
   int smallint=vmin<int>(myvector);

   //this method also allows me to get arrays
   //get a vector containing the smallest ints in each subvector
   std::vector<int> somesmallints=min< std::vector<int> >vmin(myvector);
}


Another method which I found worked was to pass a dummy parameter to the vmin functions above use this to define the output type
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
//just a code snippet
template<class T, class U>
U vmin(const T &v, const U &dummy)
{
   return v;
}
template<class T, class U>
U vmin(const std::vector<T>& v, const U &dummy)
{
   //definition the same as above
}

int main()
{
   std::vector< std::vector <int> > myvector;

   //some code to allocat vector

  //get the smallest int in the vector
   int dummy;
   int smallint=vmin(myvector,dummy);
}


I don't think I can see any better ways than this, but am always open to suggestions. Thanks Hamsterman and Galik for your extremely useful input.

And a special mention to this comment
I think it's totally retarded, though; starting from using nested vectors.

I always think it's nice that they let children on these forums but sometimes I think their parents should teach them some manners first.
helios (17560)
Your own maturity shows through in that comment.
philrosenberg (6)
I think you just need to choose your words a bit more carefully and be less confrontational with these things Helios. If someone used those words with me in person then I'd think them rude and I apply the same standards online too. Perhaps next time you could ask the questioner why they want to do what they are doing and/or suggest how they can do it better. If you are constructive like that then you will soon build a reputation.

As for the specifics here, as far as I'm concerned std::vector is just another word for array in C++ so why not nest them. As far as why try to create this function, I'd have thought that it was clear why I'd like one function call that does the job of a significant number of lines of code (especially when it gets to 4d+). If however you have a preferred method of dealling with multi-d arrays I'd be glad to hear it. I certainly don't know everything so your way might be better than mine.

All the best

Phil
helios (17560)
If someone used those words with me in person then I'd think them rude
Well, that's a problem with your sensibilities. I was merely expressing my opinion about the direction the code was headed. I'm not responsible if you take it as a personal attack.

std::vector is just another word for array in C++ so why not nest them
Because it's inefficient in both time and space, and because even simple things like getting the minimum element in an n-dimensional matrix grow in complexity with n.
I wrote a simplistic 10-cubic matrix class as a benchmark of memory access patterns (http://www.cplusplus.com/forum/general/50371/ [arithmetic_10cubic_matrix]), which shows how this kind of things should be done and which can be easily extended to n dimensions and non-cubic matrices.
In a class structured like this, getting the minimum is trivial. You simply iterate over a linear array.
philrosenberg (6)
There is nothing wrong with my sensibilities, I expect people to be polite - there is nothing wrong with that

Thanks for the link to the post - an interesting quick read. The obvious problem with generating my own type of vector is that I have to rewrite all the usefull code that already exists in the std::vector. The intention is not to make my vector supremely fast but to make it easier to use. I think often it's the case that people spend more time optimising their code for speed than they will ever save waiting for it to run - but again this is like I said sometimes it's an interesting problem so people like yourself and others want to spend time on it. However just because my aims are different to yours does not make them retarded - nor does it make your aims any less deserving of your time.
You are of course correct that many of these things become easier when you generate a multi-d array in contiguous memory and things can probably be performed faster. There are of course disadvantages - it becomes much harder to resize subdimensions when using contiguos blocks because even if you are appending to the end of a dimension you have to move almost every item in your array. In this sense a std::vector would be a lot faster. Of course there are other multi-d array implimentations that already use contiguous memoty and do a lot of this stuff. Boost probably has one and so does ALGLIB and GSL. ALGLIB includes BLAS (and the other too might also) for added computational speed when copying arrays and performing calculations but because so many people including myself use std::vector for their arrays I wanted to generate some code to make the maths I do with these vectors easier and is compatible with stuff that's already written. I don't have the time or the energy to reinvent the wheel and I don't want users of my code to have to convert all their data into my special array type.

Anyway thanks for the discussion. I've learnt some stuff and I hope you have too

Cheery-o

Phil
helios (17560)
There are of course disadvantages - it becomes much harder to resize subdimensions when using contiguos blocks because even if you are appending to the end of a dimension you have to move almost every item in your array.
And you think this is not the case with a vector? A vector will only work better if the dimension you're extending has space left in its capacity. Otherwise it will end up making lots and lots of copy constructor calls. Even vectors of pointers will be nicer in is this case.
Topic archived. No new replies allowed.