04 Jan, 2009, Keberus wrote in the 1st comment:
Votes: 0
Can anyone explain to me how to properly use iterators in C++ and give a few examples. I'd like to know how to add to, remove from, and loop through. Also, what's the difference between a list iterator and a vector iterator? If I had a class and wanted a "linked list" like how in C you use a first, last….how would I replace it and use the C++ iterator?

Thanks in advance,
KeB
04 Jan, 2009, Baiou wrote in the 2nd comment:
Votes: 0
I was never too sure what the difference was between vectors and lists, I just always chose to use lists… personal preference, but I've written a few basics below in code format. Just follow the comments and hopefully they'll be able to help.

// Create a list and list iterator. 
std::list<type> lst;
std::list<type>::iterator itr;

// To add to the front of a list, use the push_front method:
lst.push_front( typeVariable );

// To add to the end of a list, use the push_back method:
lst.push_back( typeVariable );

// To take from the beginning of a list, use the pop_front method:
lst.pop_front( typeVariable );

//To take from the end of a list, use the pop_back method:
lst.pop_back( typeVariable );

//To loop through a list, you must use an iterator.
//An iterator is is essentially a pointer to an object in the list.
//To loop through from the beginning of a list to end, use begin() and end():
for( itr = lst.begin(); itr != lst.end(); itr++ );

//To loop through from the end of a list to the beginning, use rbegin() and rend():
for( itr = lst.rbegin(); itr != lst.rend(); itr++ );

//You use an iterator just like a pointer.
itr->IteratorMethod();
// Assuming your iterator is of a class that has GetStats() as a method:
itr->GetStats();


There are a few more list methods that can be used to do different things such as 'clear', 'sort', 'splice', and 'remove'. I suggest just trying them all out to get the hang of using it.
05 Jan, 2009, Kline wrote in the 3rd comment:
Votes: 0
http://www.cplusplus.com/reference/stl/l...

I just recently took the plunge into lists and other STL stuff myself. That website has proven invaluable to me.
05 Jan, 2009, Caius wrote in the 4th comment:
Votes: 0
Keberus said:
I'd like to know how to add to, remove from[…]

The exact method for adding and removal depends on the type of underlying container. In the case of lists and vectors you'd do this:

std::list< Person* > personList; // define a list to hold pointers to Person objects
Person *pers = new Person;
personList.push_back( pers ); // append the pointer to the end of the list.
personList.remove( pers ); // delete from list (object not destructed, because it's only a pointer)
delete pers;


Keberus said:
[…] and loop through.

for( std::list< Person* >::iterator i = personList.begin(); // create an iterator 'i' and assign the first iterator in the list to it (begin)
i != personList.end(); // end() points beyond the last element, and not AT the last element!
++i ) // increment to the next iterator
{
Person *pers = *i; // dereference iterator 'i' which returns the pointer it encapsulates
pers->whatever();
}


Keberus said:
Also, what's the difference between a list iterator and a vector iterator?

Vectors use random access iterators, while lists use bidirectional iterators. Random access iterators can be added to, like i + 2, and supports the subscript operator []. Bidirectional iterators only supports the ++ and – operators. For most practical purposes the difference is that some algorithms only works on random access iterators (random_shuffle, for instance).

Keberus said:
If I had a class and wanted a "linked list" like how in C you use a first, last….how would I replace it and use the C++ iterator?

You don't need anything special in your class. All you need to do is to have the list/vector object handy, and insert the Person object (or pointer to) into it like in the above example.

Edited a small typo.
05 Jan, 2009, Caius wrote in the 5th comment:
Votes: 0
Baiou said:
// Assuming your iterator is of a class that has GetStats() as a method:
itr->GetStats();

You can't call member functions on the encapsulated pointer like that without dereferencing the iterator first: (*itr)->GetStats()
05 Jan, 2009, Caius wrote in the 6th comment:
Votes: 0
Btw, here are some simple examples of things you can do with STL:

#include <vector>
#include <list>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cctype>

// This is used with for_each below
void printChar( const char c )
{
std::cout << c;
}

// Ditto
void to_upper( char &c )
{
c = toupper( c );
}

