Iterator in a template

[Pierre Abbat]

I've used map iterators before; this is my first time making a template.
hvec (hexagonal vector) is an integral (in the mathematical sense) type
representing a point in a hexagonal lattice. A harray is an array
subscripted by an hvec. Currently I use only bytes as the elements, but I
will need to store larger things in harrays, so I made it a template. I
wrote this code to clear all elements in the harray:

template <typename T> class harray
{map<hvec,T *> index;
public:
T& operator[](hvec i);
void clear();
};

template <typename T> T& harray<T>:perator[](hvec i)
{hvec q,r;
q=i/PAGEMOD;
r=i%PAGEMOD;
if (!index[q])
index[q]=(T*)calloc(PAGESIZE,sizeof(T));
return index[q][r.pageinx()];
}

template <typename T> void harray<T>::clear()
{map<hvec,T *>::iterator i; // line 78
for (i=index.start();i!=index.end();i++)
{free(i->second);
i->second=NULL;
}
}

When I try to compile it, I get this error:

In file included from /home/phma/hexcode/hexcode.cpp:5:
/home/phma/hexcode/hvec.h: In member function 'void harray<T>::clear()':
/home/phma/hexcode/hvec.h:78: error: expected ';' before 'i'
/home/phma/hexcode/hvec.h:79: error: 'i' was not declared in this scope

How can I fix it?

 

[red floyd]

I've used map iterators before; this is my first time making a template.
hvec (hexagonal vector) is an integral (in the mathematical sense) type
representing a point in a hexagonal lattice. A harray is an array
subscripted by an hvec. Currently I use only bytes as the elements, but I
will need to store larger things in harrays, so I made it a template. I
wrote this code to clear all elements in the harray:

template<typename T> class harray
{map<hvec,T *> index;
public:
T& operator[](hvec i);
void clear();
};

template<typename T> T& harray<T>:perator[](hvec i)
{hvec q,r;
q=i/PAGEMOD;
r=i%PAGEMOD;
if (!index[q])
index[q]=(T*)calloc(PAGESIZE,sizeof(T));
return index[q][r.pageinx()];
}

template<typename T> void harray<T>::clear()
{map<hvec,T *>::iterator i; // line 78
for (i=index.start();i!=index.end();i++)
{free(i->second);
i->second=NULL;
}
}

When I try to compile it, I get this error:

In file included from /home/phma/hexcode/hexcode.cpp:5:
/home/phma/hexcode/hvec.h: In member function 'void harray<T>::clear()':
/home/phma/hexcode/hvec.h:78: error: expected ';' before 'i'
/home/phma/hexcode/hvec.h:79: error: 'i' was not declared in this scope

How can I fix it?

hmap<>::iterator is a dependent type. use
"typename map<hvec, T*>::iterator"

I believe this is in the FAQ

 

[MikeWhy]

I've used map iterators before; this is my first time making a template.
hvec (hexagonal vector) is an integral (in the mathematical sense) type
representing a point in a hexagonal lattice. A harray is an array
subscripted by an hvec. Currently I use only bytes as the elements, but I
will need to store larger things in harrays, so I made it a template. I
wrote this code to clear all elements in the harray:

template <typename T> class harray
{map<hvec,T *> index;
public:
T& operator[](hvec i);
void clear();
};

template <typename T> T& harray<T>:perator[](hvec i)
{hvec q,r;
q=i/PAGEMOD;
r=i%PAGEMOD;
if (!index[q])
index[q]=(T*)calloc(PAGESIZE,sizeof(T));
return index[q][r.pageinx()];
}

template <typename T> void harray<T>::clear()
{map<hvec,T *>::iterator i; // line 78
for (i=index.start();i!=index.end();i++)
{free(i->second);
i->second=NULL;
}
}

Red seems to have fixed your immediate problem. Additional comments:

Don't put using namespace std at global scope.

Use new/delete in preference to calloc/free.

Store std::auto_ptr<T> in your map rather than T* to allows trivial cleanup.
In particular, std::map::clear() will do the same as your harray<>::clear(),
with the addition that it also clears the now empty keys.

You probably also will want to wrap your T[PAGESIZE] in at least a typedef
if not a class.
typedef T datapage[PAGESIZE]; // NB: auto_ptr doesn't work with
arrays.

Given that auto_ptr<> doesn't work with arrays (it calls delete rather than
delete[]), strongly consider defining a class to contain your data pages,
even something so simple as:

temmplate <typename T>
class HexArray
{
private:
typedef T datapage[PAGESIZE];
struct TPage
{
datapage page;
T& operator[](const hvec & r)
{ // ASSERT: r.pageinx < PAGESIZE.
return page[r.pageinx()];
}
const T& operator[](const hvec & r) const
{ return page[r.pageinx()];
}
};
typedef std::map<hvec, TPage> HexIndex;
HexIndex index;
...
};


The compiler likely won't optimize away the multiple calls to index[q]. Each
such call walks the search tree to find q. Search for q once, and store the
reference:
hpage & qpage = index[q];
Actually, this is completely moot if you defined TPage and index as I
suggested above. operator[] becomes very trivial:
{
...
return index[q][r];
}

If you don't wrap your data page in the map, the harray destructor needs to
call clear() to ensure the allocated pages are freed. By wrapping the array
and not making a separate allocation, cleanup is trivial.

In general, combine declaration with initialization, especially since
constructors are involved.
const hvec q(i / PAGEMOD);
const hvec r(i % PAGEMOD);


index.begin()? rather than index.start()?

iterators have a strong preference for pre-increment (++i). Post-increment
(i++) involves a temporary and is more expensive.

It should be moot now, but std::for_each() is often more efficient and thus
preferred to manually iterating a container with a for loop.

I'm sure I missed a few things. Maybe the other guys will chime in. (They'll
likely ding me in turn for nesting TPage in harray. By lifting TPage out of
harray -- encapsulating T, PAGESIZE, and PAGEMOD -- harray becomes a simple
typedef for std::map<hvec, TPage>.

 

[Pierre Abbat]

hmap<>::iterator is a dependent type. use "typename map<hvec,
T*>::iterator"

I believe this is in the FAQ

Thanks, it worked. I did see "dependent type" in the FAQ but, as I said,
this is my first time making a template, and I don't understand
everything.

I'll look at auto_ptr.

Pierre

 

[SG]

[...] Additional comments:

Don't put using namespace std at global scope.

Use new/delete in preference to calloc/free.

Store std::auto_ptr<T> in your map rather than T* to allows trivial cleanup.

Never ever try to use something like std::auto_ptr in a standard
container. Hardly any container nor algorithm is able to correctly
cope with element types that have a destructive constructor and
destructor assignment operator.

Possible alternatives:
boost:tr_map or
std::map in combination with std::unique_ptr (if C++2011 is available)

Cheers!
SG