Heap/Priority Q constructors used in chapter 11

#1

I was going through Chapter-11 when I couldn’t figure out how these PQ are being initialized/constructed. I’ve listed 2 examples here. I was also wondering if learning these hard to remember initializations is “truly necessary” to getting a job at say google, and if these constructors couldn’t be made simpler?

The algos for these problems are fairly straightforward but the syntax of these constructors are fairly involved.

Page-169 ebook:

priority_queue<string, vector, function<bool(string, string)>> min_heap( [] (const string&a, const string&b) { return a.size() >= b.size(); });

Confused by the above constructor/initialization of PQ variable ‘min_heap’.
What does [] refer to? I assume whatever is inside the parenthesis after ‘min_heap’ is the compare function.What constructor is being used from these two?

http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

explicit priority_queue (const Compare& comp = Compare(),
const Container& ctnr = Container());

template
priority_queue (InputIterator first, InputIterator last,
const Compare& comp = Compare(),
const Container& ctnr = Container());

Problem 11.1: Page- 171 ebook:

priority_queue<IteratorCurrentAndEnd, vector, greater<> > min_heap;

It’s not clear what role struct IteratorCurrentAndEnd is playing here. What does it specify in the constructor? Which constructor definition is being used?
From the constructors described at http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/ they don’t match any.

0 Likes
#2

For your first question: the comparison function is a lambda and its notation [] is available to specify capture elements and it is called capture list.

Your second question: the min_heap is holding elements of type IteratorCurrentAndEnd and its named so just because it can hold iterators. It is invoking the default constructor and the comparison function object used is std::greater.

0 Likes
#3

Hi @googlejob,

It is good to know those initializations since those are best-practice which shows how good you know C++ (assuming you use C++ for interview). However, I think it might be a little over-simplified about getting a job at Google by using only one single piece knowledge here.

0 Likes
#4

So I looked up the capture list syntax and what it means. thanks. This seems like a really advanced concept and probably not many C++ programmers know this.

Yes, I agree that it’s only a single-piece of knowledge so only one piece doesn’t make that much difference. But I guess in general I was confused as to whether one needs to get into nitty-gritties of these syntax issues to get a job at google.

E.g. for 11.1 I figured out the algo to use pretty fast, but that code piece with “struct IteratorCurrentAndEnd” and how the IteratorCurrentAndEnd is advances and tracks the right index in the element the array from which the next smallest element is picked, is a little complicated. It seems to me that one can’t naturally think of these structures easily and similar processing could be done using a vector of current indices in the sorted_arrays vector of vectors.

0 Likes