std::make_pair() is a helper template function that simplifies creating a pair of
values. Rather than type
f(std::pair<const char *, int>("hello", 1));
std::make_pair() lets you type
f(std::make_pair("hello", 1));
instead. Briefly sketch the code implementing std::make_pair(), and
explain how std::make_pair() works.
std::make_pair() is implemented roughly as follows:
template < typename T1, typename T2 >
std::pair
make_pair(T1 v1, T2 v2) {
return std::pair(v1, v2);
}
std::make_pair() relies on the compiler's template-resolution mechanisms
to figure out the pair types T1 and T2, rather than have to specify
them explicitly as required by std::pair directly.
Most people seemed to have the idea down, but failed badly when writing the
code, describing a function that, for example, returned nothing instead of a
pair. The template part of the code was (literally) all over the place; one
recurring example was
template < class A, class B >
make_pair () {
A arg1
B arg2
// whatever
}
Almost everybody also seemed to think that maps were part of the answer.
Although maps use pairs, pairs are a separate data structure from maps. Just
as you don't have to declare a vector to use an integer, you don't have to
declare a map to use a pair.
Rewrite the code
typedef std::vector<int> ivec;
typedef ivec::const_iterator ivec_citer;
typedef std::map<std::string, ivec> siv_map;
typedef siv_map::const_iterator sivmap_citer;
int main()
const siv_map ret = xref(cin)
for sivmap_citer i = ret.begin(); i != ret.end(); i++
cout << i->first << " occurs in line(s): "
ivec_citer j = i->second.begin()
cout << *j
++j
while j != i->second.end()
cout << ", " << *j
++j
to eliminate all loops. If you don't remember exactly how a generic algorithm
works, make sure you explain how you're using it.
The for loop successively works on each element in ret, so the for-body
can be moved into a separate function and the for itself can be replaced by a
call to the std::for_each() generic algorithm.
static void
print_element(siv_map::value pr)
cout << i->first << " occurs in line(s): "
ivec_citer j = pr->second.begin()
cout << *j
++j
while j != pr->second.end()
cout << ", " << *j
++j
int main()
const siv_map ret = xref(cin)
std::for_each(ret.begin(), ret.end(), print_element);
The while loop in print_element() is the only remaining loop. Because it
just iterates through a sequence of strings, outputting each, it is easily
replaced by a copy to an ostream iterator:
static void
print_element(siv_map::value pr)
cout << pr->first << " occurs in line(s): "
std::copy(pr->second.begin, pr->second.end(),
std::ostream_iterator(cout, ", "))
cout << "\n";
As an alternative, you could re-impelment print_element() as an ostream
insertion operator for the elements of siv_map
std::ostream &
operator << (std::ostream & os, siv_map::value_type e)
os << i->first << " occurs in line(s): "
std::copy(pr->second.begin, pr->second.end(),
std::ostream_iterator(os, ", "))
return os << "\n";
Now main() too can be implemented as a copy to an ostream iterator:
int main()
const siv_map ret = xref(cin)
std::copy(ret.begin(), ret.end(),
std::ostream_iterator<siv_map::value_type>(std::cout))
Not a lot of people got this right. Most people who got it wrong still had
explicit loops in their code after rewriting; other people used odd choices for
generic algorithms (such as std::find_if()) without justifying why they
used them. A few people tried to talk their way through without showing any
code at all.
A colleague of yours is attempting to do an asymptotic analysis of the code for
the fifth programming assignment, but produced a contradictory result. The
code moves a linear sequence of bytes from one place in memory to another place
in memory, and so takes O(n) time (or moves). But the source and
destination rectangles have O(hw) bytes, which is equivalent to
O(n2) (by letting n = max(h, w)).
Describe the explanation you give your colleague to clear up the contradiction.
Your colleague is confusing structure and size. While it is true that a
rectangle occupies a linear segment of memory, what's important is the amount
of memory that linear segment takes up, and the amount of memory used by a
rectangle is O(hw).
I have to admit that I had trouble understanding most of the answers given for
this question. I don't believe that anybody pointed out that the problem was
confusing a linear structure with the size of the structure, although some
people attempted to make the cryptic argument that O(n) = O(n2). A number of people argued that, yes, there are hw bytes stored, but
you can move 8 (or 4) at a time, so it's really a linear number of moves.
Unfortunately, for that argument to be correct, you'd have to believe that
n2/8 can be bounded above by n, which a little math will show is
not true for n larger than 9.