C++: Can't understand this code

Question

Here is the website: link.

This is the part that I don't understand:

template<typename L>
struct Graph {
  typedef L Location;
  typedef typename vector<Location>::iterator iterator;
  unordered_map<Location, vector<Location> > edges;

  inline const vector<Location>  neighbors(Location id) {
    return edges[id];
  }
};

What I don't understand are these lines:

typedef typename vector<Location>::iterator iterator;
      unordered_map<Location, vector<Location> > edges;

      inline const vector<Location>  neighbors(Location id) {
        return edges[id];
      }

The first line is what I'm most confused about, what does

vector<Location>::iterator iterator

do? Is it a function? A type? What does the :: do in this line of code?

For the second line, I've searched what unordered_maps are and it seems like Location is the key and vector is the mapped value? Is this right?

Regarding the third and fourth line, inline doesn't have to be there, right? I looked at the wikipedia page but it's too complicated for me to understand right now. Other than the inline, what the heck does the code do? What does neighbors(Location id) do? I think it's the parameter of neighbors but then what is edges[id]? Does it return the mapped value of the key id from the unordered_map edges?

Sorry if this is all wrong, I don't know many algorithms, almost none, in fact and now I'm trying to learn A* for my PAC-MAN game so there's a big knowledge gap, I think.

[The Definitive C++ Book Guide and List](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) — Ivan Aksamentov - Drop, Sep 20 '15 at 15:27
Also, a good IDE with "Go to definition/declaration" is an essential tool when exploring code — Ivan Aksamentov - Drop, Sep 20 '15 at 15:28
@MattWang, lazyness to read is not a good reason to ask here. There are also other sources besides books and wikipedia. "C++ iterator" in google brings up very good explanations. (-1) — user23573, Sep 20 '15 at 15:37
Am I the only one to think this question doesn't show enough personal effort ? — fjardon, Sep 20 '15 at 15:40
Okay, I did not put enough effort into this question. Because of that, I'll request for this abomination of a question to be deleted because it's terrible. — Matt Wang, Sep 20 '15 at 15:54

Hatted Rooster · Accepted Answer · 2015-09-20T15:35:43.943

typedef typename vector<Location>::iterator iterator;

This defines a new type alias iterator which maps to vector<Location>::iterator. The typedef itself isn't actually used in this piece of code though.

unordered_map<Location, vector<Location> > edges;

This defines an std::unordered_map http://www.cplusplus.com/reference/unordered_map/unordered_map/ edges in which Location (which is the templated type) is the Key value and an std::vector of Locations is the mapped value.

it seems like Location is the key and vector is the mapped value? Is this right?

That's right, Location can be accessed by accessing the first member of the pair and the vector can be accessed by accessing the second member of the pair.

 inline const vector<Location>  neighbors(Location id) {
        return edges[id];
      }

inline tells the compiler that it shouldn't treat the function as as an actual function but it should replace the code in the function body with the calling code:

Graph<int> graph;
auto result = graph.neighbors(5);

With inlining this code would translate to:

Graph<int> graph;
auto result = graph.edges[id];

Note that inline is just a hint, the compiler doesn't actually have to listen to it.

`inline` is actually completely superfluous here, because the function is implicitly `inline`. — juanchopanza, Sep 20 '15 at 15:49

Vaughn Cato · Answer 2 · 2015-09-20T15:39:00.640

The line

typedef typename vector<Location>::iterator iterator;

defines a type alias within the Graph template. It has this general form:

typedef X Y;

which makes Y an alias for type X. In this case X is

typename vector<Location>::iterator

which has the form

typename A::B

Which means the type B within the class A. The typename keyword is required in this case because vector<Location> is dependent on a template parameter.

The end result is that the type iterator within Graph<L> is an alias for the type iterator within vector<L>.

C++: Can't understand this code

2 Answers2