Generic Algorithms Flashcards
(30 cards)
What happens when fill_n algorithm’s destination is smaller than as used in fil_n
The fill_n function assumes that it is safe to write the specified number ofelements. That is, for a call of the form
fill_n(dest, n, val)
fill_n assumes that dest refers to an element and that there are at least nelements in the sequence starting from dest. It is a fairly common beginner mistake to call fill_n (or similar algorithms that write to elements) on a container that has no elements:
vector vec; // empty vector
// disaster: attempts to write to ten (nonexistent) elements in vec
fill_n(vec.begin(), 10, 0);
This call to fill_n is a disaster. We specified that ten elements should be written, but there are no such elements—vec is empty. The result is undefined.
Algorithms that write to a destination iterator assume the destination is large
enough to hold the number of elements being written.
What is a back_inserter?
An insert iterator is an iterator that adds elements to a container. Ordinarily, when we assign to a container element through an iterator, we assign to the element that iterator denotes
Back_inserter takes a reference to a container and returns an insert iterator bound to that container. When we assign through that iterator, the assignment calls push_back to add an element with the given value to the container
vector vec; // empty vector
auto it = back_inserter(vec); // assigning through it adds elements to vec
*it = 42; // vec now has one element with value 42
vector vec; // empty vector
// ok: back_inserter creates an insert iterator that adds elements to vec
fill_n(back_inserter(vec), 10, 0); // appends ten elements to vec
This call to fill_n adds ten elements to the end of vec, each of which has the value 0.
What is std::copy algorithm?
The copy algorithm is another example of an algorithm that writes to the elements of an output sequence denoted by a destination iterator.
int a1[] = {0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/sizeof(*a1)]; // a2 has the same size as a1
// ret points just past the last element copied into a2
auto ret = copy(begin(a1), end(a1), a2); // copy a1 into a2
What is std::replace algorithm
The replace algorithm reads a sequence and replaces every instance of a given value with another value.
// replace any element with the value 0 with 42 replace(ilst.begin(), ilst.end(), 0, 42);
This call replaces all instances of 0 by 42. If we want to leave the original sequence unchanged, we can call replace_copy. That algorithm takes a third iterator argument denoting a destination in which to write the adjusted sequence:
// use back_inserter to grow destination as needed
replace_copy(ilst.cbegin(), ilst.cend(),
back_inserter(ivec), 0, 42);
After this call, ilst is unchanged, and ivec contains a copy of ilst with the exception that every element in ilst with the value 0 has the value 42 in ivec.
How do we eliminate duplicates in vector
The unique algorithm rearranges the input range to “eliminate” adjacent duplicated entries, and returns an iterator that denotes the end of the range of the unique values. All elements after the unique end-of-range are duplicates of some value before end of range.
What is a predicate in algorithm
A predicate is an expression that can be called and that returns a value that can be used as a condition. The predicates used by library algorithms are either unary predicates (meaning they have a single parameter) or binary predicates (meaning they have two parameters).
What is stable sort
A stable sort maintains the original order among equal elements.
What is a labda expression
A lambda expression represents a callable unit of code.
[capture list] (parameter list) -> return type { function body }
where capture list is an (often empty) list of local variables defined in the enclosing function; return type, parameter list, and function body are the same as in any ordinary function.
The capture list is used for local nonstatic variables only; lambdas can use local statics and variables declared outside the function directly.
What is lambda expression’s type
when we pass a lambda to a function, we are defining both a new type and an object of that type: The argument is an unnamed object of this compiler-generated class type. Similarly, when we use auto to define a variable initialized by a lambda, we are defining an object of the type generated from that lambda. By default, the class generated from a lambda contains a data member corresponding to the variables captured by the lambda. Like the data members of any class, the data members of a lambda are initialized when a lambda object is created.
When is a captured variable copied in lambda expression?
As with a parameter passed by value, it must be possible to copy such variables. Unlike parameters, the value of a captured variable is copied when the lambda is created, not when it is called:
void fcn1()
{
size_t v1 = 42; // local variable
// copies v1 into the callable object named f
auto f = [v1] { return v1; };
v1 = 0;
auto j = f(); // j is 42; f stored a copy of v1 when we created it
}
Comment about capturing variables by value in lambda expression
As with a parameter passed by value, it must be possible to copy such variables. Unlike parameters, the value of a captured variable is copied when the lambda is created, not when it is called:
void fcn1()
{
size_t v1 = 42; // local variable
// copies v1 into the callable object named f
auto f = [v1] { return v1; };
v1 = 0;
auto j = f(); // j is 42; f stored a copy of v1 when we created it
}
What is std::bind ?
The bind function can be thought of as a general-purpose function adaptor (§ 9.6, p. 368). It takes a callable object and generates a new callable that “adapts” the parameter list of the original object. The general form of a call to bind is:
auto newCallable = bind(callable, arg_list);
where newCallable is itself a callable object and arg_list is a comma-separated list of
arguments that correspond to the parameters of the given callable.
The arguments in arg_list may include names of the form _n, where n is an integer. These arguments are “placeholders” representing the parameters of newCallable. They stand “in place of” the arguments that will be passed to newCallable. The number n is the position of the parameter in the generated callable: _1 is the first parameter in newCallable, _2 is the second, and so forth.
Can we use std::bind to rearrange a function call’s
Yes, we can use bind to bind or rearrange the parameters in the given callable. For example, assuming f is a callable object that has five parameters, the following call to bind:
// g is a callable object that takes two arguments auto g = bind(f, a, b, _2, c, _1);
That is, the first argument to g is bound to _1, and the second argument is bound to _2. This call to bind maps
g(_1, _2)
to
f(a, b, _2, c, _1)
That is, calling g calls f using g’s arguments for the placeholders along with the bound arguments, a, b, and c. For example, calling g(X, Y) calls
f(a, b, Y, c, X)
How can we use std::bind to bind to a functions whos arguements can’t be copied
If we want to pass an object to bind without copying it, we must use the library std::ref function. There is also a cref function that generates a class that holds a reference to const.
What are other types of iterators ?
In addition to the iterators that are defined for each of the containers, the library defines several additional kinds of iterators in the iterator header. These iterators include
• Insert iterators: These iterators are bound to a container and can be used to insert elements into the container.
• Stream iterators: These iterators are bound to input or output streams and can be used to iterate through the associated IO stream.
• Reverse iterators: These iterators move backward, rather than forward. The library containers, other than forward_list, have reverse iterators.
• Move iterators: These special-purpose iterators move rather than copy their elements.
What is an insert iterator?
An inserter is an iterator adaptor that takes a container and yields an iterator that adds elements to the specified container. There are three kinds of inserters. Each differs from the others as to where elements are inserted:
- back_inserter creates an iterator that uses push_back.
- front_inserter creates an iterator that uses push_front.
- inserter creates an iterator that uses insert. This function takes a second argument, which must be an iterator into the given container. Elements are inserted ahead of the element denoted by the given iterator.
We can use front_inserter only if the container has push_front. Similarly, we can use back_inserter only if it has push_back.
Where do inserter(s) intsert elements
When we call inserter(c, iter), we get an iterator that, when used successively, inserts elements ahead of the element originally denoted by iter.
- it = va1;
behaves as
it = c.insert(it, val); // it points to the newly added element
++it; // increment it so that it denotes the same element as before
The iterator generated by front_inserter behaves quite differently from the one created by inserter. When we use front_inserter, elements are always inserted ahead of the then first element in the container.
list 1st = {1,2,3,4};
list lst2, lst3; // empty lists
// after copy completes, 1st2 contains 4 3 2 1 copy(1st.cbegin(), lst.cend(), front_inserter(lst2));
// after copy completes, 1st3 contains 1 2 3 4 copy(1st.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));
what are iostream iterators
An istream_iterator reads an input stream, and an ostream_iterator writes an output stream.
As an example, we can use an istream_iterator to read the standard input into a vector:
istream_iterator in_iter(cin); // read ints from cin
istream_iterator eof; // istream ‘‘end’’ iterator
while (in_iter != eof) // while there’s valid input to read
// postfix increment reads the stream and returns the old value of the iterator
// we dereference that iterator to get the previous value read from the stream
vec.push_back(*in_iter++);
we can rewrite this program as
istream_iterator in_iter(cin), eof; // read ints from cin vector vec(in_iter, eof); // construct vec from an iterator range
We can also use iostream iteratos with algorithms like so:
istream_iterator in(cin), eof; cout << accumulate(in, eof, 0) << endl;
Can istream_iteratos use lazy evaluation?
Yes, istream_iterators Are Permitted to Use Lazy Evaluation
When we bind an istream_iterator to a stream, we are not guaranteed that it will read the stream immediately. The implementation is permitted to delay reading the stream until we use the iterator. We are guaranteed that before we dereference the iterator for the first time, the stream will have been read. F
What are ostream_iterator ?
An ostream_iterator can be defined for any type that has an output operator (the «_space;operator). When we create an ostream_iterator, we may (optionally) provide a second argument that specifies a character string to print following each element.
There is no empty or off-the-end ostream_iterator.
ostream_iterator out_iter(cout, “ “);
for (auto e : vec)
*out_iter++ = e; // the assignment writes this element to cout
cout «_space;endl;
We can write this loop equivalently as
for (auto e : vec)
out_iter = e; // the assignment writes this element to cout
cout «_space;endl;
The * and ++ operators do nothing on an ostream_iterator, so omitting them has no effect on our program.We can easily change this loop to execute on another iterator type. Moreover, the behavior of this loop will be clearer to readers of our code.
using std::copy to do the same thing
copy(vec.begin(), vec.end(), out_iter);
cout «_space;endl;
What are reverse iterators
A reverse iterator is an iterator that traverses a container backward, from the last element toward the first. A reverse iterator inverts the meaning of increment (and decrement). Incrementing (++it) a reverse iterator moves the iterator to the previous element; derementing (–it) moves the iterator to the next element.
For example, we can sort our vector in descending order by passing sort a pair of reverse iterators:
sort(vec.begin(), vec.end()); // sorts vec in ‘‘normal’’ order
// sorts in reverse: puts the smallest element at the end of vec
sort(vec.rbegin(), vec.rend());
// find the last element in a comma-separated list auto rcomma = find(line.crbegin(), line.crend(), ',');
The seemingly obvious way
// WRONG: will generate the word in reverse order cout << string(line.crbegin(), rcomma) << endl;
generates bogus output. For example, had our input been
FIRST,MIDDLE,LAST
then this statement would print TSAL!
iter -> position cbegin() -> 1 comma -> 2 rcomma.base() -> 3 cend() -> 4 rcomma -> 5 crbegin() -> 6
1 2 3 4
FIRST,MIDDLE,LAST
5 6
Technically speaking, the relationship between normal and reverse iterators accommodates the properties of a left-inclusive range. The point is that [line.crbegin(), rcomma) and [rcomma.base(), line.cend()) refer to the same elements in line. In order for that to happen, rcomma and rcomma.base() must yield adjacent positions, rather than the same position, as must crbegin() and cend().
The fact that reverse iterators are intended to represent ranges and that these ranges are asymmetric has an important consequence: When we initialize or assign a reverse iterator from a plain iterator, the resulting iterator does not refer to the same element as the original.
What are the Iterator categories
Input iterators: can read elements in a sequence. An input iterator must provide
• Equality and inequality operators (==, !=) to compare two iterators
• Prefix and postfix increment (++) to advance the iterator
• Dereference operator () to read an element; dereference may appear only on the right-hand side of an assignment
• The arrow operator (->) as a synonym for ( it).member—that is,dereference the iterator and fetch a member from the underlying object
Describe Input Iterator
Input iterators: can read elements in a sequence. An input iterator must provide
• Equality and inequality operators (==, !=) to compare two iterators
• Prefix and postfix increment (++) to advance the iterator
• Dereference operator () to read an element; dereference may appear only on the right-hand side of an assignment
• The arrow operator (->) as a synonym for ( it).member—that is, dereference the iterator and fetch a member from the underlying object
Input iterators may be used only sequentially. We are guaranteed that *it++ is valid, but incrementing an input iterator may invalidate all other iterators into the stream. As a result, there is no guarantee that we can save the state of an input iterator and examine an element through that saved iterator. Input iterators, therefore, may be used only for single-pass algorithms. The find and accumulate algorithms require input iterators; istream_iterators are input iterators.
Describe Output iterators
Output iterators: can be thought of as having complementary functionality to input iterators; they write rather than read elements. Output iterators must provide
• Prefix and postfix increment (++) to advance the iterator
• Dereference (*), which may appear only as the left-hand side of an assignment (Assigning to a dereferenced output iterator writes to the underlying element.)
We may assign to a given value of an output iterator only once. Like input iterators, output iterators may be used only for single-pass algorithms. Iterators used as a destination are typically output iterators. For example, the third parameter to copy is an output iterator. The ostream_iterator type is an output iterator.