int main()
{
// Create a string.
std::string myString( "This is my string." );

// Create a char vector, and copy the string's contents into it.
std::vector< char > myVec( myString.begin(), myString.end() );

// Print both.
std::cout << "String: " << myString << '\n'
<< "Vector: " << &myVec[0] << '\n';

reverse( myString.begin(), myString.end() );
reverse( myVec.begin(), myVec.end() );

std::cout << "String: " << myString << '\n'
<< "Vector: " << &myVec[0] << '\n';

// Use vector as replacement for char[] array with legacy C functions.
std::vector< char > charReplacement( 32 );
snprintf( &charReplacement[0], charReplacement.size(), "Fun: %d %s.",
3, "little piggies" );
std::cout << &charReplacement[0] << '\n';

// Call printChar on each element:
for_each( myString.begin(), myString.end(), printChar );
for_each( charReplacement.begin(), charReplacement.end(), printChar );

// Convert to uppercase:
for_each( charReplacement.begin(), charReplacement.end(), to_upper );
for_each( myString.begin(), myString.end(), to_upper );
std::cout << '\n' << &charReplacement[0] << '\n'
<< myString << '\n';
}


Output said:
String: This is my string.
Vector: This is my string.
String: .gnirts ym si sihT
Vector: .gnirts ym si sihT
Fun: 3 little piggies.
.gnirts ym si sihTFun: 3 little piggies.
FUN: 3 LITTLE PIGGIES.
.GNIRTS YM SI SIHT
05 Jan, 2009, quixadhal wrote in the 7th comment:
Votes: 0
Out of curiosity, as a C++ noob, is there any reason you couldn't make a list of actual objects, rather than just pointers to them?

I realize there are plenty of reasons why you wouldn't want to do so, usually, but would the compiler deal with it?
05 Jan, 2009, Baiou wrote in the 8th comment:
Votes: 0
yea you can make a list out of regular objects as is what I did with my example. Type isn't type*. Using pointers requires a dereferencing but if you use actual objects, then the iterator acts as it's pointer.
05 Jan, 2009, Caius wrote in the 9th comment:
Votes: 0
Baiou said:
yea you can make a list out of regular objects as is what I did with my example. Type isn't type*. Using pointers requires a dereferencing but if you use actual objects, then the iterator acts as it's pointer.

Didn't realize you were using objects rather than pointers in your example. Sorry about that.

quixadhal said:
I realize there are plenty of reasons why you wouldn't want to do so, usually, but would the compiler deal with it?

There are also plenty of reason why you would want to. It can help memory management a lot, since the object will be destructed when it's removed from the container.
05 Jan, 2009, Keberus wrote in the 10th comment:
Votes: 0
Thanks for the help guys.
05 Jan, 2009, Keberus wrote in the 11th comment:
Votes: 0
Cauis is there a reason you chose to pre increment your variable as opposed to Baiou who does a post increment in the loop? This seems like you would skip over the zeroth spot if you did a pre increment? Or does it not matter in these cases?

Thanks again,
KeB
05 Jan, 2009, Caius wrote in the 12th comment:
Votes: 0
It's just a matter of preference really. The variable isn't increased until after the loop body has executed, so it makes no difference.
05 Jan, 2009, Caius wrote in the 13th comment:
Votes: 0
Just to show what I mean:

for( int n = 0; n < 5; ++n )
{
std::cout << n << '\n';
}


Output said:
0
1
2
3
4
05 Jan, 2009, Keberus wrote in the 14th comment:
Votes: 0
Hmm, I always thought it would increase before running the loop if using the ++var instead of var++…thanks for clearning that up.
05 Jan, 2009, Keberus wrote in the 15th comment:
Votes: 0
Okay, a more specific example. for removing some combatant data for my arena code is this:

void arena_data::remove_combatant( CHAR_DATA * ch )
{
list < arena_combatant_data *>::iterator fighter;

if( !ch )
{
bug( "%s: NULL ch", __FUNCTION__ );
return;
}

for( fighter = arena->fighters.begin( ); fighter != arena->fighters.end( ); fighter++ )
{
arena_combatant_data *i = *fighter;
if( ch == i->combatant )
{
restore_attribs( ch );
arena->fighters.remove( i );
delete i;
i = NULL;
return;
}
}
return;
}


Here's the line referencing fighters from the arena class:
list < arena_combatant_data * > fighters;


Above was causing a seg fault. To get it to stop for the removal loops I had to do

