How do I define the "<" operator for list iterators?

blueeyedlion (73)
I'm trying to make a map of list iterators and I have discovered that that requires the < operator defined. I intend to have it compare the address of the contents of the iterator, and I have a pretty good idea of what that code will actually look like, but I don't know the syntax required to link the function to the list iterator class or how to use a template to make it work with different kinds of lists.
shacktar (1187)
This page gives examples on how to instantiate a map with a custom comparator:
http://www.cplusplus.com/reference/stl/map/map/

If I understand correctly, yours will look something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <list>
#include <map>

using namespace std;

template <class T>
class listIteratorComp
{
    bool operator() (const list<T>::iterator& left, const list<T>::iterator& right)
    {
        //comparison code
    }
};

int main()
{
    map< list<int>::iterator, char, listIteratorComp<int> > myMapExample;
    return 0;
}
Last edited on
JLBorges (13770)
> I'm trying to make a map of list iterators

Why do you want a map where list iterators are keys? What is the data that the key maps to? Why can't that data be stored in the list itself as part of the value_type?
shacktar (1187)
Another thing with iterators is they can be invalidated. If the list(s) invalidate its/their iterators, then your map would be invalid as well.
blueeyedlion (73)
This code is why I need it defined
If anyone has a better way to do this, please tell me (my way seems very complicated)

delclarations:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
// Contains all of the dynamic objects
    // For gravity, collisions
    std::list<SpaceShip> shipList;
    std::list<Asteroid> asteroidList;

    // The lists for all possible collision pairs
    std::list<std::pair<std::list<SpaceShip>::iterator, std::list<SpaceShip>::iterator> > shipShipCollisions;
    std::list<std::pair<std::list<SpaceShip>::iterator, std::list<Asteroid>::iterator> > shipAsteroidCollisions;
    std::list<std::pair<std::list<Asteroid>::iterator, std::list<Asteroid>::iterator> > asteroidAsteroidCollisions;

    // The time tracking maps for each list (when applicable)
    std::map<std::pair<std::list<SpaceShip>::iterator, std::list<Asteroid>::iterator>, double> shipAsteroidCollisionTimers;
    std::map<std::pair<std::list<Asteroid>::iterator, std::list<Asteroid>::iterator>, double> asteroidAsteroidCollisionTimers;


function:

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
 
void World::applyCollisions ()
{
    // First clear the collision lists
    shipShipCollisions.clear ();
    shipAsteroidCollisions.clear ();
    asteroidAsteroidCollisions.clear ();

    // For every possible combination, if overlapping, add the pair to the appropriate collision list

    // For every space ship on the shipList
    for (auto currentObject = shipList.begin ();
	 currentObject != shipList.end ();
	 ++currentObject)
    {
	// For every object after the current object on the ship list
	for (auto otherObject = std::next (currentObject);
	     otherObject != shipList.end ();
	     ++ otherObject)
	{
	    if (currentObject->isOverlappingWith (*otherObject))
	    {
		shipShipCollisions.push_back (make_pair (currentObject, otherObject));
	    }
	}

	// For every object on the asteroidList
	for (auto otherObject = asteroidList.begin ();
	     otherObject != asteroidList.end ();
	     ++otherObject)
	{
	    if (currentObject->isOverlappingWith (*otherObject))
	    {
		shipAsteroidCollisions.push_back (make_pair (currentObject, otherObject));
	    }
	}
    }

    // For every object on the asteroid list
    for (auto currentObject = asteroidList.begin ();
	 currentObject != asteroidList.end ();
	 ++currentObject)
    {
	// For every object after the currrent object on the asteroid list
	for (auto otherObject = std::next (currentObject);
	     otherObject != asteroidList.end ();
	     ++otherObject)
	{
	    if (currentObject->isOverlappingWith (*otherObject))
	    {
		asteroidAsteroidCollisions.push_back (make_pair (currentObject, otherObject));
	    }
	}
    }

    // Now apply collision acceleration and damage to every pair on the collision lists, breaking asteroids as required

    for (auto collision = shipShipCollisions.begin ();
	 collision != shipShipCollisions.end ();
	 ++collision)
    {
	collision->first->collideWith (*collision->second);
    }

    for (auto collision = shipAsteroidCollisions.begin ();
	 collision != shipAsteroidCollisions.end ();
	 ++collision)
    {
	collision->first->collideWith (*collision->second);

	// Break the asteroid if it's health is 0 and take its collision off the list
	if (collision->second->getHealth () == 0)
	{
	    breakAsteroid (collision->second);

	    shipAsteroidCollisions.erase (collision);
	}
    }

    for (auto collision = asteroidAsteroidCollisions.begin ();
	 collision != asteroidAsteroidCollisions.end ();
	 ++collision)
    {
	collision->first->collideWith (*collision->second);

	// if either asteroid breaks, the collision must be removed from the list
	if (collision->first->getHealth () == 0 || collision->second->getHealth () == 0)
	{
	    // break asteroids as required
	    if (collision->first->getHealth () == 0)
	    {
		breakAsteroid (collision->first);
	    }

	    if (collision->second->getHealth () == 0)
	    {
		breakAsteroid (collision->second);
	    }

	    asteroidAsteroidCollisions.erase (collision);
	}
    }

    // update the collision timer maps
    
    // make temporary timer maps to transfer times for existing collisions to, delete all the old collision times, then transfer back to the main map

    // create temporary timer maps with the same types as the main ones
    // use auto, copy, and delete to save characters typed
     auto tempShipAsteroidCollisionTimers = shipAsteroidCollisionTimers;
     tempShipAsteroidCollisionTimers.clear ();

    auto tempAsteroidAsteroidCollisionTimers = asteroidAsteroidCollisionTimers;
    tempAsteroidAsteroidCollisionTimers.clear ();
    
    // update times for existing collisions and put them in the temp map
    for (auto collision = shipAsteroidCollisions.begin ();
	 collision != shipAsteroidCollisions.end ();
	 ++collision)
    {
	// if there is already a timer for this collision, transfer it to the temp map and add the time since last update
	if (shipAsteroidCollisionTimers.count (*collision))
	{
	    tempShipAsteroidCollisionTimers [*collision] = shipAsteroidCollisionTimers [*collision] + events.timeSinceLastUpdate;
	}
	// if not, add it to the temp map with a time of 0
	else
	{
	    tempShipAsteroidCollisionTimers [*collision] = 0;
	}
    }

    // Same as above loop
    for (auto collision = asteroidAsteroidCollisions.begin ();
	 collision != asteroidAsteroidCollisions.end ();
	 ++collision)
    {
	if (asteroidAsteroidCollisionTimers.count (*collision))
	{
	    tempAsteroidAsteroidCollisionTimers [*collision] = asteroidAsteroidCollisionTimers [*collision] + events.timeSinceLastUpdate;
	}
	else
	{
	    tempAsteroidAsteroidCollisionTimers [*collision] = 0;
	}
    }

    // Now overwrite the main maps with the temp maps
    shipAsteroidCollisionTimers = tempShipAsteroidCollisionTimers;

    asteroidAsteroidCollisionTimers = tempAsteroidAsteroidCollisionTimers;

    // Now go through all existing collisions and act on any times that meet a threshhold
    for (auto collision = shipAsteroidCollisions.begin ();
	 collision != shipAsteroidCollisions.end ();
	 ++collision)
    {
	if (shipAsteroidCollisionTimers [*collision] >= AMMO_COLLECTION_TIME && collision->second->getRadius () < SMALLEST_BREAKABLE_ASTEROID)
	{
	    // put a call to the collect ammo function here when it is made
	}
    }

    for (auto collision = asteroidAsteroidCollisions.begin ();
	 collision != asteroidAsteroidCollisions.end ();
	 ++collision)
    {
	if (asteroidAsteroidCollisionTimers [*collision] >= TIME_FOR_ASTEROIDS_TO_BEGIN_MERGING)
	{
	    mergeAsteroids (collision->first, collision->second);
	}
    }

    return;
}
Last edited on
JLBorges (13770)
I would give each object I need to keep track of a unique id - say an int. For example,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
struct object_with_id
{
    const int id ;
    inline object_with_id() : id(++counter) {}
    private: static int counter ;

};

