Is STL iterator singleton ?

[raan]

Is iterators singleton?

I am accessing a map through wrapper functions to it; that allow me to
access the contents of the map as

CUnit &unit = hash.getFirstunit();
while(hash.hasMoreunits())
{
unit = hash.getNextUnit();
}

Thats all about it. A call to getFirstUnit will initialize the
iterator. hasMoreUnits will move the iterator one unit forward and
hasNextUnit will access the next one and so on.

[just a side note, i was trying to implement a hastable with map and
set, so that each branch of the hash is a set protruding from a map
element.]

All fine unitl now. I have another function that is a straight forward
call.

hash.getUnitByName();

I initialise another set of iterators on the stack inside the function
(iterator objects scoped inside that function) which is local to the
function so that i don't disturb the original master iterators that i
keep intact in my class scope. Once I call this function, that will
throw the master iterator off the edge. What is happening here.

~raan

 

[Alf P. Steinbach]

* raan:

What is happening here.

Post the code.

See the FAQ for suggestions about how to post problem code.

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Is iterators singleton?

I am accessing a map through wrapper functions to it; that allow me to
access the contents of the map as

CUnit &unit = hash.getFirstunit();
while(hash.hasMoreunits())
{
unit = hash.getNextUnit();
}

Thats all about it. A call to getFirstUnit will initialize the
iterator. hasMoreUnits will move the iterator one unit forward and
hasNextUnit will access the next one and so on.

To answer the question in the subject, no.

What I really want to know is how you implemented that wrapper to get
that kind of functionality, using global variables? My advice, if you
insist on keeping the code like that, is to make hasMoreUnits() and
getNextUnit() take a CUnit as parameter so they know which iterator to
test for end / increment.

If the problem you are trying to solve is to iterate over your home-made
hashmap then perhaps you should instead you should try to create a STL-
compatible iterator (i.e. one that behaves like other iterators). I've
done it, so it's quite possible.

 

[tony_in_da_uk]

[just a side note, i was trying to implement a hastable with map and
set, so that each branch of the hash is a set protruding from a map
element.]

The point of hash tables is that their lookup is constant time (O(1))
- faster than binary maps which are O(ln n). Using C++/STL terms, a
set is actually a binary map where the keys are important and there is
no value associated with the node. So the idea of using a map and a
set to implement a hash table involves using two lower performance
mechanisms in an attempt to create a higher performance mechanism.

From a performance perspective: impossible. It's also impossible from

a functional perspective: consider what you're asking...

A hash table finds data associated with a particular key by generating
a numerical hash value from that key, using that value (probably
wrapped by the container size) to directly index to an entry related
to that value, then using the full key to see whether the desired data
exists at that spot. One reason it might not is because some other
key's hash value happened to yield the same index, and the other value
is here. The hash map implementation must then handle the collision
by searching elsewhere, or making the "entry" itself some kind of
associative container. That means that the original key must still be
used to find the desired value amongst the key/value pairs associated
with the hash value.

So, given your "map of sets", you presumably look up the hash value in
the map, then you have a set of values, but they're no longer
associated with a particular key and you can't work out which one you
want.

FWIW, it _would_ make sense to implement a hash table as a vector of
some associative container (e.g. (binary) map). Why vector? Because
it's fast to randomly index. And using a binary map as this secondary
resolution step is ok because you've presumably reduced the number of
elements you're searching through. If your vector has M elements, and
your hash map has N, then your binary map lookup will typically only
be - loosely speaking - O(max(ln (N/M),1)).

( Actually, it's generally faster to keep your vector much larger than
the number of entries in the hash map, and successively try a list of
offsets (e.g. 1, 3, 6, 13 whatever) from the position to which the
hash value resolved. But if you want to start learning about hash
tables, start with the simple std::map<> based approach above. )

Cheers,

Tony

 

[James Kanze]

To answer the question in the subject, no.

What I really want to know is how you implemented that wrapper
to get that kind of functionality, using global variables? My
advice, if you insist on keeping the code like that, is to
make hasMoreUnits() and getNextUnit() take a CUnit as
parameter so they know which iterator to test for end /
increment.

My advice is to not use that interface. It's probably the
poorest solution to the question of how to iterate over all of
the elements.

If the problem you are trying to solve is to iterate over your
home-made hashmap then perhaps you should instead you should
try to create a STL- compatible iterator (i.e. one that
behaves like other iterators). I've done it, so it's quite
possible.

Creating a classical iterator, such as described in the GoF, is
generally even easier, and it's easier to use. I try to provide
both interfaces to my iterators; I'll use the STL interface when
calling standard algorithms (or rather, the standard algorithms
will use the STL interface), and the GoF interface most of the
rest of the time (since it only requires a single iterator
object, instead of two).