What Does Iterator->Second Mean

What does iterator-second mean?

I'm sure you know that a std::vector<X> stores a whole bunch of X objects, right? But if you have a std::map<X, Y>, what it actually stores is a whole bunch of std::pair<const X, Y>s. That's exactly what a map is - it pairs together the keys and the associated values.

When you iterate over a std::map, you're iterating over all of these std::pairs. When you dereference one of these iterators, you get a std::pair containing the key and its associated value.

std::map<std::string, int> m = /* fill it */;
auto it = m.begin();

Here, if you now do *it, you will get the the std::pair for the first element in the map.

Now the type std::pair gives you access to its elements through two members: first and second. So if you have a std::pair<X, Y> called p, p.first is an X object and p.second is a Y object.

So now you know that dereferencing a std::map iterator gives you a std::pair, you can then access its elements with first and second. For example, (*it).first will give you the key and (*it).second will give you the value. These are equivalent to it->first and it->second.

MAP C++ using itr.first-second VS itr-second

Each std::map element is stored as a std::pair containing its key and value (in the pair's first and second fields, respectively).

The std::map::insert() method returns a std::pair containing:

• a std::map::iterator pointing at the std::map element for the key which is being inserted.

• a bool indicating whether that element has been newly inserted or it already existed in the std::map.

When the code calls ret = mymap.insert(...);, ret.first is the iterator and ret.second is the bool.

Dereferencing a std::map::iterator accesses the key/value std::pair of the element which the iterator is pointing at.

Thus, since ret.first is a std::map::iterator, then ret.first->first is the element's key and ret.first->second is the element's value.

In the subsequent loop, for (it=mymap.begin(); it!=mymap.end(); ++it), it is also a std::map::iterator, pointing at a different element of the std::map on each loop iteration. Thus, when dereferencing that iterator, it->first is the element's key and it->second is the element's value.

Does std::map::iterator return a copy of value or a value itself?

The comment in stl_pair.h is misleading in this specific case.

There will be no copy, since the map::iterator actually refers to the original data inside the map (the value_type, which itself is a pair), it’s not a copy. Thus iterator::second also refers to the original data.

Is -second defined for iterator my_map.end()?

Intuitively I'm assuming it to be valid and fully initialized?

You cannot assume an iterator to an element past-the-end of a container to be dereferenceable. Per paragraph 24.2.1/5 of the C++11 Standard:

Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element
of the array, so for any iterator type there is an iterator value that points past the last element of a
corresponding sequence. These values are called past-the-end values. Values of an iterator i for which the
expression *i is defined are called dereferenceable. The library never assumes that past-the-end values are
dereferenceable. [...]

What does result.second == false mean in this code?

Since std::map and the other non-multi associative containers only store unique items there is a chance that when you insert something into it it wont actually insert since it may already be present. insert therefore returns a std::pair<iterator, bool> where the bool will be true if the insert succeeded and false otherwise.

---

I would like to point out you can get rid of the if statement in the loop. Because of how operator[] of a map works the loop can be replaced with

for (const auto & elem : vecOfStrings) // also added const here since we don't need to modify elem
{
   ++countMap[elem];
}

And now if elem exists then you increment the value and if it doesn't you added elem to the map and increment its value.

first/second to an empty map iterator to begin

As others have pointed out, your code has undefined behavior, and printing 0 is consistent with undefined behavior – as is any other behavior.

However, you may be interested in why this particular behavior occurs, as opposed to, e.g., a segfault. A likely reason is that your map implementation uses dummy nodes. These are actually quite popular for implementations of node-based containers in general.

For example, a map iterator may be a thin wrapper around a node pointer (e.g. to a node in a balanced binary search tree). Now, the obvious way to implement the end iterator is to use a null pointer here. However, it then becomes impossible to implement operator --() on the end iterator without e.g. a pointer to the container as well – and, worse, an additional branch, because now you must check in every call to this operator whether the node pointer is null (I'm abbreviating the code example a bit, by leaving out irrelevant template parameters):

template<typename U, typename V>
typename map<U,V>::iterator &map<U,V>::iterator::operator --()
{
    if ( node_ != nullptr )
    {
        // go to predecessor
        if ( node_->leftChild_ != nullptr )
        {
            for ( node_ = node_->leftChild_; node_->rightChild_ != nullptr; node_ = node_->rightChild_ );
        }
        else
        {
            node *n;
            do
            {
                n = node_;
                node_ = node->parent_;
                // may not go before begin()
                assert( node_ != nullptr );
            } while ( n == node_->leftChild_ );
        }
    }
    else
    {
        // point to last node - map must not be empty
        assert( container_->root_ != nullptr );
        for ( node_ = container_->root_; node_->rightChild_ != nullptr; node = node->rightChild_ );
    }
    return *this;
}

However, if you have a dummy node that is always the rightmost node in the tree, and implement end iterators as wrappers around a pointer to the dummy node, the nullness check and therefore the second branch become redundant and can be removed. Likewise, the use of the container_ pointer becomes completely unnecessary, and so the pointer itself can be removed from the iterator, saving space and reducing the cost to make and copy iterators. (Actually, since C++11 use of this "container pointer" is not even allowed anymore, because containers may be moved, and this does not invalidate the iterators, by definition. A valid solution would be more complex still. MINOR UPDATE: This may have been forbidden always because containers could be swapped without invalidating iterators.)

Now, this explains why an end() iterator may actually point to "real" memory. And so, if operator *() is implemented as:

template<typename U, typename V>
typename map<U,V>::reference map<U,V>::iterator::operator *() const
{
    // cannot dereference end iterator
    assert( hasSuccessor(node_) );
    return *node_;
}

As above, I added a debugging assertion here. How is hasSuccessor implemented? It actually has to ascend all the way to the top, in the worst case, to see if node_ or any of its ancestors has a right child. This check has prohibitive run time cost – i.e. it is literally forbidden by the standard. While its average complexity is only O(1), it has a worst case complexity of O(log N), but the standard requires Θ(1) even in the worst case for this operation. Granted, in a debug build, who cares, and there are other ways to implement the check, such as having a "dummy bit" somewhere in the node. The main point is that no such check is required anyway. Therefore, your attempt to dereferencing the iterator may give you a reference to the dummy node, and since it is "real" allocated memory, you can then proceed to read the mapped value. Note that this does not make the iterator "dereferencable" as far as the standard is concerned, it just means you get neither a segfault nor a program termination as an implementation detail that may change at any time without notice.

Now, there is possibly one more question as to why you get zero, as opposed to, let's say, -135, or some "random" 8-9 digit number for that matter. map is not allowed to invoke any default constructor, for example, that has side effects. Unless you use operator [], it is not even allowed to assume that your mapped type is default constructible. However, there are many other reasons why you may get a neat zero:

• For types without a constructor w/ side effects, in particular for trivially constructible types such as int, map is indeed free to initialize them as in int{}, e.g. via placement new.
• The implementation is also allowed to memset the dummy node to zeroes before use. This could be the simplest way to ensure that the pointers are zero.
• However, the most likely explanation is that you didn't allocate and free other memory of similar size in your test program, so the allocator gave you some "fresh" memory from pages the process received from the operating system. And any multi-user operating system will make sure that memory given to a process cannot contain information from a previous process that might have held the memory. The usual approach is for the OS to memset the whole page(s) to zeroes before letting the process access them.

check if second to last in an iterator

The easiest way would be to compare your iterator against one which does indeed point to the second-to-last. And an easy way to get that is:

vector::iterator secondLast = v.end() - 2;

Assuming of course that v.size() >= 2. But the above doesn't generalize to other container types, for which you could do this:

vector::iterator secondLast = (++v.rbegin()).base();

This should rewind from the last element one step, then convert to a regular (forward) iterator. This will work with other container types like lists.

Or perhaps clearer for the general solution:

vector::iterator secondLast = v.end();
std::advance(secondLast, -2);

Again this requires size of 2 and iterators of random access or bidirectional type.

And finally, a C++11 solution:

auto secondLast = std::prev(v.end(), 2);

Renaming first and second of a map iterator

If you're just concerned about readability you could do something like this:

typedef map<Vertex, Edge> AdjacencyList;
struct adjacency
{
    adjacency(AdjacencyList::iterator& it) 
      : vertex(it->first), edge(it->second) {}
    Vertex& vertex;
    Edge& edge;
};

And then:

Vertex v = adjacency(it).vertex;

---

Related Topics