void arena_data::remove_combatant( CHAR_DATA * ch )
{
list < arena_combatant_data *>::iterator fighter, fighter2;

if( !ch )
{
bug( "%s: NULL ch", __FUNCTION__ );
return;
}

for( fighter = arena->fighters.begin( ); fighter != arena->fighters.end( ); fighter = fighter2 )
{
fighter2 = fighter;
fighter2++;
arena_combatant_data *i = *fighter;
if( ch == i->combatant )
{
restore_attribs( ch );
arena->fighters.remove( i );
delete i;
i = NULL;
return;
}
}
return;
}


Is this still something that you should have to do in these cases?

Thanks,
KeB
05 Jan, 2009, ghasatta wrote in the 16th comment:
Votes: 0
For std::list, when removing an element, any iterators that point to that element are invalidated. So, if in your original code you continued to use the iterator, rather than returning, I can see how you would have problems. I don't see anything obviously wrong with your original block of code, however.

This is not really what you were asking about, but I think you could save yourself some effort by using a different STL container type. I would suggest you use std::map if each character has one arena_combatant_data. Here is a sample implementation if arena.fighters is defined as type 'std::map<CHAR_DATA *, arena_combatant_data *>'. It skirts your iterator issue a bit ;)

I would also recommend SGI's STL Programmer's Guide as a very thorough reference.


void arena_data::remove_combatant( CHAR_DATA * ch )
{
std::map<CHAR_DATA *, arena_combatant_data *>::iterator entry = arena->fighters.find(ch);

if(entry != arena->fighters.end()
{
restore_attribs( ch );
delete entry.second;
arena->fighters.erase(entry);
}
}
05 Jan, 2009, Keberus wrote in the 17th comment:
Votes: 0
ghasatta said:
For std::list, when removing an element, any iterators that point to that element are invalidated. So, if in your original code you continued to use the iterator, rather than returning, I can see how you would have problems. I don't see anything obviously wrong with your original block of code, however.


Okay, that block was being called from another block, that I also had to use a fighter2 with, so I am assuming since it was looping through, it must've been the real culprit.

Does the code:
void arena_data::remove_combatant( CHAR_DATA * ch )
{
std::map<CHAR_DATA *, arena_combatant_data *>::iterator entry = arena->fighters.find(ch);

if(entry != arena->fighters.end()
{
restore_attribs( ch );
delete entry.second;
arena->fighters.erase(entry);
}
}


Still loop through all of the entries? Just seems weird, becuase there's no for or while loop, thats why I'm asking.

Thanks again,
KeB
05 Jan, 2009, Sharmair wrote in the 18th comment:
Votes: 0
Keberus said:
Cauis is there a reason you chose to pre increment your variable as opposed to Baiou who does a post increment in the loop? This seems like you would skip over the zeroth spot if you did a pre increment? Or does it not matter in these cases?

Thanks again,
KeB

I think it has been cleared up that functionally in this case it does not make a difference, but there is
another reason someone might want to use the pre version when they can. With the built in types and
types that the pre and post versions are made to work like the built in types, it is more efficient to use
the pre version. The increment (in the case of ++) is done at the same time with both the pre and post
versions, at the time the operator is executed. The difference is what is returned (and used by any
chained evaluation), the pre simply increments and returns the new value, the post on the other hand
has to save the current value, then increment, then return the saved value.

With that said, with user types (like this) how the pre and post work might actually be the same (or
might have totally different meaning). Though, normally it is considered good design to have operators
have expected meaning.
05 Jan, 2009, ghasatta wrote in the 19th comment:
Votes: 0
The code is functionally equivalent to what you posted. The difference is that you don't have to spend the effort writing (and re-writing!) the same loop code. The lookup still happens, it's just part of the 'find' member function instead of code you hand write*.

Different STL containers (list, vector, map, etc…) all behave slightly differently and have different advantages / disadvantages. In the case of map, the obvious advantage you get is that you have a built in relationship between the key (your CHAR_DATA *) and the value (your arena_combatant_data *). There are then built-in functions that you can take advantage of for common operations (such as finding). However, you could still use the list type and be perfectly fine.

As a friend of mine once said, C++ is like C except there are 1 million ways to do the same thing. And it's plus one. ;)

* - FYI some containers such as map implement a binary search tree. This is different from a linked list in that the contents are sorted and the iterations required for lookups can be much reduced. However, the only time this difference is really a factor is when you have very large lists (hundreds of thousands of entries at least).
0.0/19