int object_with_id::counter = 0 ; // somewhere in the implementation file

struct SpaceShip : object_with_id
{
    // ....
    bool isOverlappingWith( const SpaceShip& that ) const ;
    // etc ....
};

struct Asteroid : object_with_id
{
    // ....
    // ....
};


Retaining the current overall structure of your code (so that no modifications to the high level logic is required):

a. Keep the sequences of objects in a map that maps the id of an object to the object.

1
2
 
std::map< int, SpaceShip > shipList ; // key is the id
std::map< int, Asteroid > asteroidList ; // key is the id


b. Keep track of collisions and times in terms of pairs of ids of objects.

1
2
3
4
5
6
7
8
9
10
11
 
typedef std::pair<int,int> collision_t ;

// list for all possible collision pairs
// don't see any reason why these can't be vectors
std::vector<collision_t> shipShipCollisions ;
std::vector<collision_t> shipAsteroidCollisions ;
std::vector<collision_t> asteroidAsteroidCollisions ;

// time tracking maps
std::map< collision_t, double > shipAsteroidCollisionTimers ;
std::map< collision_t, double > asteroidAsteroidCollisionTimers ;


And now, the code would look like:


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
 
void World::applyCollisions()
{
    // First clear the collision lists
    shipShipCollisions.clear ();
    shipAsteroidCollisions.clear ();
    asteroidAsteroidCollisions.clear ();

    // For every possible combination, if overlapping, add the pair to the appropriate collision list

    // For every space ship on the shipList
    for( const auto& pair : shipList )
    {
        const auto& this_ship = pair.second ;
        const int id_this = this_ship.id ;
        // For every object after the current object on the ship list
        for( const auto& that_p : shipList )
        {
            const auto& that_ship = that_p.second ;
            const int id_that = that_ship.id ;
            if( (id_this<id_that) && this_ship.isOverlappingWith(that_ship) )
               shipShipCollisions.emplace_back(id_this,id_that) ;
        }
    }

    // etc ...

}

blueeyedlion (73)
seems like the perfect solution, except that I am not exactly sure what you mean by "implementation file" for where to put this:

int object_with_id::counter = 0 ;
JLBorges (13770)
An "implementation file" is a file which is not a header file; a file that would not be #included into other translation units.

Note: I don't think it is the 'perfect' solution; it is just a reasonable solution which is within the constraints of the existing program structure.

Last edited on
blueeyedlion (73)
When I try to put that line in the world constructor, this pops up:
 
 
error: invalid use of qualified-name 'ObjectWithId::counter'
JLBorges (13770)
You need to define the variable with a static storage duration (put the definition outside a local scope).

For example, create a file object_with_id.cc :

1
2
3
 
#include "object_with_id.h"

int object_with_id::counter = 0 ;

Topic archived. No new replies allowed.