Sign in to follow this  
Sean_Seanston

Detecting if 2 Iterators point to the same thing?

Recommended Posts

Basically, I have a situation where I have 2 containers of the same type, and I want to iterate through them and know when I've reached an element that was previously selected by being pointed at by an iterator.

 

I tried simply using == but that caused a crash. It's also possible of course that I did it wrong.

 

How is this meant to be done? Or should it be avoided if possible?

Share this post


Link to post
Share on other sites

iterators from two different containers will never be equal. If you dereference them you can compare the actual values of the objects in the two containers. Maybe that's what you want? Don't dereference an iterator equal to yourContainer.end() though.

Share this post


Link to post
Share on other sites

If you dereference them you can compare the actual values of the objects in the two containers. Maybe that's what you want? Don't dereference an iterator equal to yourContainer.end() though.

 

I thought along those lines... but then a problem I envisioned is that it's possible for the objects to be perfectly equal in value, therefore you'd need to know if they were different actual instances of such objects, and then we're probably back at square one...

 

Basically, it's for a system for moving items between 2 inventories. So Inventory A might have 200 of Item X and that might be selected, but Inventory B could also have 200 of Item X... so it's very important that it refers to the exact instances involved.

 

It would be very helpful if you could post a small program that shows what you tried.

 

I'll try to cut out the relevant bits that hopefully show enough to get the idea across without getting into anything irrelevant...

 

- I have an Inventory class which represents the inventory of, for example, a player.

This contains a map consisting of a pair representing the item name and its condition as an int, and another int as the value of the map which represents the quantity:

std::map< std::pair< std::string, int >, int > itemStock;

- This stock container can be accessed like so:

const std::map< std::pair< std::string, int >, int >& getStock();

- I have an iterator to remember the currently selected item for the purposes of a user interface:

std::map< std::pair< std::string, int >, int >::const_iterator selInvItem;

- What I tried then as I iterated through an inventory's stock container, was the following:

for( std::map< std::pair< std::string, int >, int >::const_iterator it = stock.begin(); it != stock.end(); it++ )
{
         if( selInvItem == it )
         {
                  //Found the currently selected item
         }
}

But it crashes with "Expression: map/set iterators incompatible".

 

Have I missed something?

 

I stepped through it withe breakpoints and the iterator I was using (selInvItem) didn't seem to be getting initialized for some reason... at least it was showing up as 0... but either way I have it so "it" is being compared with another iterator that shows up like it should when I step through the program and it still gives the same error.

 

Is comparing iterators that point to different containers just not a thing you do?

Edited by Sean_Seanston

Share this post


Link to post
Share on other sites
If you want to know if two iterators point to the same thing, you need to compare the thing they point to, not the iterators themselves.

Comparing iterators from two different containers is undefined behavior.

Share this post


Link to post
Share on other sites


Is comparing iterators that point to different containers just not a thing you do?

 

It is not a thing you do (like I said before). 

 


but then a problem I envisioned is that it's possible for the objects to be perfectly equal in value, therefore you'd need to know if they were different actual instances of such objects, and then we're probably back at square one...

 

If comparing objects by value is not acceptable, and you're storing objects by value (which you are) in two separate containers, then what you're asking is impossible. By definition the "same" object will be two different instances - they can't be the same, they occupy different spaces in memory. One is a copy of the other.

 

You either need to be comparing pointers, or give the objects some unique id and compare by value using that unique id (so two copies of the same object will compare as equal).

 

And taking a pointer to one of the objects in your containers limits your options. If you add or remove anything to the container, the pointer (and similarly any iterator from that container) may now be invalid. 

 

I assuming the data structures you're using right now is because you want to treat items of a certain type and of a certain condition as the same right? Like, if you buy 4 brand new bolts of cloth, you want it to be merged with the player's existing x bolts of brand new cloth? The data structures you have now don't allow for multiple instances of an item of a particular condition in one container. 

Share this post


Link to post
Share on other sites

I wish I could find the place where I read it again (although it could have been in a C not C++ context or relational operators), but I remember comparing pointers to separately allocted objects being pointed out as not well-defined in the standard.

