Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #13488 > unrolled thread

Iterator in a template

Back to article view | Back to comp.lang.c++

Contents

  Iterator in a template Pierre Abbat <phma@phma.optus.nu> - 2012-01-19 04:49 +0000
    Re: Iterator in a template red floyd <no.spam.here@its.invalid> - 2012-01-18 22:36 -0800
      Re: Iterator in a template Pierre Abbat <phma@phma.optus.nu> - 2012-01-19 13:05 +0000
    Re: Iterator in a template "MikeWhy" <boat042-nospam@yahoo.com> - 2012-01-19 05:44 -0600
      Re: Iterator in a template SG <s.gesemann@gmail.com> - 2012-01-19 06:08 -0800

#13488 — Iterator in a template

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>::operator[](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?

[toc] | [next] | [standalone]

#13490

On 1/18/2012 8:49 PM, Pierre Abbat wrote:
> 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>::operator[](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

[toc] | [prev] | [next] | [standalone]

#13497

On Wed, 18 Jan 2012 22:36:37 -0800, red floyd wrote:

> 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

[toc] | [prev] | [next] | [standalone]

#13495

"Pierre Abbat" <phma@phma.optus.nu> wrote in message 
news:hvjku8-rs3.ln1@darner.ixazon.lan...
> 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>::operator[](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>.

[toc] | [prev] | [next] | [standalone]

#13498

On 19 Jan., 12:44, MikeWhy wrote:
>
> [...] 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::ptr_map or
std::map in combination with std::unique_ptr (if C++2011 is available)

Cheers!
SG

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web