Generic Algorithms Flashcards
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.
