Detecting if 2 Iterators point to the same thing?

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

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.

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?

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.

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.

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

If you want to know if the two elements are "equal" then do:

*itA == *itB

...which dereferences the iterators (similar to pointers, except using the iterators' custom * and -> operator overloads), and compares them using that type's equality operator (==), which may have been overloaded by that type.

If you want to know whether they are the same object in memory, and not two separate but equal objects, you can compare their addresses in memory (the addresses of the objects, not the addresses of the iterators).

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.

However, you have to be aware of what data you are comparing - when using multiple inheritance, if a class inherits from both BaseA and BaseB, and you are accessing it through a BaseA* and a BaseB* pointer, the two pointers (pointing at the same class instance in memory) will have different addresses - each inherited class potentially being offset from the final derived instance.

Depending on what you are doing, you might just want to give each instance a unique ID, and then compare the IDs.

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...

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

One of the nifty things about iterators is that they were designed around the concept of pointers. Pointers are valid iterators.

And one of the nifty things about containers is that while they can implement ownership semantics, they are not forced to implement ownership semantics. An array is a perfectly valid container.

It is perfectly legal to create a container class that operates on existing allocated memory. It is also perfectly legal to have any number of iterators -- including raw pointers -- that refer to the same objects on resolution.

So while the example Servant gives will rarely be used, it is certainly valid.

The language standard leaves as undefined what happens if you compare the iterators themselves (it may crash, it may format your hard drive, it may happen to do what you wanted), but it is entirely possible that the objects the iterators are referencing can be identical objects.

I would think the standard also makes Servants solution undefined behaviour, as its comparing 2 pointers to possibly disjoint memory regions, although it often would succeed.

reinterpret_cast<uintptr_t>(&(*itA)) == reinterpret_cast<uintptr_t>(&(*itB))

That could reduce the theoretical possibility of a crash, but might still allow for an undefined result, therefore I think you should avoid doing any of this.

If you are not satisfied with the result of *itA == *itB you should just override the operator== for the data objects class.

I would think the standard also makes Servants solution undefined behaviour, as its comparing 2 pointers to possibly disjoint memory regions, although it often would succeed.

Thanks to pointer conversion rules, it is fully defined behaviour in C++ to compare two pointers for equality, provided they point to valid objects or are null pointers.

It is undefined if they do not point to an object and are not null, and consequently cannot be legally converted to void pointers.

How you use the items being pointed to is a different matter, but the comparisons of the pointers themselves is legal.

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.

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.

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.

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?

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.

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.

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.

Correct, there is a lot of very loose wording in the discussion.

Be careful of wording. This is a technical field, and items have been given very precise meanings. Subtle wording differences have large impact.

There is a world of difference between comparing two iterators and comparing the addresses of the things the iterators are referring to.

The requirements of an iterator are:

* Must be copy-constructable, copy-assignable, and destructible: X a(b); a=b;

* Must be incrementable with prefix and postfix increment: a++; ++a;

And:

* Input iterators and all other readable iterator types must also support equality tests (a==b; a!=b) and must be readable (*a; a->x)

A standard raw pointer is a perfectly legal input iterator. (In fact, it is a perfectly legal input iterator, output iterator, forward iterator, bidirectional iterator, and random access iterator).

It is not required that you can compare two iterators. For example, one iterator may be a raw pointer and another iterator may be an object instance.

However, for any InputIterator or beyond, it is completely legal to use equality operations on the item the iterator references.

It does not matter what the objects are that are being referenced, if they are actual pointers then the pointer conversion rules (section 4.10 of the current standard) absolutely require that any pointer to an object and any null pointer can be converted to a void pointer, and those void pointers can legally be compared. This can be done as an implicit conversion, or done without any warnings or diagnostics, because the standard conversions allow either zero or one conversion, which can include a pointer conversion to a void pointer.

Worded differently:

a == b is not guaranteed to work since they may not be comparable types; a may be a raw pointer and b may be some other non-pointer type; or a and b may be completely unrelated types that both happen to implement the operators necessary to be considered an iterator.

&(*a) == &(*b) must always be legal, even if a is a raw pointer and b is a fancy class instance that is part of a container library, or even if a and b are unrelated types that both implement the correct operations, and any object can be tested for equality through an implicit standard-guaranteed conversion to void pointer.

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.

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.