Lining your path with traps for which you need to be a language lawyer is one of the things making C/C++ annoying.

Edited by wintertime

Share this post


Link to post
Share on other sites

In summary for the OP:

 

The result of operator==() on two iterators is true if the iterators both indicate the same element in their range, false if they indicate different elements in their range, and undefined otherwise (eg. one-past-the-end of their range, or different ranges completely).  Undefined behaviour is undefined.

 

The result of operator==() of two object instances indicates the objects compare as equivalent. If it indicates two instances are equivalent when in fact they are not, you have a bug and need to fix your implementation.

 

If you find you have an inventory of 200 hats, operator==() between any specific two different hats should return false.  If the same hat is in two different inventories (for example, "things on my head" and "things I have with me", assuming the first is considerably smaller than the second but I'm not judging), you probably need to include a distinct object ID in your class and have it a part of the algorithm calculating the result of operator==() on your hats.

Share this post


Link to post
Share on other sites

The result of operator==() on two iterators is true if the iterators both indicate the same element in their range, false if they indicate different elements in their range, and undefined otherwise (eg. one-past-the-end of their range, or different ranges completely). Undefined behaviour is undefined.


That's not right. You are allowed to compare an iterator in a range with the `end' of the range. We do that all the time.

Share this post


Link to post
Share on other sites


As mentioned, you can't compare two iterators from different containers. You can however, compare the elements/objects the iterators are referring to.

 

Yeah... seems that's all it is alright; I remembered later too that even resizing a container will invalidate an iterator, so clearly iterators are very much linked to the state of their particular containers.

I read up on iterators and saw stuff about not comparing iterators from different containers, but I somehow thought it might at least return false if they were different, or just not allow me to compile.

 

Guess one way of getting around it is just by testing if we're dealing with the same container first, then continuing as appropriate.

 


I assuming the data structures you're using right now is because you want to treat items of a certain type and of a certain condition as the same right? Like, if you buy 4 brand new bolts of cloth, you want it to be merged with the player's existing x bolts of brand new cloth? The data structures you have now don't allow for multiple instances of an item of a particular condition in one container.

 

Yeah, I think that's right. Though I'm not sure exactly about the last sentence...

Basically, what I want is:

- Have an inventory that stores how many of whatever items someone/something has.

- Item type is referred to using a string.

- Items have a condition value referring to their state of repair, from 1-5.

- The quantity of items stored is recorded using an int.

 

So my idea was: a map using an std::pair as a key, the pair referring to an item type of a certain condition, and the value being the amount of that item with that condition that is being stored. Sooner or later, it may happen that some of these items might be equipable/usable by a character, in which case I would just use the string to look up in some sort of database that would give me the item functionality.

 

Did you mean that it wouldn't allow, for instance, storing 2 items of the same condition and type in separate entries? That was intentional, if so. Seemed to make sense as the minimum/simplest data needed to record the kind of items in an inventory, since all items of the same type and condition ought to be identical (or so I reckon right now). Or did I mess up somewhere?

 

The somewhat annoying thing about all this is that right now all I'm really trying to do is knock out a simple but functional text-based (well, bitmap fonts...) menu UI that will allow me to accomplish the bare minimum of user input and absolutely necessary output in order to make the game actually playable. Even aiming for something quick, temporary and hackish ends up taking longer than you even suspected it would sometimes...

Which leads me to wonder:

Are there any particular well-known/popular/useful libraries around that allow someone to implement simple menu systems quickly without much hassle? I know Unity can do GUIs, and I definitely intend to explore Unity as soon as I get a new computer that will run it (Vista...), but there must be standalone C++ libraries for this, right?

Share this post


Link to post
Share on other sites

If I were you, i would just start with the simplest design: Make an InventoryItem class that has name, condition and quantity. Then have a vector of those. For the selected item in your UI, you can just store an index into the vector.

 

Right now you're basing your data structures on one particular requirement of your inventory, but I suspect it will become problematic when you factor in other requirements (as you are finding out, with displaying them in a menu). A vector is simple and easy to understand.

 

This requirement: 

 

 


it wouldn't allow, for instance, storing 2 items of the same condition and type in separate entries? That was intentional,

 

is still easily met. When adding an item, just search through the inventory vector to look for entries that have a matching name/condition, and then combine the amounts instead of adding a new item. You'd still have to write that code anyway with your map (i.e. check if an item already exists, and then merge instead of add), so it doesn't really get you anything.

    vector<InventoryItem> inventory;
    InventoryItem itemToAdd;
    auto it = std::find_if(inventory.begin(), inventory.end(),
        [&itemToAdd](InventoryItem &item) { return item.Condition == itemToAdd.Condition && item.Name == itemToAdd.Name; });
    if (it != inventory.end())
    {
        it->Quantity += itemToAdd.Quantity;
    }
    else
    {
        inventory.push_back(itemToAdd);
    }

Are there any particular well-known/popular/useful libraries around that allow someone to implement simple menu systems quickly without much hassle? I

 

If you stated what rendering API you're using, I'm sure people would have suggestions.

Edited by phil_t

Share this post


Link to post
Share on other sites

 

The result of operator==() on two iterators is true if the iterators both indicate the same element in their range, false if they indicate different elements in their range, and undefined otherwise (eg. one-past-the-end of their range, or different ranges completely). Undefined behaviour is undefined.


That's not right. You are allowed to compare an iterator in a range with the `end' of the range. We do that all the time.

 

Oops, right, brainfail.  I was already thinking ahead to dereferencing the iterators.  One-past-the-end and singular iterators are always in their range, just like all sets contain the null set.

Share this post


Link to post
Share on other sites

I'll try to cut out the relevant bits that hopefully show enough to get the idea across without getting into anything irrelevant...



- I have an Inventory class which represents the inventory of, for example, a player.

This contains a map consisting of a pair representing the item name and its condition as an int, and another int as the value of the map which represents the quantity:

std::map< std::pair< std::string, int >, int > itemStock;

- This stock container can be accessed like so:

const std::map< std::pair< std::string, int >, int >& getStock();

- I have an iterator to remember the currently selected item for the purposes of a user interface:

std::map< std::pair< std::string, int >, int >::const_iterator selInvItem;

- What I tried then as I iterated through an inventory's stock container, was the following:

for( std::map< std::pair< std::string, int >, int >::const_iterator it = stock.begin(); it != stock.end(); it++ )
{
if( selInvItem == it )
{
//Found the currently selected item
}
}

But it crashes with "Expression: map/set iterators incompatible".



Have I missed something?

 

Your example has two map iterators. Your error message says you were comparing a map iterator to a set iterator. I believe the error message.

 

Also, if you're actually comparing map items to set items, the map iterator is going going to be pointing to the pair in the map and the set iterator is going to be pointing to an entry in some completely separate structure. The address comparison is pointless in that case. They'll never be the same.

 

And there's no reason to loop through a map looking for something you already have an iterator to. Looking up stuff is what maps are for. map.find(key) should work fine to see if that particular key is in there. If your inventory is a map, and you're looking at some inventory item with the same key as some other item, you know they're actually the very same items.

 

Why store the selected item as an iterator instead of a key to your map? That would really simplify things.

Edited by Pink Horror

Share this post


Link to post
Share on other sites

Your example has two map iterators. Your error message says you were comparing a map iterator to a set iterator. I believe the error message.

 

He's comparing two set iterators. It's a runtime error message. The error message is confusing, I assume the same underlying error message code is used for both map and set iterators.

 

If he were actually comparing a set iterator to a map iterator, it would generate a compile error, as they are different types.

Edited by phil_t

Share this post


Link to post
Share on other sites

 

This could be done like this:
&(*itA) == &(*itB)
Dereferencing the iterators to get (references to) the actual elements, and then getting the addresses of those actual elements in memory, and comparing those addresses.

 
If those two iterators are from different containers, how could that ever evaluate to true? Unless you can have containers somehow overlapping in memory...

 
*facepalm* I wasn't thinking clearly.

It is *possible* using custom allocators, but using an allocator to allocate the *same* memory location for two *different* containers would be really weird.

 

I wish I could find the place where I read it again (although it could have been in a C not C++ context or relational operators), but I remember comparing pointers to separately allocted objects being pointed out as not well-defined in the standard.
Lining your path with traps for which you need to be a language lawyer is one of the things making C/C++ annoying.

 

Yes, I was pointing how how it could be done, and immediately followed up with one potential pitfall - multiple inheritance giving different addresses to ""the same"" instance (the only pitfall that came to my mind), and a better solution - using unique IDs for each object, if the OP is storing classes he can alter the definitions of. I don't advocate using memory addresses as unique identifiers for general purposes (though sometimes it is useful) - I should've been more explicit in that regard. smile.png

Edited by Servant of the Lord

Share this post


Link to post
Share on other sites

I remembered later too that even resizing a container will invalidate an iterator

Sometimes. Not always. Each function for each container has different guarantees about whether it'll invalidate the iterators, and which iterators it'll invalidate.

A basic example is std::vector::pop_back(). That'll invalidate the last iterator (and the end() iterator). But it also guarantees it won't invalidate the other iterators.

See std::vector::pop_back(), and the section labeled "Iterator validity". Each function's page has the details for that function/container. You don't have to worry about memorizing that detail, only remembering to *check*, and overtime you'll remember the details for the ones you use most frequently.
 

so clearly iterators are very much linked to the state of their particular containers.

Yes. Iterators and pointers to the raw memory, depending on the container. 

The point of iterators and pointers pointing at elements is to hold onto them for a short time for the use of a single function or algorithm. For referring to objects long-term, you need a different method - that's not iterators' purpose (and dangerous for pointers to), because containers need to shuffle around their objects in memory.
 

Guess one way of getting around it is just by testing if we're dealing with the same container first, then continuing as appropriate.

I think you took the wrong off-ramp, and need to get back on the highway for another couple exits before making your turn.

What I mean is, take a step back and don't ask "how can I check if the iterators refer to the same object", and instead ask, "What is my actual goal again? How can I go about implementing that?"
 
 

- Have an inventory that stores how many of whatever items someone/something has.
- Item type is referred to using a string.
- Items have a condition value referring to their state of repair, from 1-5.
- The quantity of items stored is recorded using an int.


 
Personally, I wouldn't use a string to identify them, but I'll do it that way below anyway.
 
You have two conflicting 'requests' for this container. The quantity of items is stored (great! So all items of the same type are identical!), but differing durability/condition on each item (oh, so they're not identical?). Since they aren't actually identical (they have different conditions), each item (even of the same type) should be different elements. You don't need compression or need to micro-manage the memory here, items are very small, memory-wise.
 
An easy straightforward way to doing this is:

struct Item
{
     std::string name;
     Enum type;
     int condition = ...;
     Stats stats;
};
 
typedef std::vector<Item> Items;
typedef size_t ItemIndex;
typedef ItemIndex InvalidItemIndex = ItemIndex(-1);
 
//Convenience functions. Iterates over the container and looks up an index using the item name.
//If multiple items exist with the same name, returns the first one found. If no item in 'items' exists with that name, returns 'InvalidItemIndex'.
ItemIndex FindFirstIndexWithName(const Items &items, const std::string &name);
 
//If it exists, "erases" that index from 'items'. To prevent other indices from becoming invalid,
//that item's name is just set to "" (an empty string), so we know that spot is available for re-use.
void EraseItemByIndex(Items &items, ItemIndex indexToDelete);
 
//Adds an item to the container and returns its new index.
ItemIndex AddItem(Items &items, Item itemToAdd)
{
      //Check for the first available spot we can re-use, by looking for an item with an empty string name (which means we previously erased it).
      ItemIndex availableIndex = FindFirstIndexWithName(items, "");
 
      if(availableIndex != InvalidItemIndex)
      {
           items[availableIndex] = itemToAdd;
           return availableIndex;
      }
      
      //If the index returned is invalid, that means we need to create a new spot.
      //This potentially invalidates any *iterators*, but our indices are still fine.
      items.push_back(itemToAdd);
 
      //The new index is the final index in the container.
      return (items.size() - 1);
}
 
struct Player
{
     ItemIndex equippedHelm = InvalidItemIndex;
     ItemIndex equippedChestPiece = InvalidItemIndex;
     ItemIndex equippedWeapon = InvalidItemIndex;
    
     Items inventory;
};

 
I'd actually do it a bit more complicated than this, probably using std::unordered_maps, unique IDs, and more layers of redirection, but for a simple game, there's no point in overcomplicating it.
 
The key is, make it simple, and write convenience functions to do the heavy lifting for you.

Share this post


Link to post
Share on other sites


When adding an item, just search through the inventory vector to look for entries that have a matching name/condition, and then combine the amounts instead of adding a new item. You'd still have to write that code anyway with your map (i.e. check if an item already exists, and then merge instead of add), so it doesn't really get you anything.

 

Hmm... yes, that's true. Hadn't really got to that part yet unfortunately.

 

I'll probably go with that then. Using maps can be very verbose too, especially if you're not using C++11 like I'm not, and especially when that map contains a pair...

 


If you stated what rendering API you're using, I'm sure people would have suggestions.

 

Oh yeah, I'm using OpenGL.

 


And there's no reason to loop through a map looking for something you already have an iterator to. Looking up stuff is what maps are for. map.find(key) should work fine to see if that particular key is in there.

 

Well what I was doing was iterating through the whole map to print out the name/condition/quantity of each item to the screen. The iterator was for detecting which item should be "selected" both in visual terms on screen and in terms of being the item to manipulate in the case of moving etc.

 


The point of iterators and pointers pointing at elements is to hold onto them for a short time for the use of a single function or algorithm. For referring to objects long-term, you need a different method - that's not iterators' purpose (and dangerous for pointers to), because containers need to shuffle around their objects in memory.

 

I'll be sure to keep this in mind in future. Makes sense.

 


The quantity of items is stored (great! So all items of the same type are identical!), but differing durability/condition on each item (oh, so they're not identical?). Since they aren't actually identical (they have different conditions), each item (even of the same type) should be different elements. You don't need compression or need to micro-manage the memory here, items are very small, memory-wise.

 

I think I might have been averse to making another class unless absolutely necessary at the time I planned out the system... I remember working on a project a few years ago which got bloated to hell with classes and a needlessly complicated architecture that may have irrationally scared me away from another class in this case...

 

Probably for the best to have another class. Especially since it's conceivable that condition won't be the only distinguishing attribute for a stored item in the end.

 

I'll think about all this and see what I come up with. Thanks all.

Share this post


Link to post
Share on other sites


Personally, I wouldn't use a string to identify them, but I'll do it that way below anyway.

 

Regarding this, why is that exactly BTW?

 

Is it just that you might envision a situation where more than 1 item type might have the same name, or is it something else?

 

What I've actually been planning has been what is probably best described as the Flyweight pattern, which I've also used before.

 

What I was going to do exactly was mark the Inventory entry with the std::string to signify the type, and then I would have looked up a table of ItemType objects which described all of the characteristics common to that type.

As it is now, since I'm replacing the map with a vector of Item objects, I'm going to just give the Item class a shared_ptr< ItemType > member that refers to the ItemType object found in a map of all ItemTypes keyed by an std::string.

 

So I'll then just have some kind of getType() function in the Item class, and use that to access its name etc. when necessary.

 

Is that closer to what you were thinking about, or was it something completely different?

Share this post


Link to post
Share on other sites

Compared to an enum, a std::string:

- takes up more space

- costs more to hash

- allocates heap memory

- is "weakly-typed"... if you mis-type the string name for an item somewhere in your code, you won't find out until runtime, instead of compile time

 

 

Why not just use an enum? It addresses all those problems.

 

Now, if you need to be able to dynamically add new types of inventory items without recompiling your code (like, by just editing a game data file), then you will need some kind of late-binding like a string would offer. Or, you could dynamically generate a new integer id or something. Depends on how your game is setup.

 

Maybe rename ItemType to ItemCharacteristics, or ItemDescription.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this