Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
506 Cards in this Set
- Front
- Back
Who and when crated C++? |
Who and when crated C++? Bjarne Stroustrup 1985 *-------------------------* Yes |
|
hello world c++ console ( print out ) |
#include "iostream" |
|
When an overflow and round-off errors can occur? |
Overflow and round-off errors can occur when the result of a calculation is outside a computer's numeric range (i.e. either very big or very small). |
|
What program combines machine code with previously translated machine code for input/output and other services to build your program? |
linker takes your machine code file and the necessary parts from the iostream library and builds an executable file |
|
What is the compiler? |
the program that translates the source code into object code |
|
c++ console application basic include |
#include "iostream" |
|
recommended way to hold a console app |
#include "iostream" #include "stdio" getchar(); |
|
equivalent for |
count << "Hello World!" << endl; |
|
Integer type |
Integer type ==> int, unsigned int, short |
|
When dealing with strings you need to include what class |
String |
|
static cast |
data type conversion |
|
x += 4 ie equivalent to |
x = x + 4;
x++; vs ++x; |
|
cin >> a >> b; is equivalent to |
cin >> a; |
|
"stringstream" |
this standard header file defines a class called stringstream. It allows string-based object to be treated as a stream. This way we can perform extraction or insertion operation from/to string. int myint; |
|
the default type for floating point literals is |
double |
|
define constants using directives |
#define
the compiler literally replace every occurrence of the identifier with what has been defined |
|
What operator accepts one parameter, which can be either a type or a variable itself and returns the size in byte of that type of object |
sizeof() |
|
explicit type casting operator |
the simplest method of type casting |
|
fundamental data type |
char - 1 byte short int (short) - 2 bytes |
|
C++ way of intializing variables |
type identifier = (initial_value); |
|
short |
-32768 to 32767 |
|
enumerated types |
enum Weekday { MON, TUE, WED, THU, FRI, SAT, SUN } |
|
void function cannot be ____________ |
passed as variable |
|
get length of a string |
name.length(); |
|
name.length(); |
s.substr(i) The substring of s from index i to the end of the string
s.substr(i, n) The substring of s of length n starting at index i |
|
Read string s from the input stream f |
getline(f, s) |
|
concatenates two strings. |
string fname = "Harry"; |
|
setw(8) |
setw(8) - used to set the width of the next output field
cout << "I is " << i << ". " << setw(8) << setprecision(3) << fixed << j + 1 << endl;
|
|
java doc comment for function style |
/** |
|
inline functions |
inline void messageRepeat(int r, string message) {
for (int i = 0; i < r; i++ )
This technique is generally good when we want our code to run a little faster and it is only beneficial when we have short enough function. It is faster due to the fact that inline functions do not have to work with the stack. It makes the binary slightly smaller. |
|
selection operation |
C++ has a selection operator of the form
else y = -x; |
|
explicit cast |
int pennies = static_cast(100 * (amount_due - amount_paid)); |
|
It does not make sense in most circumstances to compare floating-point numbers exactly. Instead, |
we should test whether they are close enough. That is, the magnitude of their difference should be less than some threshold. Mathematically, we would write that x and y are close enough if |x - y| <= ε |
|
if (-0.5 <= x <= 0.5) // Error |
This looks just like the mathematical test –0.5 ≤ x ≤ 0.5. Unfortunately, it is not. Let us dissect the expression -0.5 <= x <= 0.5. The first half, -0.5 <= x, is a test with outcome true or false, depending on the value of x. The outcome of that test (true or false) is then compared against 0.5. This seems to make no sense. Can one compare truth values and floating-point numbers? Is true larger than 0.5 or not? Unfortunately, to stay compatible with the C language, C++ converts false to 0 and true to 1. |
|
De Morgan’s Law |
De Morgan’s Law has two forms: one for the negation of an and expression and one for the negation of an or expression: |
|
Test for failed stream due to incorrect user input |
if (cin.fail()) { cout << "End of input.\n"; |
|
cin idiio |
Because the expression cin >> x has cin as its value, and you can use a stream as the condition of an if statement, you can use the following test: |
|
once a stream fails, all further input operation also fails unless |
cin.clear(); |
|
Buffon needle experiment def |
A needle of length 1 inch is dropped onto paper that is ruled with lines 2 inches apart. If the needle drops onto a line, we count it as a hit. |
|
Sets the seed of the random number generator. |
srand(time(0)); |
|
To generate a random value ranging between a and b, you have to make a simple transformation: |
double r = a + (b - a) * (rand() * 1.0 / RAND_MAX); |
|
static class member and its initialization |
class Y { |
|
class definition |
class ClassName { |
|
When to use virtual destructors? |
Virtual destructors are useful when you can delete an instance of a derived class through a point to base class.
since the Base's destructor is not virtual and b is a Base* pointing to Derived object, delete b has undefined behavior. In most implementations, the call to the destructor will be resolved like any non-virtual code, meaning that the destructor of the base class will be called but not the one of the derived class, resulting in resources leak. |
|
Declaring global variables |
int integer; |
|
char size |
char size 1 byte -128 to 127 |
|
alternative way to initializing variables in C++ |
int a(2); // initial value = 2 |
|
Strings in C++ |
C++ language library provides support for strings through the standard sting class. |
|
include needed for stirngs |
#include "string" |
|
how to express octal |
0113 //ocatel precede with 0 |
|
scientific notation aka exponential notation |
use e
2×10^0 = 2 |
|
constants in c |
#define PI 3.14159 |
|
declaring constant with specific type |
const int pathwidth = 100; |
|
Passing vectors by constant reference |
passing a vector into a function by value us unfortunately somewhat inefficient, because the function must make a copy of all elements. The cost of a copy can be avoided by using a constant reference |
|
unlike all other parameters, array parameters are always passed by _______________ |
reference |
|
remove an element from a vector |
values.pop_back(); |
|
you can use #define to define macros |
#define getmax(a,b) a>b?a:b |
|
typeid (expression) |
typeid allows to check the type of an expression
|
|
static_cast use |
static_cast can perform conversions between pointers to related classes, not only from the derived class to its base, but also from a base class to its derived. This ensures that at least the classes are compatible if the proper object is converted, but no safety checks performed during run-time to check if the object being converted is in fact a full object of the destination type. Therefore, it is up to the programmer to ensure that the conversion is safe. |
|
static_cast can also be used to perform any other non-pointer conversion that could also be performed implicitly like |
double d = 3.14149265; |
|
references initialization |
always init a reference |
|
True or False: Objects should have a defined lifetime |
True |
|
Which of the following statements are true when working with variables in C++? (Choose 2) |
bd |
|
create a point c++ way |
void f() { |
|
in order to derive a class from another, we use a _______ |
colon (:) |
|
abstract base classes |
in an abstract base class e could leave member functions without implementation at all this is done by appending =0 to the function declaration |
|
the main difference between an abstract base call and a regular polymorphic class is |
is that because in abstract base classes at least one f its members lacks implementation we cannot create instances (objects) of it. |
|
function templates |
special type of function that can operate with generic types template template identifier function_declaration; GetMax (x,y); |
|
expression *x can be read as |
expression *x can be read as pointed by x |
|
expression (*x).y can be read as |
expression (*x).y can be read as member y of object pointed by x |
|
classes can be defined not only with the keyword class but also with keywords |
struct and union |
|
static members |
a class can contain static members, either data or function static data members of a class are also known as "class variable"
|
|
default constructor |
if you do not declare any constructor in a class definition, the compiler assumes the class to have a default constructor with no arguments
The compiler assume that CExample has a default constructor, so you can declare objects of this class by simply declaring them without any arguments CExample ex; |
|
CRectangle rectb; |
CRectangle rectb; // correct |
|
Overloading constructors def |
like functions constructors can also be overloaded with more than one function that have the same name but different types or number of parameters |
|
Enumerations |
enum enum_name { |
|
typedef |
typedef existing_tye new_type_name; |
|
unions |
unions allow one same portion of memory to be accessed as different data types |
|
the arrow operator -> |
this is a dereference operator that is used exclusively with pointers to objects with members |
|
inheritance C++ syntax |
class derived_class_name: public base_class_name { /* ... */ }; |
|
virtual member def |
a member of a class that can be redefined in its derived classes is know as virtual member. On order to declare a member of a class as virtual, we must precede is declaration with the keyword virtual: |
|
The Car class inherits from the Vehicle class. The Car class contains one constructor which does not specify a particular Vehicle constructor. Which of the following is true? |
a |
|
like any other type, structure can be pointed by its on type of pointers: |
struct movies_t { movies_t* pmovie; |
|
scope operator :: |
specifies the class to which the member being declared belongs |
|
override the + operator for class CVector |
in class |
|
multiple inheritance |
class CR: public CP, public CO; |
|
class template |
template class mypair { |
|
template specialization |
if we want to define a different implementation for a template when a specific type is passed as template parameter, we can declare a specialization of that template mycontainer (T arg) {element=arg;} |
|
non-type parameters for template |
templates class mysequence { |
|
trying to reset an object by calling a constructor |
the constructor is invoked only when an objects is first created. You cannot call the constructor to reset an object: |
|
conditional operator |
the conditional operator evaluates an expression returning a value if that expression is true and a different one of the expression is evaluated fo false |
|
comma operator |
the comma operator (,), is used to separate two or more expression that are included where only one expression is expected. When the set of expressions has to be evaluated for a value, only the rightmost expression is considered |
|
stringstream |
the standard header file defines a class called stringstream that allows a string-based object to be treated as a stream. |
|
exit function |
exit is a function defined in the cstdlib library |
|
explicit type casting operator |
type casting operators allow you to convert a datum of give type to another. The simples one, which has been inherited from the C language, is to precede the expression to be converted by the new type enclosed between parentheses (); i = (int) f; i = int (f); |
|
inline function |
inline specifier indicate the compiler that inline substitution is preferred to the usual fnction call mechanism for a specific function. This does not change the behavior of a function itself but is used to suggest to the compiler that the code generated by he function body is inserted at each point the finction is called, instead of being inserted only once and perform a regular call to it, which generally involves some additional overhead in running time. |
|
Function __________ be overloaded only by its return type. |
Function cannot be overloaded only by its return type. At least one of ots parameters must have a different type |
|
recursivity def (factorial body example) |
recursivity is the property that functions have to be called by themselves.
|
|
multidimensional arrays are just an abstraction for programmers since we can obtain the same results with a simple array just by putting a factor between its indices |
int jimmy [3][5]; |
|
arrays as parameters |
void procedure(int arg[]. int n) |
|
reference operator (&) |
ted = &andy; |
|
dereference operator |
bath = *ted; |
|
include guard |
include guard is a technique which uses a unique identifier that you #define at the top of the file
classs X { }; |
|
//x.h |
//b.h |
|
void pointer |
void type of pointers is a special type of pointer. In C++ void represents the absence of type, so void pointers are pointers that point to a value that has no type. |
|
null pointer |
a null pointer is a regular pointer of any pointer type which has a special value that indicates that it is not pointing to any valid reference or memory address. This value us the result of type-casting the integer value zero to any pointer type. |
|
pointers to function |
C++ allows operator with pointer to functions. The typical use of this is for passing a function as an argument to another function, since these cannot be passed dereferenced. In order to declare a pointer to a function we have to declare it like the prototype of the function except that the name of the functions is enclosed between parentheses () and an asterisk (*) is inserted before the name |
|
example a function minus that is a pointer that has two parameters of type int |
int (* minus)(int, int) = substraction; |
|
Pointer to function src |
#include |
|
operators new and new[] |
in order to request dynamic memory we use the operator new. new is followed by a data type specfier and -if a sequence of more than one element is required the number of these within brackets []. It returns a pointer to the beginning of the new block of memory allocated. Its form is: |
|
nothrow def |
bobby = new int [5]; //if it fails an exception is thrown |
|
Dynamic memory in ANSI-C |
operators new and delete are exclusively of C++. They are not a available in the C language. But using pure C language adn its library, dynamic memory can also be used through the functions malloc, calloc, reallocand free, which are also available in C++ |
|
exception specification |
when declaring a function we can limit the exception type it might directly or indirectly throw by appending a throw suffix to the function declaration
int myfunction (int param); // all exceptions allowed |
|
standard exceptions |
c++ standard library provides a ase class specifically designed to declare objects to be thrown as exceptions. It is called exception and is defined in hte header file under the namespace std. |
|
exception ios_base::failure |
decription |
|
example of try cat |
try { |
|
The four specific casting operator |
dynamic_cast (expression) |
|
the traditional type-casting |
(new_type) expression |
|
dynamic_cast |
dynamic_cast can be used only with pointers and references to objects. Its purpose is to ensure that the result of the type conversion is a valid complete object to the requested class.
dynamic_cast can only be used with pointers and references to classes (or with void*). Its purpose is to ensure that the result of the type conversion points to a valid complete object of the destination pointer type. |
|
virtual members def |
a member of a class that can be redefined in its derived classes is known as a virtual member. In order to declare a member of a class as virtual, we must precede its declaration with the keyword virtual. |
|
What is inherited from the base class? |
In principle, a derived cass inherits every member of a base class except: |
|
if the base class has no default constructor or you want that an overloaded consturctor is called when a new derived object is created, you can specify it in each constructor definition of the derived class |
derived_constructor_name (parameters) : base_constuctor_name (parameters) {...} |
|
Multiple inheritance |
In C++ it is perfectly possible tat a class inherits members from more than one class. This is done by simply separating the different base classes with commas in the derived class declaration. |
|
vector variable definition |
vector variable_name; |
|
salaries.push_back(s); |
push_back command resizes the vector salary by adding one element to tis end; then it sets that eleemt to s. |
|
pop_back function |
pop_back removes the last element of a vector shrinking its size by one |
|
Interfaces |
every class has a public interface: a collection of member functions through which the objects of the class can be manipulated |
|
implicit member def |
the six implicit members implicitly declared on classes under certain circumstances |
|
The move constructor and move assignment are members that take a parameter of type rvalue reference to the class itself |
MyClass (MyClass&&); // move-constructor |
|
rvalue reference |
An rvalue reference is specified by following the type with two ampersands (&&). As a parameter, an rvalue reference matches arguments of temporaries of this type. |
|
The move constructor is called |
The move constructor is called when an object is initialized on construction using an unnamed temporary. Likewise, the move assignment is called when an object is assigned the value of an unnamed temporary: |
|
Composition over inheritance |
Composition over inheritance (or Composite Reuse Principle) in object-oriented programming is a technique by which classes may achieve polymorphic behavior and code reuse by containing other classes that implement the desired functionality instead of through inheritance.[2] |
|
ADT abbr |
abstract data type |
|
UML notation |
member is public + |
|
Automatic object vs static object |
Automatic: created when the declaration is reached and destroyed when the surrounding block is exited |
|
If an object is passed by value to a function |
Contents of data members of the actual parameter are copied into the corresponding data members of the formal parameter Requires more memory |
|
If a variable is passed by reference to a function |
The formal parameter receives only the address of the actual parameter |
|
Abstract data type (ADT): |
data type that separates the logical properties from the implementation details |
|
By default, members of a struct are __________ ? |
By default, members of a struct are public |
|
constructor with default parameter |
class rectangleType { |
|
if a class objects is passed by value, the contents of the member variables of the actual parameter are _______________ |
if a class objects is passed by value, the contents of the member variables of the actual parameter are copied into the corresponding member variables of the formal parameter |
|
an efficient way to pass a variable as a parameter is by _____________ |
an efficitn way to pass a variable as a parameter is by reference |
|
How can you in C++ pass variable by reference and still prevent the function from changing its value |
by using the const keyword |
|
there is a problem whenever an input with the >> operator is followed by a call to getline. How to handle it with code? |
cin >> readme; |
|
Consider again the variation of the Employee class with work hour fields of type Time. There |
Before the constructor code starts executing, the default constructors are automatically invoked on all data fields that are objects. In particular, the arrive and leave fields are initialized with the current time through the default constructor of the Time class. Immediately afterwards, those values are overwritten with the objects Time(arrive_hour, 0, 0) and Time(leave_hour, 0, 0). |
|
It would be more efficient to construct the arrive and leave fields with the correct values right away. That is achieved as follows with the form described |
Employee::Employee(string employee_name, double initial_salary, int arrive_hour, int leave_hour) : arrive(arrive_hour, 0, 0), leave(leave_hour, 0, 0) |
|
How to initialize pointers |
p=NULL; |
|
to deallocate dynamically created array |
delete [] ptrVar; |
|
in C++, the retunr type of a function can be a pointer |
int* testExp(...) . |
|
dynamic multidimensional array |
int *board[4] |
|
function using two dimensional array |
void fill (int **p, int rowSize, int columnSize) |
|
For non objects type of the actual and formal parameters must match for objects type |
C++ allows the user to pass an object of a derived class to a formal parameter of the base class type |
|
pure virtual functions |
virtual void draw() = 0; |
|
abstract class |
once a class contains one or more pure virtual functions, then that class called an abstract class due to an abstract class not being a complete class, as it does not contain the definitions of certain functions, you cannot create objects of that class |
|
GENERAL SYNTAX TO OVERLOAD THE PRE-INCREMENT OPERATOR ++ AS A MEMBER FUNCTION |
Function Prototype (to be included in the definition of the class): |
|
GENERAL SYNTAX TO OVERLOAD THE PRE-INCREMENT OPERATOR ++ AS A NONMEMBER FUNCTION |
Function Prototype (to be included in the definition of the class): |
|
GENERAL SYNTAX TO OVERLOAD THE POST-INCREMENT OPERATOR ++ AS A MEMBER FUNCTION |
Function Prototype (to be included in the definition of the class): //the value of the object } |
|
GENERAL SYNTAX TO OVERLOAD THE POST-INCREMENT OPERATOR ++ AS A NONMEMBER FUNCTION |
Function Prototype (to be included in the definition of the class): |
|
operators that cannot be overloaded |
. |
|
sometimes it is necessary for a member function to refer to the object as a whole, rather than the object's individual member variable. This is done via |
this every object of a class type contains a pointer to itself and the name of the pointer is this |
|
friend function |
friend function of a class is a nonmember function of the class but has access to all of the members . |
|
the function that overloads any of the operator (), [], ->, or = for a class must be declared as a ...? |
member function of the class |
|
functions that overload << and >> must be ...? |
friend functions of the class |
|
if # is a binary operator the name of the function to overload is operator# |
the expression myObj # yourObj is translated to myObje.opertor#(yourObj) |
|
when overriding relational operators what I the return type of the function |
bool |
|
if # represents the binary operator that is to be overloaded as nonmember function of the class rectangleType the operation |
operator#(myRec,yourRec) |
|
GENERAL SYNTAX TO OVERLOAD THE BINARY (ARITHMETIC OR RELATIONAL) |
Function Prototype (to be included in the definition of the class): |
|
GENERAL SYNTAX TO OVERLOAD THE BINARY (ARITHMETIC OR RELATIONAL) |
Function Prototype (to be included in the definition of the class): |
|
GENERAL SYNTAX TO OVERLOAD THE PRE-INCREMENT OPERATOR ++ AS A MEMBER FUNCTION |
Function Prototype (to be included in the definition of the class): |
|
GENERAL SYNTAX TO OVERLOAD THE PRE-INCREMENT OPERATOR ++ AS A NONMEMBER FUNCTION |
Function Prototype (to be included in the definition of the class): className operator++(className& incObj){ |
|
GENERAL SYNTAX TO OVERLOAD THE POST-INCREMENT OPERATOR ++ AS A MEMBER FUNCTION |
Function Prototype (to be included in the definition of the class): |
|
GENERAL SYNTAX TO OVERLOAD THE POST-INCREMENT OPERATOR ++ AS A NONMEMBER FUNCTION |
Function Prototype (to be included in the definition of the class): |
|
what() function |
part of the class exception |
|
two classes immediately derived from the class exception |
logic_error and |
|
class invalid_argument (exceptions) |
is designed to deal with illegal arguments used in |
|
class out_of_range |
deals with the string subscript out of range error. If a length greater than the maximum allowed for a string object is used, the class length_error deals with this error |
|
class runtime_error def |
is designed to deal with errors that can be detected only during program execution. For example, to deal with arithmetic overflow and underflow exceptions, the classes overflow_error and underflow_error are derived from the class runtime_error. |
|
Using user-defined exception class divisionByZero with default error message |
#include "divisionByZero.h" |
|
the following function specifies that it throws exceptions of type int, string, and divisionByZero, in which divisionByZero is the class, as defined previously. |
void expThrowExcep(int x) throw (int, string, divisionByZero) { |
|
member access operator scope resolution operator |
member access - .
scope resolution - :: |
|
int x = 25; |
46 |
|
int x = 33; |
33 |
|
In the ____ sort, if list[index] is greater than list[index +1], then the elements list[index] |
B bubble |
|
The code for the bubble sort function requires ____. |
C two for loops and an if statement inside the second loop |
|
The binary search algorithm finds the middle element using which of the following formulas? |
D mid = (first+last)/2 |
|
The first step in the binary search is to compare the search item with the element in ____ of the list. |
C the middle |
|
In general, if L is a sorted list of size n, to determine whether an element x is in L, the binary search makes at most ____ key comparisons. |
D 2 * log2n + 2 or in more general sense O(log(n)) |
|
Which statement creates the vector object, vecList, of size n and initializes using n copies of the element elem? |
C vector < elemType > vecList(n, elem); |
|
a struct is a ____ data structure. |
C heterogeneous |
|
In C++, the ____ symbol is an operator, called the member access operator. d. $ (dollar sign) |
b . |
|
Which of the following is an allowable aggregate operation on a struct? b. Assignment |
B Assignment |
|
A ____ sign in front of a member name on the UML diagram indicates that this member is a public member. b. - |
A + |
|
A ____ sign in front of a member name on the UML diagram indicates that this member is a private member. |
B - |
|
A ____ sign in front of a member name on the UML diagram indicates that this member is a protected member. |
C # |
|
What does ADT stand for? b. asynchronous data transfer |
C abstract data type |
|
Insertion sort |
Insertion sort is good only for sorting small arrays (usually less than 100 items). In fact, the smaller the array, the faster insertion sort is compared to any other sorting algorithm. However, being an O(n^2) algorithm, it becomes very slow very quick when the size of the array increases. It was used in the tests with arrays of size 100. |
|
Shell sort |
Shell sort is a rather curious algorithm, quite different from other fast sorting algorithms. It's actually so different that it even isn't an O(nlogn) algorithm like the others, but instead it's something between O(nlog2n) and O(n1.5) depending on implementation details. Given that it's an in-place non-recursive algorithm and it compares very well to the other algorithms, shell sort is a very good alternative to consider. |
|
person a("Bjarne Stroustrup", 60); |
person a("Bjarne Stroustrup", 60); |
|
Some resources cannot or should not be copied, such as file handles or mutexes. In that case, simply declare the copy constructor and copy assignment operator as private without giving a definition: |
private: person(const person& that) = delete; |
|
The rule of three |
Sometimes you need to implement a class that manages a resource. (Never manage multiple resources in a single class, this will only lead to pain.) In that case, remember the rule of three: |
|
selection sort notes |
selection sort is a combination of searching and sorting. |
|
// Selection Sort Function for Descending Order |
void SelectionSort(apvector &num) { |
|
insertion sort algorithm c++ |
Insertion sort algorithm removes an element from the sorting list, and placing it into the correct position in the already sorted part of the list, until no input elements left. |
|
insertion sort algorithm c++ complexity |
best - if the list already sorted then it is the best case O(n) - linear |
|
the big three |
If you need to explicitly declare either the destructor, copy constructor or copy assignment operator yourself, you probably need to explicitly declare all three of them. |
|
The Rule of Four (and a half) |
The next version of C++, C++11, makes one very important change to how we manage resources: the Rule of Three is now The Rule of Four (and a half). Why? Because not only do we need to be able to copy-construct our resource, we need to move-construct it as well. |
|
Since a copy constructor
and an = operator overload
have pretty much the same code, the same parameter, and only differ on the return, is it possible to have a common function for them both to use? |
Yes. There are two common options.
One - which I don't recommend - is to call the operator= from the copy constructor explicitly:
or even: |
|
The copy constructor exists to make copies. In theory when you write a line like: |
The compiler would have to call the copy constructor to copy the return of foo() into c. |
|
Stream variables (for example, ifstream and ofstream) should be passed by ______________ |
Reference |
|
Consider the accompanying definition of the recursive function mystery below. |
c |
|
Forward manner linked list
|
Forward manner |
|
The basic operations of a linked list are as follows |
The basic operations of a linked list are as follows: search the list to determine whether a particular item is in the list, insert an item in the list, and delete an item from the list. |
|
What is the output of the following code? |
c |
|
What is the output of the following code? |
d |
|
Traversing a Linked List |
current = head; |
|
code to print out the data stored in each node |
current = head; } |
|
code to set the data in the 5th node to be 10 |
current = head; |
|
The basic sequential search algorithm can be improved in a number of ways |
One of those ways is to assume that the item being searched for will always be in the list. This way you can avoid the two termination conditions in the loop in favor of only one. Of course, that creates the problem of a failed search. If we assume that the item will always be found, how can we test for failure? |
|
Bubble Sort Algorithm C++ complexity |
Worst case performance O(n^2) |
|
Which of the following classes is derived directly from the exception class? |
B: logic_error and runtime_error |
|
A catch block that has ____ is designed to catch any type of exception. (p.957) |
B: ellipses as the parameter |
|
OVERLOADING THE STREAM INSERTION OPERATOR (<<) |
Function Prototype (to be included in the definition of the class): |
|
OVERLOADING THE STREAM EXTRACTION OPERATOR (>>) |
Function Prototype (to be included in the definition of the class): |
|
GENERAL SYNTAX TO OVERLOAD THE ASSIGNMENT OPERATOR = FOR A CLASS |
Function Prototype (to be included in the definition of the class): |
|
CTS |
Common type system
Should be used for programs wirtten in any programming language targetiong a CLI implementation
CTS specifies how data types are used within the CLR and includes a set of predefiend type.
|
|
CLR |
CLR - Common Language Runtime is a standardize environment for the exevution of programs writtein in a wide range of high-level languages. |
|
MSIL def |
MSIL - Microsoft Intermediate Language.
The CLI specifies a standard intermediate language for hte virtual machine to which the high-level language source code is compuled. With the .NET Framework, this intermediate languages is referred as MSIL
|
|
JIT def |
Just-in-tine
Code in the intermediate langiage is ultimately mapped to machine code by JIT compiler when you execute a program
|
|
MFC |
MFC
for programming the graphical user interface for your Windows appl.
The MFC encapsulate the Windows API for GUI creation and control and greatly eases the process of program develpment
|
|
Special member functions |
Default constructor - C::C();
Destructor - C::~C();
Copy constructor - C::C (cosnt C&);
Copy assignment - C& operator=(cosnt C&);
Move consturctor - C::C (C&&);
Move assignment - C& operator= (C&&);
|
|
Passing Vectors by const reference |
passing a vector into a function by value is somewhat inefficient, becaue the function must make a copy of all elements.
The cost of a copy can be avoided by using a const refrente,
double average(const vector& values)
instead of
double average(vector values)
|
|
Can arrays be function return type |
No
although arrays can be function parameters, they cannot be function return types.
|
|
Passing two dimensional array as parameter |
Two-dimentsional arrays you cannot simply pass the numbers of rows and columns as parameters:
void print(const double table[][],int tab_rows,int tab_cols); //NO
void print(const double table[][TABLE_COLS},int table_rows) //ok TABLE_COLS predefined const
|
|
selection sort verbal explanation |
sethe selection sort algorithm sorts a sequence by repeatedly finding the smallest ellement of the unsorted tail region and movint it ot the front
is an O(n^2) algorithm - doubling the data set means a fourfold increase in processing time |
|
Can a funtion return a vector? |
A fucntion can return a vector. |
|
the compilation process |
preprocessor compiler linker |
|
Virtual functions can be overridden by derived classes ?Pure virtual functions must be overridden by derived classes ? |
Virtual functions can be overridden by derived classes
virtual int area() const; Pure virtual functions must be overridden by derived classesvirtual int area() const = 0; |
|
unique_ptr |
Type of smart pointer
if only one object needs acess to the underlying pointer
header file |
|
shared_prt |
Type of smart pointer
if several want to use hte smae underlying pointer
Cleaned up when the last copy goes out of scope
header file |
|
void testTime(const clockType& otherClock) causes?? |
the otherClock is passed by reference so it saves time by not copying it additionally the const make it unchangable |
|
passing vectors by constant reference |
Passing a vector into a fucntion by value is unfortunately somewhat inefficietn, because the fucntion must make a copy of all elements. The cost of a copy can be avoided by using a constant reference.
double average(const vector& values)
instead of
double average(vectorm>double> values)
This is useful optimization that greatly increases performance. |
|
int atoi(const char s[]) |
header cstdlib
Converts a character array containing digits into its integer value
char year[] = "1999"; int y = atoi(year); // now y is the integer 1999 |
|
Use the -> operator to ...? |
Use the -> operator to access a data memeber or a member function through an object pointer. |
|
Always initalize pointer variable. If you can't initialize them with the return value of new, then set the to NULL. Never use a pointer that has been deleted. It is common to immediately set every pointer to NULL after deleting it |
This delete first; first = NULL;
is not complete solution second = first; delete first; first = NULL;
|
|
to deallocate the array, you use the ..... |
delete[] operator delete[] staff; |
|
Function point |
the name of a function without () denotes a pointer
double (*f)(double) - This delcares f as pointer, so that *f is a function.
double *f(double) denotes a function f (and not a function pointer) that consumes a double and returns a double* pointer. |
|
double read_data(istream in); will fail why? |
It will fail due to missing &
double read_data(istream& in); |
|
Why should we pass istream& as param for functions instead of ifstream& |
if you use istream& you can pass parameters of types other than ifstream, such as cin |
|
one-character lookahead |
if you read a char and you regretted it, you can unget it, so that the next input operation can read it again. You can unget only one character at a time
char ch; input_data.get(ch); if ('0' <= ch && ch <= '9' ) { input_data.unget(); //did not want to read it int n; input_Data >> n; } |
|
you can sort a vector v by calling |
sort(v.begin(), v.end());
v.begin(), v.end() are iterators that denote the beginning and ending postiion of the vector |
|
converting an integer into a sting using streams |
string int_to_string(int n) { ostringstream outstr; outstr << n; return outstr.str(); } |
|
converting string to int via streams |
int string_to_int(string s) { istringstream instr(s) int n; instr >> nl return n; } |
|
constructor mutator accessor |
A constructor is used to initialize objects when they are created. A constructor with no parameters is called a default constructor. A mutator member function changes the state of the object on which it operates. An accessor member function does not modify the object. Accessors must be tagged with const. |
|
const correctness |
You should declare all accessor functions in C++ with the const keyword |
|
Calling Constructors from Constructors |
There is an unfortunate inefficiency in the constructor: Employee::Employee(string employee_name, double initial_salary, int arrive_hour, int leave_hour) { name = employee_name; salary = initial_salary; arrive = Time(arrive_hour, 0, 0); leave = Time(leave_hour, 0, 0); } Before the constructor code starts executing, the default constructors are automatically invoked on all data fields that are objects. In particular, the arrive and leave fields are initialized with the current time through the default constructor of the Time class. Immediately afterwards, those values are overwritten with the objects Time(arrive_hour, 0, 0) and Time(leave_hour, 0, 0). It would be more efficient to construct the arrive and leave fields with the correct values right away. Employee::Employee(string employee_name, double initial_salary, int arrive_hour, int leave_hour) : arrive(arrive_hour, 0, 0), leave(leave_hour, 0, 0) { name = employee_name; salary = initial_salary; } Many people find this syntax confusing, and you may prefer not to use it. The price you pay is inefficient initialization, first with the default constructor, and then with the actual initial |
|
WPF, MFC, DirectX |
Windows (desktop) applications -WPF, MFC, DirectX |
|
C++/CX |
Windows Store apps -C++/CX |
|
C++ REST SDK |
* Windows Phone apps - C++ REST SDK |
|
standard header |
The properties of fundamental types in a particular system and compiler implementation can be obtained by using the numeric_limits classes (see standard header ). If for some reason, types of specific sizes are needed, the library defines certain fixed-size type aliases in header . |
|
c-like initialization |
consists of appending an equal sign followed by the value to which the variable is initialized:
type identifier = initial_value; int x = 0;
|
|
constructor initialization (introduced by the C++ language) |
constructor initialization (introduced by the C++ language), encloses the initial value between parentheses (()):
type identifier (initial_value); For example: int x (0); |
|
uniform initialization |
uniform initialization, similar to the above, but using curly braces ({}) instead of parentheses (this was introduced by the revision of the C++ standard, in 2011):
type identifier {initial_value}; For example:
int x {0};
|
|
auto and decltype |
When a new variable is initialized, the compiler can figure out what the type of the variable is automatically by the initializer. For this, it suffices to use auto as the type specifier for the variable:
int foo = 0; auto bar = foo; // the same as: int bar = foo;
Here, bar is declared as having an auto type; therefore, the type of bar is the type of the value used to initialize it: in this case it uses the type of foo, which is int. |
|
Variables that are not initialized can also make use of type deduction with the decltype specifier: |
int foo = 0; decltype(foo) bar; // the same as: int bar;
Here, bar is declared as having the same type as foo. |
|
auto and decltype |
auto and decltype are powerful features recently added to the language. But the type deduction features they introduce are meant to be used either when the type cannot be obtained by other means or when using it improves code readability. The two examples above were likely neither of these use cases. In fact they probably decreased readability, since, when reading the code, one has to search for the type of foo to actually know the type of bar. |
|
Prefix u U L |
Character type
u char16_t U char32_t L wchar_t |
|
The for-loop has another syntax, which is used exclusively with ranges:
for ( declaration : range ) statement; |
This kind of for loop iterates over all the elements in range, where declaration declares some variable able to take the value of an element in this range. Ranges are sequences of elements, including arrays, containers, and any other type supporting the functions begin and end; Most of these types have not yet been introduced in this tutorial, but we are already acquainted with at least one kind of range: strings, which are sequences of characters.
An example of range-based for loop using strings: // range-based for loop #include #include using namespace std;
int main () { string str {"Hello!"}; for (char c : str) { std::cout << "[" << c << "]"; } std::cout << '\n'; } [H][e][l][l][o][!]
Note how what precedes the colon (:) in the for loop is the declaration of a char variable (the elements in a string are of type char). We then use this variable, c, in the statement block to represent the value of each of the elements in the range. |
|
Arguments by reference do not require a copy. The function operates directly on (aliases of) the strings passed as arguments, and, at most, it might mean the transfer of certain pointers to the function. In this regard, the version of concatenate taking references is more efficient than the version taking values, since it does not need to copy expensive-to-copy strings.
On the flip side, functions with reference parameters are generally perceived as functions that modify the arguments passed, because that is why reference parameters are actually for.
The solution is for the function to guarantee that its reference parameters are not going to be modified by this function. This can be done by qualifying the parameters as constant: |
string concatenate (const string& a, const string& b) { return a+b; }
|
|
Inline functions |
Calling a function generally causes a certain overhead (stacking arguments, jumps, etc...), and thus for very short functions, it may be more efficient to simply insert the code of the function where it is called, instead of performing the process of formally calling a function.
Preceding a function declaration with the inline specifier informs the compiler that inline expansion is preferred over the usual function call mechanism for a specific function. This does not change at all the behavior of a function, but is merely used to suggest the compiler that the code generated by the function body shall be inserted at each point the function is called, instead of being invoked with a regular function call. |
|
In C++, functions can also have optional parameters |
In C++, functions can also have optional parameters, for which no arguments are required in the call, in such a way that, for example, a function with three parameters may be called with only two. For this, the function shall include a default value for its last parameter, which is used by the function when called with fewer arguments. For example:
// default values in functions #include using namespace std;
int divide (int a, int b=2) { int r; r=a/b; return (r); }
int main () { cout << divide (12) << '\n'; cout << divide (20,4) << '\n'; return 0; }
In this example, there are two calls to function divide. In the first one: divide (12) The call only passes one argument to the function, even though the function has two parameters. In this case, the function assumes the second parameter to be 2 (notice the function definition, which declares its second parameter as int b=2). Therefore, the result is 6. |
|
The function sum could be overloaded for a lot of types, and it could make sense for all of them to have the same body. For cases such as this, C++ has the ability to define functions with generic types, known as function templates. Defining a function template follows the same syntax than a regular function, except that it is preceded by the template keyword and a series of template parameters enclosed in angle-brackets <>: |
emplate function-declaration The template parameters are a series of parameters separated by commas. These parameters can be generic template types by specifying either the class or typename keyword followed by an identifier. This identifier can then be used in the function declaration as if it was a regular type. For example, a generic sum function could be defined as: template SomeType sum (SomeType a, SomeType b) { return a+b; }
|
|
Instantiating a template |
Instantiating a template is applying the template to create a function using particular types or values for its template parameters. This is done by calling the function template, with the same syntax as calling a regular function, but specifying the template arguments enclosed in angle brackets:
name (function-arguments) For example, the sum function template defined above can be called with:
x = sum(10,20);
|
|
Essentially, these are the four possible combinations of the dereference operator with both the prefix and suffix versions of the increment operator (the same being applicable also to the decrement operator): |
*p++ // same as *(p++): increment pointer, and dereference unincremented address *++p // same as *(++p): increment pointer, and dereference incremented address ++*p // same as ++(*p): dereference pointer, and increment the value it points to (*p)++ // dereference pointer, and post-increment the value it points to |
|
Pointers and const |
Pointers can be used to access a variable by its address, and this access may include modifying the value pointed. But it is also possible to declare pointers that can access the pointed value to read it, but not to modify it. For this, it is enough with qualifying the type pointed by the pointer as const. For example: int x; int y = 10; const int * p = &y; x = *p; // ok: reading p *p = x; // error: modifying p, which is const-qualified
|
|
Pointers can also be themselves const. And this is specified by appending const to the pointed type (after the asterisk): |
int x; int * p1 = &x; // non-const pointer to non-const int const int * p2 = &x; // non-const pointer to const int int * const p3 = &x; // const pointer to non-const int const int * const p4 = &x; // const pointer to const int
|
|
Both expressions have a value of 'o' (the fifth element of the array |
*(foo+4); foo[4];
|
|
p++ = *q++; |
p++ = *q++;
Because ++ has a higher precedence than *, both p and q are incremented, but because both increment operators (++) are used as postfix and not prefix, the value assigned to *p is *q before both p and q are incremented. And then both are incremented. It would be roughly equivalent to: |
|
C++ allows operations with pointers to functions. The typical use of this is for passing a function as an argument to another function. Pointers to functions are declared with the same syntax as a regular function declaration, except that the name of the function is enclosed between parentheses () and an asterisk (*) is inserted before the name: |
// pointer to functions #include using namespace std;
int addition (int a, int b) { return (a+b); }
int subtraction (int a, int b) { return (a-b); }
int operation (int x, int y, int (*functocall)(int,int)) { int g; g = (*functocall)(x,y); return (g); }
int main () { int m,n; int (*minus)(int,int) = subtraction;
m = operation (7, 5, addition); n = operation (20, m, minus); cout < return 0; } |
|
The other method is known as nothrow |
The other method is known as nothrow, and what happens when it is used is that when a memory allocation fails, instead of throwing a bad_alloc exception or terminating the program, the pointer returned by new is a null pointer, and the program continues its execution normally.
This method can be specified by using a special object called nothrow, declared in header , as argument for new:
foo = new (nothrow) int [5];
In this case, if the allocation of this block of memory fails, the failure can be detected by checking if foo is a null pointer:
int * foo; foo = new (nothrow) int [5]; if (foo == nullptr) { // error assigning memory. Take measures. }
|
|
C++ integrates the operators new and delete for allocating dynamic memory. But... |
C++ integrates the operators new and delete for allocating dynamic memory. But these were not available in the C language; instead, it used a library solution, with the functions malloc, calloc, realloc and free, defined in the header (known as in C). The functions are also available in C++ and can also be used to allocate and deallocate dynamic memory. |
|
The arrow operator (->) |
The arrow operator (->) is a dereference operator that is used exclusively with pointers to objects that have members. This operator serves to access the member of an object directly from its address. For example, in the example above:
pmovie->title
is, for all purposes, equivalent to:
(*pmovie).title
|
|
Nesting structures |
tructures can also be nested in such a way that an element of a structure is itself another structure:
struct movies_t { string title; int year; };
struct friends_t { string name; string email; movies_t favorite_movie; } charlie, maria;
friends_t * pfriends = &charlie;
After the previous declarations, all of the following expressions would be valid:
charlie.name maria.favorite_movie.title charlie.favorite_movie.year pfriends->favorite_movie.year
(where, by the way, the last two expressions refer to the same member). |
|
Type aliases (typedef / using) |
A type alias is a different name by which a type can be identified. In C++, any valid type can be aliased so that it can be referred to with a different identifier.
In C++, there are two syntaxes for creating such type aliases: The first, inherited from the C language, uses the typedef keyword:
typedef existing_type new_type_name ;
where existing_type is any type, either fundamental or compound, and new_type_name is an identifier with the new name given to the type.
For example: typedef char C; typedef unsigned int WORD; typedef char * pChar; typedef char field [50];
This defines four type aliases: C, WORD, pChar, and field as char, unsigned int, char* and char[50], respectively. |
|
How you get a function pointer in C++? |
by writing the function name without the () double square(double x) { return x*x; } ... print_table(square);
void print_table(DoubleFunPointer f) { cout << setprecesion(2); for (double x = 1; x<= 10; x++) { double y = f(x); cout << setw(10) << "|" << setw(10) << y < } } |
|
Use ypedef to make function poitner types easier to read. |
void print_Table(double (*f)(double))
typedef double(*DoubleFunPointer)(double); void print_table(DoubleFunPointer f); |
|
setfill |
sets the fill character for padding a field (the defauls character is a space) out << setfill('0') << setw(6) << 123; // 000123 |
|
hex dec |
out << hex << 123; //7b out << dec << 123; //7b |
|
istringstream class ostringstream class |
istringstream class - read characters from a string ostringstream class - rights characters to a string
string inpu = "January 23, 1995"; istringsteam instr(input); string month; int day; string coma; string year;
instr >> month >> day >> comma >> year; |
|
Naming lambda expression |
you can assign a statless lambda - one that does not reference anything in an external scope to a variable that is a function pointer, thus giving the lambda a name, You can use the funct pointer to call the lambda
atuo sum = [](int a, int b) {retur a+b;};
cout << "5+10 equal " << sum(5, 10) << endl; cout << "15+10 equal " << sum(15, 10) << endl; |
|
function <> template |
an extension to the STL fucntional header defines the function<> class template that you can use to define a wrapper for a function object. The function<> template is referred to as a polymorphic function wrapper because an instance of the template can wrap a variaty of function obj |
|
templates and lambda expressions |
you can use a lambda expression inside a tempalte.
template T average(const vector& vec) { static_assert(std::is_arithmetic::value, "Type parameter for average() must be arithmetic."); T sum(0); std::for_each(vec.begin(), vec.end(), [∑](const T& value) {sum += value; }); retrun sum/vec.size(); } }
|
|
Insertion in linked list p points to the node after the second a new node to be inserted after p node |
newNode = new nodeType; newNode->info = 50; newNode->link = p->link; p->link = newNode; |
|
Pointer to a struct |
struct ListElement { RECT aRect; ListElement* pNext; }; |
|
Defaukt parameter values |
you can specify default vales for the parameters to a function in the function prototype. If you put the definition of the member function inside the class, you can put the defaul values for the parametes in the function header.
class CBox {
CBox (double lv = 1.0, double bv = 1.0, double hv = 1.0) { .. }
} |
|
Using an initializaion list in a constructor |
you can initialize hte members of an object in the class consturctos using explicit assignments. You can also have used a different technicque called an intializtion list.
//CBox class CBox {
CBox (double lv = 1.0, double bv = 1.0, double hv = 1.0) { .. }
}
NEEEDS to be in a CLASS |
|
Making a Constructor Explicit |
if you define a cosnturctor with a single parameter the compule will use this consturcto for implicit conversions, which may not be what is needed. If you do not want for this to happen add the keyword explicit to the definition of hte constructor
explicit CBox( double side): m_lenght(side), m_width(side), m_height(side) {}
With the constructor declared as explicit, it will onle be called when it is explicitly invoked and will nto be used for implicit conversion |
|
Implicit conversion when there are default parameters in the constructor |
if the constructor is CBox (double lv = 1, double bv =1, double hv =1): m_lenght(lv), m_width(bv), m_height(hv) { cout << nedl << "Constructor called."; }
because there are defualt values for the second and third parametersm the following statements will compile: CBox box; box = 99;
This time, you will get an impilict call to the previous version of the constuctors with the first argument vlaue as 99, and the other arguments with defualt values. This is unlikely to be what you want. To prevent this, make the consturctor explicit: explicit CBox (double lv = 1, double bv =1, double hv =1): m_lenght(lv), m_width(bv), m_height(hv) { cout << nedl << "Constructor called."; } |
|
frind function |
//in class friend double BoxSurface(const Cbox& aBox);
//definition double BoxSurface(const Cbox& aBox) {
} |
|
pointers to objects |
CBox* pBox(nullptr); //Declare a pointer to CBox pBix = &cigar; // Sotres address of CBox object cigar in pBox cout << pBox->Volume(); // Display volume of object pinter to by pBox |
|
int fillarr(int arr[])
is equivalent to |
int fillarr(int *arr) |
|
Return from yur function a pinter to the first eleemtn of an array |
int* fillarr(int arr[]) { int y[10]; int *a = fullarr(y); count << a[0] << endl; } |
|
the function call operator and overloading it |
the funtion call operator is ()
the overload for this operator is operator()() |
|
here is a class that overload the function call operator |
class Area { public: int operaotr()(int lenght, int width) { return lenght*width;} }; |
|
adding global functions |
you migth think that you put definitions for inline functions in a .cpp file (like other func definitions) the definitions for inline fonc need to be available when a file containing calls to the is compiled (other wise you get a linker error) If you call an inline function in a .cpp file the inline function definition must appear in an .h file that is included in the cpp.file |
|
getline(cin, sentence, '*'); |
this template func is for reading data from stream into a string or wstring obj. The first arg is the stream that is the source The second arg is the object to receive the input The third arg is the character that terminates the input |
|
find_last_of(char ch, size_t offset=0) |
searches a string obj for the first occurrence of any character in the string, str, starting at position offset |
|
find_first_of(char ch, size_t offset=0) |
searches a string obj for the first occurrence of the character, ch, starting at position offset, and returns the index position where the character is found as value of type size_t |
|
if you write any kind of constructor for a derived class you are responsible for... |
for the initialization of all members fo the derived class object, including all its inherited members |
|
preventig class derivationcircumstances can arise where yo uwant |
to be sure that your class cannot be used as a base class
class CBox final {
}; |
|
casting between class type |
CContainer* pContainer = new CGlassBox(2.0, 3.0, 4.0); CBox* pBox = dynamic_cast(pContainer); CGlassBox* pGlassBox = dynamic_cast( pContainer);
The first statement stores the address of the CGlassBox obj created on the heap in a base class pointer of type CContainer*. The second statement casts pContainer up the class hierarchy to type CBox*. The third statemetn casts the address in pContainer to its actual type, CGlassBox*. |
|
It's a good idea to declare your base class destuctor as virtual... |
Using virtual destructors ensures that your objects will be properly destroyed and avoids potential progrma crashes that might otherwise occur. |
|
header file deque |
a deque container implements a double ended queue of elemetns of type T. This is equivalent to a vector with the capability of adding elements to the beginning efficiently |
|
header file list |
a list coinert is a doubly-linked list of elemetns of type T |
|
header file forward_list |
a forward_list container is a singly linked list of elelemts of type T. Inserting and deleting eleemnts in a forwar_list will be faster than in a list as long as you are processint the elements in a forwar direction.
Random access will be slower for forward_list than for a list |
|
header file map |
a map is an associative container that stores each object (of type T) with an associated key (of type K). Key/object pairs are stored in the map as objects of type pair which is another STL template type. The key determines where the key/object pair is located and is used to retrieve an obejct. Each key must be unique.
|
|
heaer file unordered_map |
An unordered_map container is similar to a map, except that the key/object pairs are in no particular order in the container |
|
header file hash_map |
hash_map container stores key/object pairs that have unique keys. Pairs are grouped into buckets based on has values produced from keys. |
|
header file set |
A set container is a map where each element server as its own key. All elemetns in a set must be unique. A consequence of using an object as its own key is that you cannot change an object in a set; to change an object you must delete it and the insert the modifeid verions. The lements in the container are oredered in ascending seuqnce. |
|
header file unordered_set |
an unordered_set contianer is similar to a set except that the elements are not ordered in any particular way |
|
header file bitset |
defines the bitset class tempalte that represnete a fixed number of bits. This is typically used to store flags that represent a set of state or conditions |
|
allocators |
Most of the STL containers grow their capacity automatically to fit new obj in our sotre. Additional memory for these contianers is made available by an object called an allocat that typically allocates spce on the heap when required You can optionally supply your own allocator obj type via an additional parameter the vector template for creating a vector is really a vector> template and A is hte allocator type |
|
Comprators |
Some contianers usea comparator object that is used to determine the order of elements within the contianer. map>K,T> container is really map, A>> |
|
STL defines container adapter |
this is a tempalte class that wraps an existing STL contianer class to provide a different, and typically more restricted, capability. |
|
List hte container adapters |
queue stack |
|
Iterator |
this are objects that behave like pointers and are very important for accessint the contents of all STL containers |
|
Iterator categories |
Four Input and output iterator Forward Iterator Biderectional iterator Random access iterator |
|
Input and outout iterators |
These iterators read or write a sequnce of objects and may onlybe used once. To read or write a second time, you must obtain a new iterator. |
|
Forward iteraors |
Forward iterators incprporate the capabilities of both input and output iterators, so you can apply the operations show for the previous category to them, and you can use them for access and store operations. Forwar iterators can also be reused to traverse a set of objects in a forward direction as many times as you want |
|
Biderectional iterator |
Bidirectional iterators provide the same capabilites as forward iterators and additionally allow the operations --iter and iter--. This means you can traverse backward as well as forward through a sequence of objects. |
|
Random access iterator |
Random access iterators have the same capabiliteis as bidirectional iterators |
|
reverse iterators |
the3 iterators returned by rbegin() and rend() are called reverse iterator because they are of type vector::reverse_iterator |
|
How can you create a vector containing the contents of anoher vector in reverse order |
double data[] = {1.5,2.5,3.5,4.5}; vector mydata(data, data+4); vector values(mydata.rbegin(), mydate.rend()); |
|
clear() function for a list
remove() function fro alist |
clear() - deletes all the elements from a list
remove() - removes the elements from a list that match a particular valie
|
|
int data[] = {10,22,4,56,89,77,13,9}; list numbers(begin(data), end(data)); number.assign(10, 99); // replace contents by 10 copies of 99 numbers.assign(data+1,data+4); // Replace contents by 22 4 56 |
the assign() funtions comes in the two oveloaded version illustrated here. The arguments to the first are teh count of the number of replacements eleemtns, and the replacement element value |
|
unique() function |
unique() function will eliminate adjacent duplicate elements from a list, so if you sort the contents first, applying teh function esures that all elemetns are unique. |
|
You have Empoyee* boss = ...; raise_salary(*boss,10); You want to find out the name of the employee to which boss points. There is a method get name |
string name = *boss.get_name(); //error dot has higher precedence that *
string name = *(boss.get_name()); //error boss is a pointer not an object
string name = (*boss).get_name(); // ok string name = boss->get_name(); // ok |
|
Set reference to NULL and check if reference is null |
Employee* boss = NULL; // will set later ... if (boss != NULL ) name = boss->get_name(); //ol |
|
The sting class has a constructor _______ that you can use to convert any character pointer or array to a safe and convinient string obj |
string(char *)
|
|
char *p(); strcpy(p, "Harry");
What is wrong with this syntax? |
This is not a syntax error. The srcpy func exprect two char pointers. However the sting "Harry" is copied to a pointer p that is not allocated to hold memory. |
|
basic_isstringstream template |
sstream header defines the tempalte basic_isstringstream tempalte that defines na obj type that can access data from a stream buffere.
string data("2.4 2.5 3.6 2.1"); istringstream input(data); istream_iterator begin(input) end; coutn << "The sum is"" << accumulate(begin, end, 0,0) << endl; |
|
an inserter iterator can add new elements to the sequenec containers vector, deque, and list. There are three templates that create inserter iterators defined in the iterator header |
back_insert_iterator - inserts elements at the end of a container of type T
front_insert_iterator - inserts elements at the beginning of a container of type T
insert_iterator - inserts elements starting at a specified position within a container of type T |
|
code to create an iterator that can insert data at the beginning of the list container numbers |
list numbers; front_insert_iterator> iter(numbers); *iter = 99; //insert 99 at the front of the numbers container |
|
you can use a lambda expression inside a tempalte te |
template T average(const& vec) { static_assert(std::is_arithmetic::value, "Type parameter for average() mist be arithmetic."); T sum(0); std::for_each(vec.begin(), vec.end(), (∑)(const T& value) {sum += value; )}; return sum/ver.size(); } |
|
Naming a lambda expression |
you can assign stateless lambda - one that does not reference anything in an external scope - to a variable that is a function pointer, this giving the lambda a name.
auto sum = P{(int a, int b{ return a+b;};
the function pointer, sum points to the lambda expression so you can use it
count <"5 + 10" << sum(5,1) << endl; |
|
There are two key requirments to make sure that the recursion is successfull |
1) Every recursive call must simplify the computation in some way 2) There must be special cases to handle the simplest computation directly |
|
you have
second = first; ... delete first; first = NULL;
what happens with second |
second becomes a dangling operator |
|
The array/pointer duality law states |
The array/pointer duality law states taht a[n] is identical to *(a+n) where a is a pinter into an array and n is an inter offset |
|
returning a pointer to a local array like this is....
double* minmax(const double a[], int a_size) { assert(a_size>0); double result[2]; result[0] = 0; result[1] = 0;
for (int i = 0;i < a_size; i++ ) { if (a[i] < result[0]) result[0] = a[i]; if (a[i] > result[0]) result[0] = a[i]; } return result; }
|
Wrong the result array is declared in the functions so once the fucntion finishes the space is releases. Workaroud have the function retunr a vector of
vector minmax(const double a[], int a_size) |
|
recursive helper function |
sometimes it is easier to find a recursive solution if you change the orginal problem. Then the original problem can be solved by calling a recursive helper func. Typical example - palindrome test. |
|
f(n) = O(g(n)) means |
that f grows no faster than |
|
In many Windwos programs, variable names have a prefix, which indicates what kind of value the variable holds and how it is used b by c dw fn h i l lp n p s sz w |
b - a Bool by - type unsigned char; a byte c - type char dw - type WORD (unsingned long) fn - a function h - a handle, used to reference i - type int l - type long lp - long pointer n - type unsinger int p - a pointer s - a string sz - zero terminated string w - type WORD, unsigned short |
|
binary search full code |
int binary_search(vector v, int from, int to, int value) { if ( from > to ) return -1; int mid = (from+to)/2;
if (v[mid]==value) return mid; else if (v[mid] < value) return binary_search(v, mid+1, to, value); else return binary_search(v, from, mid-1, value); } |
|
v.begin() and v.end() are |
iterators that dneote the beginning and ending position of the vector
sort(v.begin(), v.end()); |
|
primary use for the decltype operator is in deifnint function templates. The return type of a template function with muliple type paramerter may depend on the types used to instanitate the template |
template return_type f(T1 v1[], T2 v2[], const size_t& count) { decltype (v1[0]*v2[0]) sum (0); for(size_t i = 0; < count; i++) sum +=vi[i]*v2[i]; return sum; }
return_type needs to be the type of the resut lof multiplying corresponding elements of the array arguments. |
|
Accepting a Variable Number of Function Arguments
You can defi ne a function so that it allows any number of arguments to be passed to it. You indicate that a variable number of arguments can be supplied by placing an |
... ellipsis
int sumValues(int first,...) |
|
Returning a Reference |
You can also return an lvalue reference from a function. This is fraught with potential errors because an lvalue reference has no existence in its own right (it’s always an alias for something else), you must be sure that the object that it refers to still exists after the function completes execution
double& lowest(double values[], const int& length); // Function prototype |
|
Using an Initialization List in a Constructor |
// Constructor definition using an initialization list
The way this constructor defi nition is written assumes that it appears within the body of the class defi nition. The values of the data members are not set in assignment statements in the body of the constructor. As in a declaration, they are specifi ed as initializing values using functional notation and appear in the initializing list as part of the function header
This is more efficient initialized the members of an object in the class constructor using explicit assignments |
|
Making a Constructor Explicit |
If you define a constructor with a single parameter, the compiler will use this constructor for implicit conversions. For example, if we define a constructor
the following code fragment:
you can use the explicit keyword in the defi nition of the constructor to prevent it:
With the constructor declared as explicit, it will only be called when it is explicitly invoked, and |
|
Draw the graph showing memory allocation for the code
{ Employee* boss; boss = new Employee(...); //Memory for employee allocated on the heap .. deleted boss;// memory for employee manually reclaimed }
|
|
|
An accessor member function does not modify the object. Accessor must be tagged with |
Accessor must be tagged with const |
|
Calling Constructors from Constructors |
Consider again the variation of the Employee class with work hour fields of type Time. There is an unfortunate inefficiency in the constructor: Employee::Employee(string employee_name, double initial_salary, int arrive_hour, int leave_hour) { name = employee_name; salary = initial_salary; arrive = Time(arrive_hour, 0, 0); leave = Time(leave_hour, 0, 0); } Before the constructor code starts executing, the default constructors are automatically invoked on all data fields that are objects. In particular, the arrive and leave fields are initialized with the current time through the default constructor of the Time class. Immediately afterwards, those values are overwritten with the objects Time(arrive_hour, 0, 0) and Time(leave_hour, 0, 0). It would be more efficient to construct the arrive and leave fields with the correct values right away. That is achieved as follows with the form described in Syntax 5.4. Employee::Employee(string employee_name, double initial_salary, int arrive_hour, int leave_hour) : arrive(arrive_hour, 0, 0), leave(leave_hour, 0, 0) { name = employee_name; salary = initial_salary; } Many people find this syntax confusing, and you may prefer not to use it. The price you pay is inefficient initialization, first with the default constructor, and then with the actual initial |
|
To teach the compiler this new meaning of the > operator, we provide a member function called operator> as follows: |
bool Product::operator>(Product b) const { if (price == 0) return true; if (b.price == 0) return false; return score / price > b.score / b.price; } |
|
Describe the behavior?
suppose you write these statements CMessage motto1("Radiation fades you genes."); CMessage motto2(motto1); // calls the default copy constructor |
The effect of the default copy constructor will be to cope the address that is stored in the pointer member of the class from motto1 to motto2 because the copying process implemented by the default copy consturctor involves simply copying the values stored in the data members of the original object to the new object. |
|
Describe the behavior?
CMessage thought("Eye awl weigh yews my spell checker."); DisplayMessage(thought); // Call a function to output a message
Where the function DisplayMessage() is defined as: void DisplayMesasge(CMessage localMsg) { cout << endl << "The message is: "; localMsg.ShowIt();
return; } |
The problem lies with the parameter. The parameter is a CMessage object, so the argument in a call is passed by value. With the default copy constructor, the sequence of events is as follows: 1) The object thought is created with the space for the message "Eye awl weighs yews my spell checked" allocated in the free store. 2)The function DisplayMessge() is called and, because the argument is passed by value, a copy, localMsg, is made using the default copy constructor. Now, the pointer in the copy point ot the same string in the free store as the original object. 3)At the end of the function, the local object goes out of scope, so the destructor for the CMessage class is called. This deletes the local objects (the copy) by deleting the memory pointed to by the pointer pmessage; 4)On return from the function DisplayMessage(), the pointer in the original object, thought, still point to the memory are that has just been deleted. Next time you try to use the original object, your program will behave in weird. |
|
the operator keyword and creating operator functions |
you can write an operator function with or without a space between the operator keyword and the operator itself, as long as there's no ambiguity. The ambiguity arises with operators with names rather than symbols such as new or delete. If you were to write operatornew and operatordelete without a space, they are legal names for ordinary functions, so for operator functions with these operators, you must leave a space between the keyword operator and the operator name |
|
int fillarr(int arr[]) is equivalent to |
int fillarr(int* arr) |
|
You have seen that you can use a for loop to iterate over all the elements in an array. The range based for loop makes this even easier. The loop is easy to understand through an example: |
double temperatures[] = {65.5, 68.0, 75.0, 77.5, 76.4, 73.8,80.1};
This calculates the average of the values stored in the temperatures array |
|
You could also write a range based loop using the auto keyword: |
for(auto temperature : temperatures) |
|
You can also create strings that comprise Unicode characters, the characters in the string being of type ...? |
You can also create strings that comprise Unicode characters, the characters in the string being of type wchar_t. Here’s a statement that creates a Unicode string:
|
|
getline() function |
|
|
nullptr |
NOTE The reason for introducing nullptr into the C++ language was to remove |
|
_countof() to obtain the number of array elements in the loop |
Remember that pstr is an array of pointers — using the sizeof operator on the array or on individual elements will not tell us anything about the memory occupied by the text strings. pstr[0] is a pointer to a character array and thus |
|
Array of constant pointers to constants |
// Array of constant pointers to constants |
|
To summarize, you can distinguish three situations relating to const, pointers, and the objects to |
A pointer to a constant object
In the fi rst situation, the object pointed to cannot be modifi ed, but you can set the pointer to point to something else:
In the second, the address stored in the pointer can’t be changed, but the object pointed to can be:
Finally, in the third situation, both the pointer and the object pointed to have been defi ned as constant and, therefore, neither can be changed: |
|
You can use pointer notation with an array name to reference elements of the array. You can reference each element of the array beans that you declared earlier, which had three rows of four elements, in two ways: Therefore, the following two statements are equivalent |
beans[i][j] |
|
Allocating memory for an array dynamically is very straightforward. If you wanted to allocate an array of type char, assuming pstr is a pointer to char, you could write the following statement: |
pstr = new char[20]; // Allocate a string of twenty characters
delete [] pstr; // Delete array pointed to by pstr |
|
using references |
There are two kinds of references: lvalue references and rvalue references. Essentially, a reference is a name that can be used as an alias for something else. |
|
Declaring and Initializing Lvalue References |
Suppose that you have declared a variable as follows:
You can now use the reference in place of the original variable name. For example, this statement,
Note that you cannot write: |
|
Rvalue References |
Rvalue references are important in the context of functions
As you know, every expression in C++ is either an rvalue or an lvalue. A variable is an lvalue |
|
rvalue vs lvalue |
every expression in C++ is either an rvalue or an lvalue. A variable is an lvalue because it represents a location in memory. An rvalue is different. It represents the result of evaluating |
|
Calling constructor of base class |
|
|
Over riding a method in base class
|
|
|
Virtual destructor example |
class Base1 { |
|
A method without an implementation is called an |
abstract method
Abstract methods are often used to create an |
|
Pure virtual destructor |
Can also define a destructor as pure. class BST { But must also pro vide a function body.Why? BST::~BST() {} |
|
The standard C++ set class stores values in _______________ order |
The standard C++ set class stores values in sorted order |
|
The iterator visits the elements in __________ order, not in the order in which you _________ them. |
The iterator visits the elements in SORTED order, not in the order in which you INSERTED them. |
|
names.insert("Tom"); names.insert("Dick"); names.insert("Harry");
write the code that prints the set elements in dictionary oreder |
set::iterator pos; for (pos = names.begin(); pos!=names.end(); p++) cout << *pos << " ";
//prints Dick Harry Romeo Tom |
|
multiset def |
multiset is similar to a set, but elements can occur multiple times. |
|
In a multiset you can insert an element multiple times, the element count reflects the number of insertions. Each call to erase decrements the element count until it reaches 0. |
multiset names; names.insert("Romeo"); names.insert("Juliet"); names.insert("Romeo"); names.insert("Juliet");//names.count("Juliet") is 2 names.erase("Romeo"); //names.count("Romeo") is 0 |
|
performance of a vector, linked list, and balanced binary tree |
Vector Linked List - Balanced Binary tree Add/remove element at end O(1) - O(1) - N/A Add/remove element in the middle O(n) - O(1) - O(log(n)) Get kth element O(1) - O(k) - N/A Find value O(n) - O(n) - O(log(n)) |
|
multimap can have multiple values associated with the same key. Instead of using the [] operator, you insert and erase pairs |
multimap friends; frieds.insert(make_pair("Tom", "Dick")); // Dick is a friend for Tom frieds.insert(make_pair("Tom", "Harry")); // Harry is a friend for Tom
|
|
To enumerate all values associated with a key, you obtain two iterators that define the range containing all pairs with a given key |
multimap::iterator lower = friends.lower_bound("Tom"); multimap::iterator upper = friends.upper_bound("Tom"); |
|
iterate over the contents of a map |
map::iterator pos; for (pos = scores.begin(); pos != scores.end(); pos++) { count << "The score of " << pos-second << "\n"; } |
|
find member function for the map |
to fin out whether a key is present in the map, use the fund member function. t yields an iterator that pints to the entry with the given key, or past the end of the container if the key is not present |
|
the iterator of a map with key type K and value type V yield elements of type pair |
the pair class is a simple class defined in the header that stores a pair of values. It has two public (!) date fields first and second |
|
with the map class in the standard library, you use the [] operaotr to associate keys and values |
map scores; scores["tom"] = 90; scores["dick"] = 91; scores["harry"] = 92;
|
|
sets and dupicates |
Sets don't have duplicates Adding a duplicate of an elemetn that is already present is ignored |
|
strncat_s(), wcscat_s(), strncat_s(), wscncat_s()
functions of |
This functions provide secure alternative for string concatenating. All the usual function rely that the strings are terminated. |
|
strcpy_s() function |
a more secure version of strcpy() Requires an extra argument between the destination and source arguments that specifies the size of the destination string buffer |
|
comparing null-terminated strings via |
strcmp() compares two null-terminated strings that you specify by arguments that are pointers of type *char.
char* str1("Jill"); char* str2("Jill"); int result = strcmp(str1, str2); if (result<0) ..
|
|
Searching Null-Terminated Strings |
strspn() function searches a string for the first character that is not contained in a given set
|
|
C++ 11 introduces an alternative syntax for writing the function header |
auto power(double x, int n)-> double // Function header |
|
PASSING ARGUMENTS TO A FUNCTION |
There are two mechanisms used to pass arguments to functions. The first mechanism applies when you specify the parameters in the function defi nition as ordinary variables (not references). This is called the pass-by-value method of transferring data to a function
pass-by-value mechanism still operates as before; |
|
stream manipulators left and right |
left Selects left alignment.
out << left << setw(6) << 123; x right Selects right alignment (default).
123 // left 123 // right |
|
Accepting a Variable Number of Function Arguments |
int sumValues(int first,...)
There must be at least one ordinary parameter, but you can have more. The ellipsis must always be placed at the end of the parameter list. |
|
Declaring Pointers to Functions |
You can declare a pointer pfun that you can use to point to functions that take two arguments, of |
|
Prototype for a function, pfun, returning type double* |
double *pfun(char*, int);
long sum(long num1, long num2); // Function prototype |
|
When you initialize a pointer to a function in the declaration, you can use the auto keyword for the type. You can write the previous declaration as: |
auto pfun = sum; |
|
If you want to specify that a catch block is to handle any exception thrown in a try block, you put an |
ellipsis (...) between the parentheses enclosing the exception declaration: |
|
try block followed by two catch blocks looks |
try |
|
FUNCTION OVERLOADING |
Function overloading allows you to use several functions with the same name as long as they each have different parameter lists.
int max(int data[], const int& len); // Prototypes for |
|
int max(int data[], const int& len); // Prototypes for
double max(long data[], const int& len); // Not valid overloading Why? |
Every function — not just overloaded functions — is said to have a signature, where the signature of a function is determined by its name and its parameter list. All functions in a program must have unique signatures, otherwise the program does not compile. |
|
Suppose you define functions with the following
void f(int n);
These functions are differentiated by the type of the parameter, but code using these will not compile. |
When you call f() with an argument of type int, the compiler has no means of determining which function should be selected because either function is equally applicable. In general, you cannot overload on a given type, type, and an lvalue reference to that type, type&. However, the compiler can distinguish the overloaded functions with the following prototypes:
|
|
The f(int&) function will always be selected when the argument is an lvalue. The f(int&&)
int num(5); |
int num(5); |
|
Declaring Pointers to Functions |
The pointer can only point to functions with the same return_type and list_of_parameter_types specified in the declaration. If you attempt to |
|
assert function |
If the argument expression of this macro with functional form compares equal to zero (i.e., the expression is false), a message is written to the standard error device and abort is called, terminating the program execution.
#include |
|
recursive algorithm to find the largest element in an array (pseudo) |
Base Case: The size of the list is 1 |
|
recursive algorithm to find the largest element in an array (real code) |
int largest(const int list[], int lowerIndex, int upperIndex) else |
|
Binary search code
int binarySearch(const int list[], int listLength, int searchItem) |
int binarySearch(const int list[], int listLength, int searchItem) |
|
Template for function to compute the maximum element of an array |
template T max(T x[], const int& len) |
|
Arrays of Pointers to Functions
In the same way as with regular pointers, you can declare an array of pointers to functions. You can |
double sum(const double, const double); // Function prototype
You cannot use auto to deduce an array type, so you must put the specifi c type here |
|
It can be quite handy to be able to omit one or |
You can specify a default value for the parameter to this function by specifying the initializing string |
|
You can insert one or more objects after a given position in the list using the ______________ function |
insert_after()
int data[] = {1, 2, 4, 5}; std::Foward_list datalist; auto iter = datalist.insert_after(datalist.before_begin(), 11) //11 returns an iterator pointing to the inserted element
iter = data;ost.insert_after(iter, 3,15); //inserts 3 copies of the 3rd argument =15
iter = datalist.insert_After(iter, begin(data), end(data)); // insert a range following iter, and increments iter to point to 5 |
|
before_begin() |
a forward_list container also has a before_begin() func that returns an iterator pointing to the position before the first element |
|
int data[] = {1,2,3,4,5,6,7,8}; list numbers(data, data+3); //1,2,3 list values(data+1, data+8); //2,3,4,5,6,7,8
how are you going to merge the two lists |
number.merge(values); |
|
int data[] = {1,2,3,4,5,6,7,8}; list numbers(data, data+3); //1,2,3 list values(data+1, data+8); //2,3,4,5,6,7,8
merge the two lists and sort descending |
number.sort(greater()); // 3,2,1 values.sort(greater()); //8,7,6,5,4,3,2,1 number.merge(values, greater());
greater() func object specifies that the list should be sorted in desc sequence and then merger into the same sequence |
|
remove_if() func |
removes elements based on the result of applying a unary predicate |
|
What function allows you to remove all or part of one list and insert it in another. |
int data[] = {1,2,3,4,5,6,7,8}; list numbers(data, data+3); //1,2,3 list values(data+4, data+8); //5,6,7,8 number.splice(++begin(number), values); // 1,5,6,7,8,2,3 |
|
The assign() function comes in the two overloaded versions. The arguments to the first are the count of the number of replacement elements, and the replacement element value. The arguments to the second version are either two iterators or two pointers, specifying a sequence in the way you have already seen |
int data[] = {10,22,4,56,89,77,13,9}; list numbers(begin(data), end(data)); //1,2,3 number.assign(10, 99); // replace contents by 10 copies of 99 numbers.assign(data+1,data+4); // replace contents by 22,4, 56 |
|
The unique() function will eliminate _____________ |
adjacent duplicate elements from a list. If the list is sorted the function ensures that all elements in the list will be unique |
|
Replace the two functions with one template
#include "stdafx.h" int square(int x) { double square(double x) { int _tmain(int argc, _TCHAR* argv[]) |
#include "stdafx.h" using namespace std;
template T square(T t) { // int _tmain(int argc, _TCHAR* argv[]) getchar(); return 0;
|
|
code bloat |
each call to a template with different types we generate a template based function for each type. If we use a lot of types we get code bloat |
|
Cointainers
Sequence containers
Associative Containers
Unordered Containers |
Sequence containers vector dequeue list forward list array
Associative Containers (always sorted) set, multiset map, multimap
Unordered Containers unordered set/multiset unordered map/multimap
|
|
STL headers related to containers |
#include #include #include #include // set and multiset #include // map and multimap #include #include #include #include #include #include |
|
cout << vec[2]; vs cout << vec.at(2); |
cout << vec[2]; // no range check
cout << vec.at(2); // throw range_error exception of out of range |
|
for (int i; i < vec.size(); i++) cout << vec[i] << " ";
for (vector::iterator itr = vec.begin(); itr!=vec.end; ++itr) cout << *itr << " ";
Which is faster? |
The second options is faster and recommended |
|
Both aliases defined with typedef and aliases defined with using are semantically equivalent. The only difference being that |
typedef has certain limitations in the realm of templates that using has not. Therefore, using is more generic, although typedef has a longer history and is probably more common in existing code. |
|
Just like we can create function templates, we can also create class templates, allowing classes to have members that use template parameters as types. For example: |
template The class that we have just defined serves to store two elements of any valid type. For example, if we wanted to declare an object of this class to store two integer values of type int with the values 115 and 36 we would write:
mypair myobject (115, 36);
|
|
template T mypair::getmax ()
Confused by so many T's? |
There are three T's in this declaration: The first one is the template parameter. The second T refers to the type returned by the function. And the third T (the one between angle brackets) is also a requirement: It specifies that this function's template parameter is also the class template parameter. |
|
Template specialization |
It is possible to define a different implementation for a template when a specific type is passed as template argument. This is called a template specialization |
|
|
e = d; // copy assignment operator
The copy assignment member is the only operator implicitly defined for all classes. Of course, it can be redefined to any other functionality, such as, for example, to copy only certain members or perform additional initialization operations |
|
Constant iterators |
Each iterator type has a companion type for a constant iterator, similar to a constant pointer. Below is const-correct implementation of the find_entry fucntions:
int TelephoneDir::find_entry(string name) const { map::const_iterator p = database.find(name); if (p == database.end()) return 0; //Not found else return p->second; } |
|
multiset |
a multiset (or a bag) is similar to a set, but elements can occur multiple times
multiset names; names.insert("Romeo"); names.insert("Juliet"); names.insert("Romeo"); // now name.count("Romeo"); is 2 names.erase("Juliet"); // now name.count("Juliet"); is 0 names.erase("Juliet"); // no effect
|
|
summarize the performance of the fundamental operations on vector, list, and balanced binary tree |
Add/remove element at end Vector - O(1) Linked list - O(1) Balanced Binary Tree - N/A
Add/remove element in the middle Vector - O(n) Linked list - O(1) Balanced Binary Tree - O(log(n))
Get k-th element Vector - O(1) Linked list - O(k) Balanced Binary Tree - N/A
Find Value Vector - O(n) Linked list - O(n) Balanced Binary Tree - O(log(n)) |
|
Treee traversal schemes include |
preorder traversal inorder traversal postorder traversal |
|
a multimap cna have multiple values associated with the same key. Instead of using the [] operator, you insert and erase pairs |
multimap friends; friends.insert(make_pair("Tom", "Dick")); // Dick is a friend of Tom friends.insert(make_pair("Tom", "Harry")); // Harry is also a friend of Tom |
|
To find out whether a key is present in the map use the _____ member function |
find
It yields an iterator that points to the entry with the given key, or past the end of the container if the key is not present |
|
alternative syntax to define type aliases was introduced in the C++ language: |
using new_type_name = existing_type;
using C = char;
|
|
next_permutation
is a transformation algorithms that reorders the values in a sequence. For 1,2,3 there are 6 permutations 1,2,3-1,3,2-,2,1,3-2,3,1-3,1,2-3,2,1. Sequence of n elements will have n! permutations |
vector a(4); generate(a.begin(), a.end(), SequenceGenerator(1)); // init with values 1,2,3,4 while (next_permutation(a.begin(), a.end()) { cout << "output permutation "; for ( vector::iterator p = a.begin(); p!= a.end(); p++) { count << *p; << " "; } cout << "\n"; } |
|
max_element
used to locate elements within a sequence. This search algorithm returns an iterator that describes a position. |
vector d(10); generate(d.begin(), d.end(), rand); // gen 10 rand numbers vector::iterator max = max_element(d.begin(), e.end()); |
|
min_element
used to locate elements within a sequence. This search algorithm returns an iterator that describes a position. |
vector d(10); generate(d.begin(), d.end(), rand); // gen 10 rand numbers vector::iterator min = min_element(d.begin(), e.end()); |
|
find searching algorithm |
this function returns an iterator that identifies the first element that matches a give element
list values;
list::iterator p = find(values.begin(), values.end(), 7); |
|
find_if searching algorith |
this generic algorithm takes a predicate and returns the first value that satisfies the predicate.
The following will return the first leap year in a list of years:
list years; ... list::iterator first_leap = find_if(years.begin(), years.end(), is_leap_year); |
|
Traditional way to travers a struct |
Node * current = list.head; while ( current != NULL) { string item = current->data; current = current->next; }
|
|
pattern vs algorithm |
pattern is more abstract than an algorithm. Algorithm gives you specific instructions how to implement a computation. Pattern gives you advice on solving a design problem |
|
the difference between an ofstream and an ostringstream |
is the buffer that is attached to the stream ofstream class has a filebuf obj that saves characters to a file ostringstream has a stringbuf obj that inserts characters into a string |
|
visit all items in a linked list |
list::iterator pos; for ( pos = list.begin(); pos != list.end(); ++pos) { string item = *pos; } |
|
anonymous unions |
Unions can also be declared with no type name or object name. In this case, they become anonymous unions, and its members are directly accessible by their member names struct { char title[50]; char author[50]; union { float dollars; int yen; } price; } book;
struct { char title[50]; char author[50]; union { float dollars; int yen; }; } book; The only difference between the two pieces of code is that in the first one, the union has a name (price), while in the second it has not. This affects the way to access members dollars and yen of an object of this type. For an object of the first type (a regular union), it would be:
book.price.dollars book.price.yen
|
|
header file |
the standard library provides a number of predefined functions like
predicate versions of the standard relational operators equal_to, not_equal_to, greater, less, greater_equal, and less_equal (can be used with standard containers)
the standard arithmetic operator - plus, minus, multiples, divides, modulus, and negate ( can be used with generic algorithms ) |
|
accumulate function (part of ) |
takes two iterator denoting a range, the default value that is returned when the ranges is empty, and a function defaults to plus
the following returns the product of a vector of integers instead of their sum
int prod = accumulate(a.begin(), a.end(), 1, multiples()); |
|
generic algorithm |
is an algorithm that has been generalized so that it can operate not only with a wide variety of values and variety of types, but also with multiple types off containers |
|
two features are key to development of generic algorithms |
templates and iterators
templates allow algorithms to work with multiple types. Template parameters values are matched at compile time.
iterators are used to ties the algorithms to containers, and allow the same algorithm to work with many different containers |
|
definition of the for_each algorithm |
template void for_each(Iterator current, Iterator stop, Action action) { while (current != stop) { action(*current); ++current; } } |
|
find_if algorithm |
this generic algorithm takes a predicate and returns the first value that satisfies the predicate
The following would return the first leap year in a list of years
list year; ... list::iterator first_leap = find_if(year.begin(), year.end(), is_leap_year); |
|
function binary_search |
returns a Boolean value indicating whether or not the value is found in the container
operates on sorted sequence |
|
function lower_bound |
returns an iterator indicating where a value can be inserted so as to maintain ordering
operates on sorted sequence
there is also upper_bound |
|
function remove_copy |
takes a specific value as argument and copies to another container the sequence of the original container with all instances of the value removed
a = 1,2,3,2,4,2,5,6 b = 0,0,0,0,0,0,0,0
remove_copy(a.begin(), a.end(), 2) would copy all values except the 2s
a = 1,2,3,2,4,2,5,6 b = 1,3,4,5,6,0,0,0
|
|
function remove_copy_if |
would copy all values except those divisible by 2
a = 1,2,3,2,4,2,5,6 b = 0,0,0,0,0,0,0,0 remove_copy_if(a.begin(), a.end(), DivisibleBy(2)); a = 1,2,3,2,4,2,5,6 b = 1,3,5,0,0,0,0,0 |
|
function remove() |
a = 1,3,4,5,6,2,5,6 remove(a.begin(), a.end(), 2);
will return an iterator pointing to the 2
to remove the unwanted value use the erase function
vector::iterator p = remove(a.begin(), a.end(), 2); a.erase(p, a.end)); // remove the remaining values
the function remove_if is similar but with a predicate |
|
forgetting to erase removed elements |
because the generic algorithms manipulate containers indirectly via iterators, they never change the size of a container they are iterating over. vector x (1,2,2,3,3,3,4,4,4,4); unique(x.begin(), x.end());
will leave x holding the values 1,2,3,4,3,3,4,4,4,4. The unwanted ending parts of this collection are eliminated by using a subsequent erase operator
vector::iterator p=unique(x.begin(), x.end()); erase(p, x.end()); // now x will hold 1,2,3,4 |
|
algorithms count and count_if |
count and count_if are used to count the number of values in a collection, or to count the number of values that satisfy a predicate
int three_count = count(a.begin(), a.end(), 3); int event_count = count_if(a.begin(), a.end(), is_even); cout << " number of 3's " << three_count << ", number even " << even_count << " \n"; |
|
iterator adapters |
adapters allow you to reuse algorithms for new situations For example, through the use of an adapter, you can use an algorithm that is designed to fill a container to send data to an output stream |
|
Range-based for loop |
a ranged-based for loop is used to sequentially examine the values from an iterable expression, sich as a collection
for (int x : my_vec) { // do something } --- old way --- for (vector::const_iterator itr = my_vec.begin(); itr != my_vec.end(); itr++) { } |
|
forwarding constructor |
forwarding constructor allows one constructor to invoke a second constructor, thereby simplifying the coding of classes that have multiple constructor --- old way --- class Employee { public: Employee(); Employee(string name, double salary); } --- new way (note the def values) --- Employee:: Employee() : Employee("no name", 1.00) { } |
|
regular expressions example |
regex pattern("i[sp]+i"); // pattern is any number of s's or p's between i's match result; if (regex_match("Mississippi", result, pattern)) { for (int i = 0; i < result.size(); i++) count << "found " << result[i] << "\n"; } |
|
lambda function def |
lambda function is an unnamed function used as an expression, typically one passed as argument to another function. |
|
function objects |
function object is an instance of a class that defines the function call operator. Because the class defines this operator, instances of the class can be invoked using the same syntax as an ordinary function.
class DivisibleBy { public: DivisibleBy(int n); bool operator()(int x); private: int n; }; DivisibleBy::DivisibleBy(int in) : n(in) { }
inline bool Divisibley::operator()(int x) { return 0 == x % n; }
The value of the divisor n can be used by the constructor when an instance of this class is created. This instance can then be used as a function, one that will return true when the argument is divisible by given amount.
list a_list; ... auto itr = find_if(a_list.begin(), a_list.end(), DivisibleBy(17)); if (itr != a_list.end()) ... // found it
The need to construct the class DivisibleBy solely for the purpose of creating one simple function seems have-handed alternative is creating functions as expressions. |
|
lambda function |
lambda function is a pair if square brackets, followed by an argument list and the function body. The function has no name, and so is typically used only as an argument.
auto itr = find_if(a_list.begin(), a_list.end(), [](int x) { return 0 == x& 17; }); if (itr != a_list.end()) ... // Found it |
|
lambda function general syntax |
[](param1, param2, .., paramn) { statement }
[](int x) {return 0 == x % 17; }
Define a nameless function that can be used as an expression, most commonly as an argument to another function |
|
default/deleted implementations |
Syntax: return_type ClassName::func_name(param1,..., paramn) = default;
return_type ClassName::func_name(param1,..., paramn) = delete;
Example: void operator_(const Box& right) = default; void operator_(const Box& right) = delete;
Purpose: To indicate that the default implementation of a copy constructor, default constructor, assignment operator, or destructor should be instantiated (if he default keyword is used), or to indicate that the default implementation should not be created( if the delete keyword is used). |
|
concept (Def) |
concept is similar to class definition, but it is used to characterize the requirements that a template argument must satisfy.
function sum double sum(double array[], int n) { double result = 0; for (int i =0; i < n; i+ ) result =+ array[i]; return result; } sum is being generalized as a template templateT sum(T array[], int n) { T result = 0; for (int i =0; i < n; i+ ) result =+ array[i]; return result; }
The problem is that if you try to instantiate this func with a type that does not understand the addition operator, the compiler will produce an error message, but that message will refer to the template class and not to the declaration. Using concepts, we can ensure that any arg used to expand the template must know how to invoke eh addition operator. We need to describe the func. we need auto concept Addable { T operator+(T x, T y); } |
|
concept definition (general syntax) |
auto concept ConceptName { function declaration operator declaration } Example: auto concept Addable { T operator+(T x, T y); } Purpose: to define what operations a template argument must implement.
|
|
template function concept binding |
template requires concept1,...,conceptn return_type function_name(parameters) { statements }
Example: template requires Addable
Purpose: To indicate that template parameters to a template function definition must satisfy certain properties. |
|
template class concept binding |
template requires concept1,..., conceptn class ClassName { features };
Example: template requires Addable class Box { public: Box(T int) { value = init; } private: T Value; }
Purpose: To indicate that template parameters to a template class definition must satisfy certain properties. |
|
Initialization algorithms |
a container can be initialized by filling, copying, or generating.
fill(a.begin(), a.end(), 1); // fills a vector with value
fill_n(a.begin(),5,2); // fill the first five position of a vector with value 2
copy(a.begin(), a.end(), b.begin()); // fill b vector with the content of a
generate(c.begin(), c.end(), RandomInt(50, 75)); // fill vector with generated values
generate_n(c.begin(), 10, RandomInt(10, 20)); // fill the first 10 values of a vector generated values |
|
Sorting algorithms |
the list container provides for sorting as member functions
sort(a.begin(), a.end()); // sort reverse(a.begin(), a.end()); // reverse the sorted array random_shuffle(a.begin(), a.end()); // random shuffle |
|
stream iterator |
stream iterator is another form of adapter that is used to convert iterator operations into I/O stream operations. Example ostream_iterator.
The following program reads a file of integers from the standard input, removes all the even numbers, and copies those that are not even to the standard output, separating each value with a newline: int main() { vector x; copy(istream_iterator(cin), istream_iterator(), back_inserter(x); vector::iterator p = remove_if(x.begin(), x.end(), is_even); x.erase(p, x.end()); copy(x.begin(), x.end(), ostream_iterator(count, "\n")); return 0; } |
|
type inference/determination |
Type names can become exceedingly long and complicated particularly when using qualified names for iterators combined with template classes.
instead of vector::iterator current = a_container.begin(); we can use auto current = a_container.begin(); |
|
decltype keyword |
decltype keyword allows a declaration statement to infer the type of a new variable from the type of an existing variable |
|
auto initialization (syntax) |
auto var_name = initial_value;
Example: auto current = a_container.begin();
Purpose: Define a new variable with particular initial value, avoiding having to explicitly declare the type for the new variable. The type of the variable will be automatically inferred from the type of the initial value |
|
type duplication (syntax) |
decltype(Var_name) var_name; decltype(Var_name) var_name = initial_value;
Example: decltype(start_point) end_point;
Purpose: to |
|
Difference between aliases defined with "typed" and aliases defined with "using" |
Both aliases defined with typedef and aliases defined with using are semantically equivalent.
The only difference being that typedef has certain limitations in the realm of templates that using has not. Therefore, using is more generic, although typedef has a longer history and is probably more common in existing code. |
|
Anonymous unions |
Unions can also be declared with no type name or object name. In this case, they become anonymous unions, and its members are directly accessible by their member names. For example, look at the differences between these two structure declarations
structure with regular union struct { char title[50]; char author[50]; union { float dollars; int yen; } price; } book;
structure with anonymous union struct { char title[50]; char author[50]; union { float dollars; int yen; }; } book;
The only difference between the two pieces of code is that in the first one, the union has a name (price), while in the second it has not. This affects the way to access members dollars and yen of an object of this type. For an object of the first type (a regular union), it would be:
book.price.dollars
book.price.yen |
|
Here is an example with four ways to construct objects of a class whose constructor takes a single parameter: |
// classes and uniform initialization #include using namespace std;
class Circle { double radius; public: Circle(double r) { radius = r; } double circum() {return 2*radius*3.14159265;} };
int main () { Circle foo (10.0); // functional form Circle bar = 20.0; // assignment init. Circle baz {30.0}; // uniform init. Circle qux = {40.0}; // POD-like
cout << "foo's circumference: " << foo.circum() << '\n'; return 0;
} |
|
keyword struct |
keyword struct, generally used to declared plain data structures, can also be used to declare classes that have member functions, with the same syntax as with keyword class. The only difference between both is that members of classes declared with the keyword struct have public access by default, while members of classes declared with the keyword class have private access by default. For all other purposes both keywords are equivalent in this context. |
|
Const member functions |
When an object of a class is qualified as a const object:
const MyClass myobject;
The access to its data members from outside the class is restricted to read-only, as if all its data members were const for those accessing them from outside the class. Note though, that the constructor is still called and is allowed to initialize and modify these data members:
|
|
Copy constructor |
When an object is passed a named object of its own type as argument, its copy constructor is invoked in order to construct a copy.
A copy constructor is a constructor whose first parameter is of type reference to the class itself (possibly const qualified) and which can be invoked with a single argument of this type. For example, for a class MyClass, the copy constructor may have the following signature: MyClass::MyClass (const MyClass&);
|
|
Copy assignment |
Objects are not only copied on construction, when they are initialized: They can also be copied on any assignment operation. See the difference:
MyClass foo; MyClass bar (foo); // object initialization: copy constructor called MyClass baz = foo; // object initialization: copy constructor called
foo = bar; // object already initialized: copy assignment called |
|
Implicit conversion |
Implicit conversions are automatically performed when a value is copied to a compatible type. For example: short a=2000; int b; b=a;
Here, the value of a is promoted from short to int without the need of any explicit operator. This is known as a standard conversion. Standard conversions affect fundamental data types, and allow the conversions between numerical types (short to int, int to float, double to int...), to or from bool, and some pointer conversions.
|
|
pop_back member function for vector |
removes the last element of a vector, shrinking its size by one.
vector salaries(10);
Note that the pop_back function does not return the element that is being removed. If you want to know what that element is, you need to capture it first.
double last = salaries[salaries.size() - 1]; salaries.pop_back(); // Removes last from the vector
This is not very intuitive if you are familiar with the so-called stack data structure, whose pop operation returns the top value of the stack. Intuitive or not, the names
push_back and pop_back are part of the standard for C++. |
|
modify a vector via vector |
The following function raises all values in the vector by the given percentage. Because the vector content is modified, you must use a reference parameter:
void raise_by_percent(vector& values, double rate) { for (int i = 0; i < values.size(); i++) values[i] = values[i] * (1 + rate / 100);
} |
|
Type casting |
C++ is a strong-typed language. Many conversions, specially those that imply a different interpretation of the value, require an explicit conversion, known in C++ as type-casting.
There exist two main syntaxes for generic type-casting functional and c-like:
double x = 10.3; int y; y = int (x); // functional notation
y = (int) x; // c-like cast notation |
|
Special member functions are member functions that are implicitly defined as member of classes under certain circumstances. There are six: |
Default constructor C::C(); Destructor C::~C(); Copy constructor C::C (const C&); Copy assignment C& operator= (const C&); Move constructor C::C (C&&);
Move assignment C& operator= (C&&); |
|
If an ellipsis (...) is used as the parameter of catch (try catch) |
If an ellipsis (...) is used as the parameter of catch, that handler will catch any exception no matter what the type of the exception thrown. This can be used as a default handler that catches all exceptions not caught by other handlers:
try { // code here } catch (int param) { cout << "int exception"; } catch (char param) { cout << "char exception"; } catch (...) { cout << "default exception"; }
|
|
You must alert the compiler that the function call needs to be preceded by the appropriate function selection, which can be a different for every iteration in the loop by using the virtual keyword |
class Clock { public: Clock(bool use_military; virtual string get_location() const; virtual int get_hours() const; int get_minutes() const; bool is_military() const; private: ... } |