PPT - Computer Science

Report
Accelerated C/C++
Advanced OOP
CS 440/540
Spring 2015
Kenneth Chiu
Purpose
• I’m assuming all of you have had a first-pass in
C++.
– Basic style
– Basic programming approach
• Learn iteratively.
• Content-based on what has tripped me up in the
past.
• Why is C++ the way it is?
• Sometimes a language may have a mistake.
– What is a mistake in a language?
What Is A Language?
• What is a computer language?
– HTML?
– PHP?
– XML?
– Excel Macros?
• “Turing complete”
– Can compute anything that a TM can compute.
Compilation Process
• What happens when we compile?
– What is object code?
• Invoked via a front-end driver:
–
–
–
–
Run the preprocessor.
Run the compiler.
Run the assembler.
Run the linker.
• What happens when you run a compiled program?
–
–
–
–
OS loads the file into memory.
Sets up various memory regions.
May do some runtime linking/relocation.
Jump to main.
Language Runtime
• Close correspondence between machine and
source.
– i = 2 + j;
• Not a close correspondence.
– if (typeid(A) == typeid(B)) { … }
• Such machine code is said to be part of the
language runtime.
• Source code that causes no machine code to
be generated?
Types of Violations of the Standard
• What is a language standard, what does it specify?
– Does it tell you what you can or cannot do?
• Not really.
– It specifies constraints on the language. It says, if you do A,
then B happens.
– It’s a contract, essentially.
• What is a “violation” of the standard?
– It’s imprecise word, but commonly used to mean
something not in accordance with some aspect of the
standard.
– What happens when your program violates the standard?
• Does it mean the program won’t compile? Will it crash?
– Can a compiler also violate the standard?
– Are there different ways that a program can “violate” the
standard?
•
What will this print out?
– #include <iostream>
int main() {
char i = 0;
i--;
std::cout << (int) i << std::endl;
}
– Prints out -1 when compiled on remote.cs.binghamton.edu.
– Is it guaranteed to print this out? In every occurrence?
– How can we find out what it will print out?
– The compiler vendor needs to tell you if char is signed or unsigned?
•
•
Known as implementation-defined behavior.
What will this print out?
– void foo(int i1, int i2) { }
foo(printf(“First.\n”), printf(“Second.\n”));
– Is it guaranteed to print this out? In every occurrence?
– How can we find out what it will print out?
– You can’t. The compiler vendor can change it at will.
•
•
Known as unspecified behavior.
What will this do?
– int *a = 0;
*a = 1;
– Anything could happen. Anything.
– “Demons could fly out of your nose!”
– Known as undefined behavior.
Implications of “undefined behavior”
for the Implementer
• As the implementer, what do you do if the
specification says that the result is undefined
behavior?
• For example, let’s say the function below is
specified as:
– void foo(int *);
• If the pointer is null, the behavior is undefined.
• If the pointer does not point to the first element of an
array of two integers, then the behavior is undefined.
Compile-Time vs. Run-Time
• What kind of error is better?
• For a given error, there’s no advantage to
making it run-time.
• However, to turn that run-time error into a
compile-time error usually means using a
strict, statically-typed language.
• Those languages are usually thought of as
being not as flexible.
Preprocessor
•
#include “A.hpp”
– #include <A.hpp>
•
•
#define macro(a, b)
#if
–
–
–
–
•
•
•
•
•
•
#if FOO == 3
#if defined(a)
#endif
#else, #elif
#ifdef, #ifndef
#error, #pragma
__LINE__ (integer literal), __FILE__ (string literal), __DATE__ (string literal),
__TIME__ (string literal)
__cplusplus
# (stringification) and ## (token gluing) in expansions
[Show]
• -E (option to show results after preprocessing)
• [Show preprocessor_output_option.]
• Line continuation is a backslash at the end. (Make sure you don’t
have a space after the backslash.)
• What’s wrong with this?
– #define MY_MACRO(t)
void foo_##t() {
// This is a comment.
call_something();
}
\
\
\
\
• Multi-line macros:
– #define macro(x)
\
cout << x << endl;
\
cout << “DEBUGGING” << endl;
– Good?
– if (condition)
macro(my_var);
– #define macro(x)
do {
cout << x << endl;
/* Etc. */
} while (0)
– Why did we leave off the semicolon at the end?
\
\
\
\
• Macros can call other macros, but cannot be
used recursively.
• Suppose you have code that should compile on both Linux and
Win32, but you need to call a different function in each. What do
you do?
– Why not just have two versions of your source code?
• Conditional compilation:
– #ifdef __linux
some_linux_func(…);
#else
some_win32_func(…);
#endif
– Is this good?
– #ifdef __linux
some_linux_func(…);
#elif defined (__win32_preprocessor_symbol)
some_win32_func(…);
#else
#error Unknown platform
#endif
• Predefined identifiers: These are not macros
– __func__: A static const character array
initialized with the current function name.
• void some_func() {
cout << __func__ << endl;
}
void some_other_func() {
cout << __func__ << endl;
}
– Why aren’t these macros?
• Variadic macros
– #define foo(…) func(_VA_ARGS_)
– Let’s say we wanted to print the file name and line number with all of
our debug statements.
– [Show debug_print.]
– #include <stdio.h>
#define dbg(fmt, ...) \
fprintf(stderr, "%s[%d]: " fmt "\n",
__FILE__, __LINE__, ## __VA_ARGS__)
int main() {
dbg("%d, %d", 1, 2);
dbg("%d, %d, %f", 1, 2, 3.14);
dbg("Uh-oh!");
}
Assertions
• Assertions are ways of “asserting” that certain things are
true.
– By putting in an assertion, you are saying that if the expression
being asserted is not true, then something is very seriously
wrong.
• What kind of assertions might you use here?
– delet(Animal *a) {
…
}
– Animal *pop_front(List *l) {
…
}
• To make assertions work, include this header file:
– #include <assert.h>
• Assert liberally.
– Preconditions
• Any condition that before a section of code that that code relies on for
correctness.
– Postconditions
• Any condition after a section of code that that code will preserve, if it
was correct.
• For example, in a BST, you know that the left child must be greater
than or equal to the right child.
– Loop invariants
• Any condition within a loop that your code relies on for correctness.
• Consider code for binary search. Let’s say that it maintains an index to
the beginning of the current search region (begin_index), and a
pointer to the end of the current search region (end_index). What
assertion can you put in at the end of the loop?
– while (...) {
...
assert(???);
}
• Use to check return codes.
– A quick and dirty way of checking error codes.
Gives you 80% of the benefit, with 5% of the
effort.
– ec = some_lib_or_sys_call(…);
assert(ec == 0);
• To compile-out the assertions, define
NDEBUG.
– g++ -DNDEBUG foo.cpp
• How is the assert() macro defined?
– How do we find it?
– #ifndef NDEBUG
#define assert(e)
((e) ? static_cast<void>(0)
: fail(#e, __FILE__, __LINE__, __func__))
#elif
#define assert(e)
#endif
• What if we have an assertion that is low-cost, so we always want it to be
included, even in production code?
– #define check(e)
\
((e) ? static_cast<void>(0)
\
: fail(#e, __FILE__, __LINE__, __func__))
\
\
Assertions vs. Exceptions vs. Special
Return Values
• What are the possible behaviors you could implement for these
conditions?
– Animal *find(const char *type_name);
• Normally returns the found Animal.
• What should you do if the animal is not found?
– int read(int fd, char *buf, int count);
• Normally returns count of bytes read.
• What should you do if it is the end of file?
– double sqrt(double x);
• Normally returns the square root of the number.
• What should you do if the number is negative?
– int send_socket(int sock_fd, const char *buf,
int count);
• Normally returns the count of the number of bytes sent.
• What if the network is down?
– void *lookup_in_hash_table(const char *key);
• Normally returns the value that is found (which is a void * for this particular hash
table).
• What if the key is not found?
– void *malloc(size_t sz);
• What if there is no more memory?
Compile-Time Assertions
• assert() is strictly run-time. You won’t know till you run the
program.
• How can you assert things at compile-time?
– A limited number of things can be checked in the preprocessor:
• #define FOO 2
#if FOO < 4
…
#endif
• #if sizeof(long) < 8
#error Type long is too small.
#endif
– C++11 supports static_assert, which can check basically
anything that is a compile-time constant (constexpr).
• static_assert(sizeof(long) >= 8, “Type long is too
small.”);
– C++98 can use boost static asserts.
Comments
• How are these comments?
– // Define an int variable i in the for-loop, and
// initialize it to 0. Execute the for-loop as long
// as i is less than the value of a.size(). At the
// end of each iteration, increment i by 1. In the
// body of the for-loop, multiple a[i] by 2, and
// assign it to a[i].
– for (int i = 0; i < a.size(); i++) {
a[i] *= 2;
}
– // Add 7 to x, then bitwise AND it with the bitwise
// complement of 0x7.
– x = (x + 7) & ~0x7;
– // Call compute_y() with i and x as parameters.
– compute_y(i, x);
– // Initialize health to 1.
– double health = 1.0;
• Better?
– // Double each element in array a.
for (int i = 0; i < a.size(); i++) {
a[i] *= 2;
}
– // Round up x to next multiple of 8.
x = (x + 7) & ~0x7;
– // Compute y-coordinate of ith
// player given a fixed
// x-coordinate.
compute_y(i, x);
– // Create monsters starting at
// health 1.0, since health 0 means
// dead.
double health = 1.0;
• Don’t say the obvious.
– // Initialize x.
x = 1;
• Do comment the non-obvious.
– // Round up x to next multiple of 8
x = (x + 7) & ~0x7;
• How do you comment out large sections of code?
– Use #if 0 to comment out large sections. It will nest.
• If working in a team, consider leaving your initials/name in
comments that might need explanation.
– // x cannot be defined as a long due to a bug
// in the Solaris compiler. –ken
SOURCE CODE ORGANIZATION
C++/C Source Code Organization
• Why break code up into multiple files?
– Ease of finding things?
– Compilation speed.
• Only need to recompile part of the app.
• Known as separate compilation
– Libraries
– Reuse?
• If I put a class separately into A.cpp, it is easier to
move to another application.
• Okay, why split into header file and implementation file? What
(bad) things would happen if we did not?
– For libraries, the case is clear.
• Need declarations to tell the compiler how to call code.
– What about your application? Why not put everything into A.cpp,
like in Java?
• Suppose B.cpp needs to use class A.
• The compiler needs the declarations.
• Why not just include the whole source file?
– Why need header file if already linking the library?
• Because the link happens after the assembly code for a call is generated.
• Even if the compiler knew the libraries early, it can’t find the calling
information.
– Why need library if already have the header file?
• The header file tells the compiler how to call something, but there still has to
be some code there to call.
• Are you satisfied with these answers? What’s the meta-question
here? (Why isn’t this an issue in Java?)
• The header-file/implementation-file split is a
convention.
– The standard does not dictate what goes in a header
file.
– However, the design of C++ does strongly influence
best practices.
• What goes in a header file?
– The minimum amount necessary for the
implementation (classes and/or declarations of
standalone functions) to be used by other files.
– In other words, you divide the code into two chunks.
• In the first chunk, you put everything that is needed to use
your code.
– Such as call it, or if a class, define an instance of the object, etc.
– This is the header file (.hpp).
• Everything else goes in the second chunk.
– This is the implementation file (.cpp) file.
A.hpp
B.hpp
C.hpp
includes
A.cpp
B.cpp
C.cpp
main.cpp
compiled to
A.o
B.o
C.o
main.o
link
a.out
(exe)
Libraries
• How many times per executable is a header file
compiled? What about implementation file?
– If something can go in either, should we put it in the
header file or implementation file?
• What do these code snippets need?
• obj->a_member
• void foo(MyClass *) {}
• obj->foo();
• Where do these go?
•
•
•
•
•
Class definitions
Function definitions
Function declarations
Global variable declarations
Global variable definitions
Translation Unit
• Consider this code fragment from a file named foo.cpp:
– …
void foo() {
goo();
}
…
• Are either of these statements is clear and unambiguous?
– “The call to goo() will be a syntax error if there is no declaration of it in this
file.”
– “The call to goo() will be a syntax error if this file doesn’t declare goo(),
and this file doesn’t (recursively) include any header files that declare
goo().”
• This suggests that we should have a new term: A translation unit is the
result of reading in a file, after all processing of included files and
conditional compilation.
– “This will be a syntax error if there is no declaration of goo() in the translation unit.”
Handling Global Variables
• How do you use global variables when you
split things into files? Does this work?
File1.cpp
File2.cpp
int a;
void f() {
// Access a.
// …
}
int a;
void g() {
// Access a.
// …
}
$ g++ File1.cpp File2.cpp ...
One Definition Rule (ODR)
• In C and C++, each variable can be defined only once.
You can declare a global variable by using extern.
– Defining (no extern) actually creates a variable.
– Declaring (by using extern) states the existence of a
variable, and indicates that it was defined somewhere
else, so tells the linker to go look for it.
• So, a global variable should be defined in one
translation unit and declared in all others that use it.
• How to fix previous?
•
You need to have:
File1.cpp
int a;
void f() {
// Access a.
// …
}
•
File2.cpp
extern int a;
void g() {
// Access a.
// …
}
Of course, you should probably be more systematic about it:
globals.cpp
globals.hpp
int a;
double x;
extern int a;
extern double x;
File1.cpp
File2.cpp
#include “globals.hpp”
void f() {
// Access a.
// …
}
#include “globals.hpp”
void g() {
// Access a.
// …
}
$ g++ globals.cpp File1.cpp File2.cpp ...
• There is a lot of redundancy between globals.hpp and
globals.cpp. Imagine if it were a very large file. Anyway to avoid it?
globals.cpp
globals.hpp
int a;
double x;
// ...
// Zillions of them
extern int a;
extern double x;
// ...
// Zillions of them
• Leverage the preprocessor:
globals.hpp
#ifndef XYZZY_GLOBALS_HPP
#define XYZZY_GLOBALS_HPP
#include <A.hpp>
#ifndef XYZZY_GLOBALS_EXTERN
#define XYZZY_GLOBALS_EXTERN extern
#endif
XYZZY_GLOBALS_EXTERN A a;
XYZZY_GLOBALS_EXTERN double x;
#endif
File2.cpp
#include “globals.hpp”
void g() {
// Access a.
// …
}
globals.cpp
#define XYZZY_GLOBALS_EXTERN
#include “globals.hpp”
$ gcc File1.cpp File2.cpp globals.cpp
• Isn’t this actually more complicated?
ODR, Revisited
• Let’s say you are the linker implementer. Could
you make this work if you wanted to?
File1.cpp
File2.cpp
int a;
void f() {
// Access a.
// …
}
int a;
void g() {
// Access a.
// …
}
$ g++ File1.cpp File2.cpp ...
• [Show multiple_definitions]
• What about this?
File1.cpp
File2.cpp
int a;
void f() {
// Access a.
// …
}
int a = 1;
void g() {
// Access a.
// …
}
$ g++ File1.cpp File2.cpp ...
• We could even make this work, but which one?
• At some point, rules become too complicated.
Sometimes simple rules are better, even if they
sometimes seem to make things inconvenient.
Include Guards
• The (loose) convention in C++ is to put each class in a separate header file.
• Is this correct?
D1.hpp
#include "B.hpp"
class D1 : public B {
… };
B.hpp
class B { … };
D2.hpp
#include "B.hpp"
class D2 : public B {
… };
main.cpp
#include "D1.hpp"
#include "D2.hpp"
int main() {
D1 d1;
D2 d2;
// …
}
• Include guards make includes “idempotent”. (This means it’s okay if a file
gets included twice.)
• Maintains simple rule: If you use a class, include its header file.
B.hpp
#ifndef XYZZY_B_HPP
#define XYZZY_B_HPP
class B {
… };
#endif
D1.hpp
#ifndef XYZZY_D1_HPP
#define XYZZY_D1_HPP
#include "B.hpp"
class D1 : public B {
… };
#endif
Why the funny prefix?
D2.hpp
#ifndef XYZZY_D2_HPP
#define XYZZY_D2_HPP
#include "B.hpp"
class D2 : public B {
… };
#endif
main.cpp
#include "D1.hpp"
#include "D2.hpp"
int main() {
D1 d1;
D2 d2;
// …
}
• Does this work?
– // A.hpp
#ifndef ACME_A_HPP
#define ACME_A_HPP
#include “B.hpp”
struct A {
B *b_field;
};
#endif
– // B.hpp
#ifndef ACME_B_HPP
#define ACME_B_HPP
#include “A.hpp”
struct B {
A a_field;
};
#endif
• First-level of include:
Include of
B.hpp from toplevel A.hpp
– // A.hpp
#ifndef ACME_A_HPP
#define ACME_A_HPP
// B.hpp
#ifndef ACME_B_HPP
#define ACME_B_HPP
#include “A.hpp”
struct B {
A a_field;
};
#endif
struct A {
B *b_field;
};
#endif
• Second-level of include
Include of B.hpp in
top-level A.hpp
– // A.hpp
#ifndef ACME_A_HPP
#define ACME_A_HPP
// B.hpp
#ifndef ACME_B_HPP
#define ACME_B_HPP
// A.hpp
#ifndef ACME_A_HPP
#define ACME_A_HPP
#include “B.hpp”
struct A {
B *b_field;
};
#endif
struct B {
A a_field;
};
#endif
struct A {
B *b_field;
};
#endif
Include of A.hpp in
include of B.hpp in toplevel A.hpp
• Solution is a forward declaration to break the cycle.
– // A.hpp
#ifndef ACME_A_HPP
#define ACME_A_HPP
struct B;
struct A {
B *b_field;
};
#endif
– // B.hpp
#ifndef ACME_B_HPP
#define ACME_B_HPP
#include “A.hpp”
struct B {
A a_field;
};
#endif
• How about this?
– // A.hpp
#ifndef A_HPP
#define A_HPP
struct B;
struct A {
B foo() { return B(); }
};
#endif
– // B.hpp
#ifndef B_HPP
#define B_HPP
struct A;
struct B {
A foo() { return A(); }
};
#endif
Show recursive inline
• Need to split apart class definition from function
definition:
– // A.hpp
#ifndef MY_COMPONENT_HPP
#define MY_COMPONENT_HPP
struct B;
struct A {
inline B foo();
};
struct B {
inline A foo();
};
inline B A::foo() { return B(); }
inline A B::foo() { return A(); }
#endif
Show recursive inline
• Can accomplish same effect by careful positioning.
– // A.hpp
#ifndef A_HPP
#define A_HPP
struct B;
struct A {
inline B foo();
};
#include “B.hpp”
inline B A::foo() { return B(); }
#endif
– // B.hpp
#ifndef B_HPP
#define B_HPP
struct A;
struct B {
inline A foo();
};
#include “A.hpp”
inline A B::foo() { return A(); }
#endif
Show recursive inline
• Header files should be independent.
– // Should not need anything here.
#include <A.hpp>
• A header file should always be included in the
implementation file. Which is better?
– // File A.cpp
#include <iostream>
#include <A.hpp>
// Code is here…
– // File A.cpp
#include <A.hpp>
#include <iostream>
// Code is here…
CLASSES
Objects
• What is an object?
• What is object-oriented programming? What is non-OOP?
– In non-OOP, data and the code that use and modify data are all mixed
together. There is not a clear notion that this code goes with this data. Data is
“amorphous”, without clear groupings.
• Can you do object-oriented programming in C?
– Xt
– File systems
– struct class1 {
int (*method1)(struct class1 *, double x);
double member1;
int member2;
};
p->method1(p, 3.14);
• Classes encapsulate operations and data, grouping them together.
• Class syntax is all about how to group the data and the operations, and
what operations are valid, etc.
• An object in C++ has a set of “fields”, known as
data members. Those belong to the object.
– Then there are a set of member functions, these
operate on the data members.
Class Definition
• Class definition looks like:
– class Foo { … } obj1, obj2;
class Foo { … };
Foo obj1, obj2;
• Are these different types?
– class Type1 { int mem1; double mem2; } o1;
class Type2 { int mem1; double mem2; } o2;
o1 = o2; // Type error?
– Types in C++ are by name only, so above doesn’t work. How about
this?
• typedef Type1 Type3;
Type1 o1;
Type3 o2;
o1 = o2; // Type error?
• Typedefs are aliases, so it works.
• Another kind of typing, not supported by C++,
is “duck typing”.
• “When I see a bird that walks like a duck and swims like
a duck and quacks like a duck, I call that bird a duck.”
– James Whitcomb Riley
– If an object can behave like A, then it is an A.
– Usually used with dynamic typing.
• Can add methods at run-time.
– Just try to call the method. If it’s there, then it will
succeed.
Member Variables
• Member variables (also known as data members or
fields) are declared like:
– class A {
string _label;
int m_position;
double energy_, weight_;
};
– Why all the funny stuff at the beginning or end?
Member Functions
• Member functions define the set of valid “operations” that
you can do on an object of a particular class.
– class A {
public:
void op1(int i);
void op2(double x) { … }
void op3(const std::string &);
…
};
void A::op1(int i) { … }
void A::op3(const std::string &s) { … }
• (Normally the function definition and class definition would not be in the same
file.)
• Member functions always operate on an object.
– They have access to all member variables.
– Remember, you cannot call a member function without an object!
– (Except for static member functions, which we’ll talk about a bit later.)
• Inside a member function, to refer to a member, just use
the name:
– class A { int member; … };
void A::func(int i) {
int j = member*i;
…
}
A a1, a2;
a1.func(1); // Uses a1.member.
a2.func(2); // Uses a2.member.
• What if a local variable has the same name as a member?
– class A { int i, j; … };
void A::func(int i) {
int ii = i;
int j = 2;
int k = j;
…
}
• Inlined member functions
– Implicitly
• class A {
void f() { … }
• Java-style.
– Explicitly
• class A {
inline void f();
};
// Does this go in header file or .cpp file?
inline void A::f() { … }
– Why inline? What should be inlined?
– [Show excessive_inlining.]
– Don’t get in the habit of always defining the member
function in the class, since it will cause excessive
inlining.
• Two (member) functions can have the same
name. As long as they have different
signatures, there is no conflict.
– void foo(int);
void foo();
void foo(int, int);
int foo(int); // Okay?
The this Pointer
• Member functions execute “within” objects.
• In the member function, a special keyword is used to
refer to the object within which the member
function is executing.
– class A { int member; void A::func(); };
void A::func() {
// The type is as if defined as:
//
A *this;
this->member;
}
• Inside a member function, class members are
searched when a name is used.
– class A { int a; … };
void A::func() {
a = 1123;
}
• This can be thought of an implicit usage of the this
pointer, which can also be used explicitly for clarity
or for disambiguation.
– class A { int a; … };
void A::func() {
int a;
a = 123;
this->a = 456;
}
Static Class Members
• Suppose you want to assign a unique object ID to
every instance of a class. How would you do it?
– class A { int id; };
int obj_id; // Global counter.
A::A() {
id = obj_id++;
}
• Disadvantages?
– Global variables should be avoided.
• How else would you improve the above?
• There is only one variable for each static member,
which is used by all instances of a class.
• Using a static member can enforce better
encapsulation, avoid polluting namespace, etc.
– // In A.hpp.
class A {
private:
const int id;
static int next_id;
};
– // In A.cpp.
A::A() : id(next_id++) { }
int A::next_id;
• Const static integer members can be assigned
a value in the class:
– struct A {
static const int N = 10;
};
• They can be used as compile time constants:
– int array[A::N];
• They do not require a definition unless there
address is taken (odr-used).
Typedefs and Type Aliases
• Typedefs and type aliases can be defined in a class.
– class A {
public:
typedef A *a_ptr;
using b_ptr = B *; // C++11
…
};
…
A::a_ptr a; // Pointer to A.
A::b_ptr b; // Pointer to B.
– Type alias is the same as typedef except that with type alias can
define alias templates.
– In this case, it is not that powerful, but we will see later on that
typedefs can be very useful, especially when combined with
templates.
Member Access Control
• C++ provides a way to label members with different
degrees of access from scopes outside of the class.
– class A {
int private_member;
public:
int public_member;
private:
int private_member2;
};
– public: All have access.
– private: Only member functions of the same class, or
member functions of friend classes.
– protected: Only member functions of the same class, friend
classes, or derived classes have access.
What is a struct?
• What is the difference between this class
and this struct?
class A1 {
public:
void f();
int i1;
private:
int i2;
};
struct A2 {
public:
void f();
int i1;
private:
int i2;
};
• A struct is the same as a class, except that initial
access is public instead of private.
class A1 {
void f();
Private
int i1;
members
private:
int i2;
};
struct A2 {
void f();
Public
int i1;
members
private:
int i2;
};
Friends
•
A function or operator can be granted access to private members.
– class A {
friend void foo();
private:
int i;
};
void foo() {
A a;
a.i; // Okay.
}
void goo() {
A a;
a.i; // Access violation.
}
•
Member functions and other classes can also be friends.
– class A {
friend int B::f();
friend class B;
…
};
• A friend function can be defined in the friend declaration, and is implicitly
inline:
– struct A {
friend void foo() { }
};
• A friend declaration is not actually a declaration:
– struct B {
friend void foo();
};
int main() {
foo(); // Syntax error.
}
• However, in some cases, argument-dependent lookup (ADL) will apply.
– struct C {
friend void foo(C *);
};
int main() {
C c;
foo(&c); // Will compile, due to ADL.
}
How Much Privacy Is There?
• Is this breaking encapsulation? Is it how we think of
encapsulation in the real world?
– class Person {
private:
int private_info;
…
};
void Person::snoop(Person *other_person) {
cout << this->private_info
<< other_person->private_info << endl;
}
• This is arguably breaking encapsulation, but is syntactically
okay.
• What if you strongly are against this? What can you do?
– You can use conventions to try to enforce best practices.
– Coding style is that only the same object can access private members.
“Public” vs. public:
• I will sometimes use “public” in two different
ways.
– “You don’t want this to be part of your public API.”
• Don’t document it as something for external use.
– “This member must have public: access for the
code to work.”
• The first is a statement more at the design level.
• The second is at the implementation level.
• There is not always a perfect correspondence
between the two levels.
What Do You Make Private?
•
Which classes do you make friend classes?
– class A {
void somewhat_private();
void really_private();
void public();
};
– Suppose class B needs A::somewhat_private(), while class C needs
A::really_private(). What do you do?
•
In C++, a class has:
– a “private” interface, composed of the data and function members exposed to friends
and member functions.
– A “public” interface, composed of public members, exposed to everyone else.
•
•
In real life, how many “interfaces” do you, as a person, have?
In the real world, our relationships are not divided into just public and private.
– We have a completely public interface,
– a professional interface used at work,
– a friend interface used with friends, a family interface used with family, etc.
• Similarly, an object might have more than just two
“interfaces”.
• Suppose a class A had a helper class named Helper
that needed access to a certain non-public interface,
but not to all the private members of A. No way in
current C++ to do this, but this is a possible syntax
for it.
– class Helper {…};
class A {
expose_to Helper:
void func1();
expose_to all: // Same as public:
void func2();
private:
void func3();
Forward Declarations
• Which of these are allowed?
class A {
int i;
A *a;
};
class A {
int i;
A a;
};
class A {
int i;
static A a_member;
};
class A {
int i;
B b;
};
class B {
int i;
A a;
};
class A {
int i;
B *bptr;
};
class B {
int i;
A *aptr;
};
– Will the above actually compile?
• Use a forward declaration.
– class B;
class A {
B *bptr;
};
class B {
A *aptr;
};
Classes Define a Scope
• One of the scopes in C++ is class scope.
– // Where can you use these names?
class A { int i; void foo(); };
• Outside of a class, can use resolution operator.
– class A { … };
// This would refer to a member
// of A. Will it compile?
int i = A::var;
– Remember that scope is about what a name refers to.
You can refer to a name in a way that is a syntax error.
const Member Functions
• Objects (including primitives) in C++ can be
declared const.
– const A a, b;
const int i = 2134;
i = 1; // Okay?
a = b; // Okay?
a.my_method(); // Okay?
•
•
•
A member function can be called on a const object only if it does not change
the object.
C++ uses a keyword to indicate that the member function does not modify the
object.
What happens?
– void A::func() const {
member = 1234;
}
•
Which of these will compile?
– void A::nonconst_func() {
A *ap = this;
}
– void A::const_func() const {
A *ap = this;
}
– void A::const_func2() const {
const A *ap = this;
}
– void some_func(A *obj); // Changes obj.
void A::func() const {
some_func(this);
}
• Let’s say that you really need to change a member in a const
function. What do you do?
• Is this safe?
– void A::func() const {
A *ptr = const_cast<A *>(this);
ptr->member = 1234;
}
– const A a_const;
a_const.func(); // Okay?
A a_nonconst;
const A &const_ref(a_nonconst);
const_ref.func(); // Okay?
– [Show cast_away_const.]
• Rule says that casting away constness is okay, but if you try to cast
something that was defined const, the behavior is undefined.
• If you cast away constness of something that was not defined const,
but is being accessed through a const pointer or ref, then it is okay.
• What does constness mean?
– void func(const A &a) {
const int i1 = a.member;
some_other_func();
const int i2 = a.member;
if (i1 != i2) {
// Is this possible?
…
}
}
• Constness does not mean that the object will not
change. It means that you promise not to change it.
• A const member function is guaranteed not to
modify the object.
• Suppose you write a class named Trie, with a
function:
– int lookup(const std::string &) const;
• Your users are not quite satisfied with speed. You
examine the usage patterns, and you notice that it
looks like:
– lookup “abcdef”
… Repeated 1 million times.
lookup “xyz”
… Repeated 1 million times.
etc.
• What might you do to improve performance?
• Cache the last lookup:
– class Trie {
…
std::string cached_key;
int cached_value;
};
int lookup(const std::string &key) const {
if (key != cached_key) {
cached_key = key;
cache_value = real_lookup(key);
}
return cached_value;
}
• Does this work? Should it work?
• mutable keyword can be used to indicate that a member
can be changed, even if the object is const.
– class MyClass {
mutable int var;
};
• Will allow this:
– struct A {
void func() const;
mutable int a_member;
};
void A::func() const {
this->a_member = 234;
}
int main() {
const A const_a;
const_a.func();
}
• Const-ness can be physical or logical.
– Physical constness: the bits don’t change.
– Logical constness: a user of the public interface of
the object cannot detect any change.
• Which is better?
– Often debated, but in my experience, I have found
logical constness to be preferred, due to the issues
in the previous slide.
– I generally use logical constness.
Class Scope
• A number of things can be defined in class scope, and can be
referenced from outside the class.
– struct A {
int data_member;
void func_member();
typedef int typedef_member;
class class_member { … };
static int static_data_member;
static void static_func_member();
enum enum_member { … };
};
• Nested types can be used normally:
– A::typedef_member i; // Defines an int.
// Defines an object of the nested class.
A::class_member obj;
• Name resolution needs to consider class
scope.
• Local first, then class, then namespace.
Nested Classes
• Classes can be nested:
– class A {
class B {
int i;
void f();
};
void f();
int i;
};
• Okay, but what does it mean?
• Suppose we create an object of type A. Is
this the correct picture of the object?
– No, nesting a class only nests the scopes
created by the classes.
A a;
Object of class of A::B
class A {
class B {…};
…
};
• There is no nesting of objects implied.
• A nested class can be used to create objects
external to the outer class.
class A {
public:
class B {…};
…
};
A::B b_obj1;
A a_obj;
A::B b_obj2;
• How can one get this, if this is what one
wants?
– Use composition.
– Or use inheritance.
Object of class A
class A {
class B {…};
B b;
};
Object of class of A::B
Object of class A
Object of class of B
class B {…};
class A {
B b;
…
};
• But this can be done without nested classes.
• What is the purpose then of nested classes?
– The scoping helps to hide information, and also reduce name
clashes.
– With overloading, exceptions, and templates, often useful to
create small helper classes, that are only used inside the outer
class. These make sense to define as nested classes.
• What about access and nested classes? Consider:
– class A {
class B {
int B_priv;
void B_f();
};
void A_f();
int A_priv;
};
void A::A_f() {
B b;
b.B_priv; // Allowed?
}
void A::B::B_f() {
A a;
a.A_priv; // Allowed?
}
• A nested class is automatically a friend of the outer class.
– I.e., inner can access outer.
• The outer class is not a friend of the inner class, however.
– I.e., outer cannot access inner.
Local Classes
• Can be declared in a function body.
– void f() {
class Local {…};
…
}
• Everything must be in class definition.
• Sometimes handy for creating small, local
functions.
• Can call recursively, and access local static
variables.
– void work() {
static int i;
struct Local {
static void foo() {
goo(i + 1);
}
static void goo(int j) {
...
}
};
Local::foo();
}
INITIALIZATION, ASSIGNMENT, AND
DESTRUCTION
Default vs. Implicit
• For some things, the compiler will automatically
generate one for you, if you don’t define one. These
are known as the implicit versions.
• What are some of these?
–
–
–
–
Default constructor
Destructor
Copy constructor
Copy assignment operator
• A constructor that takes no arguments is called the
default constructor.
Constructors
• Objects are initialized with constructors:
– class A {
public:
A(); // Default constructor.
A(int);
A(double, int, const B &);
};
• What get’s executed?
– class A {
public:
A() { … } // Default ctor.
A &operator=(const char *) { … } // Copy assign.
};
– A a = “hello”;
• These are essentially the same:
– A a(“hello”); // Direct initalization.
A a = “hello”; // Copy initialization, NOT assignment.
– [Show equal_ctor.]
• Default constructor is used when no constructor
arguments are given.
– A a1, a2(3), a3();
– What is the difference between a1 and a3?
• Hint: A a4(int);
• Default arguments can be useful:
– Time::Time(int hour, int min,
Timezone tz = UTC);
• Which of these is okay?
– class A {
public:
A(int);
};
class B { };
B b; // Compiles?
A a; // Compiles?
– If you don’t define any constructor,
• the compiler will implicitly define a default constructor.
– If you define a non-default constructor,
• then the compiler will not implicitly define the default
constructor.
• You can explicitly ask the compiler to generate the default
constructor in C++11:
– struct Foo {
Foo() = default; // Inlined.
std::string str;
};
– struct Foo {
Foo();
std::string str;
};
// In .cpp file.
Foo::Foo() = default; // Not inlined.
• What happens if you don’t do the above? Any difference?
• What about this?
– struct Foo {
Foo() = default;
Foo(const char *s) : str(s) {}
std::string str;
};
Conversions
• How would you critique this code?
– struct String {
// Construct using given C string.
String(const char *s) { . . . }
// Create a string of spaces of the given length.
String(int length_) { . . . }
int length;
char *buf;
};
void print(const String &) {
cout << s.buf << endl;
}
...
int nl = 100; // Name length, used later.
// Create three names.
String n1(“alice”), n2(“bob”), n3(“joe”);
print(nl); // Print the first name.
– struct Polygon {
Polygon(int n_sides);
...
};
void draw(const Polygon &);
...
Polygon square(4);
int squared = 4*4; // Area of the square.
// Draw the square created above.
draw(squared);
• The programmer most likely did not intend the automatic conversion.
– How to prevent it?
• Constructors define conversions. What if you don’t want the conversion?
– Disable with explicit keyword.
– For example,
explicit Polygon(int n);
– class String {
public:
// Create a string of spaces
// of the given length.
explicit String(int length);
…
};
• Explicit constructors also cannot be used in copy initialization:
– Polygon p1(10); // Okay.
Polygon p2 = 10; // Error if explicit.
Explicit Temporaries
• Let’s say you have a 2-D Vector class:
– Vector v1(x1, y1), v2(x2, y2);
v1 = v2;
v2 = ...; // How to assign (2.3, 3.1) to v2?
• Could use a “setter” method.
– v2.set(2.3, 3.1);
• The more idiomatic C++ way is with explicit temporary.
– v2 = Vector(2.3, 3.1);
• Also very commonly used with return values.
– Vector operator+(const Vector &v1, const Vector &v2) {
return Vector(v1.x + v2.x, v1.y + v2.y);
}
Member Initialization
• Consider a class designed to be a better string:
– class String {
…
int len; // Length of the string
char *buf; // Array of chars to hold it.
};
• What should the initial values be, when we create a string?
How do the members get the initial values?
• [Show string_init.]
• Consider:
– struct A {…};
struct B {
B();
A a;
};
B::B() {
// How do we initialize the a member?
}
• If we do nothing, then the default constructor for A
will be used, if there is one.
• If default constructor for A is not right, then use
constructor initializer list:
– B::B() : a(12, 3) {}
• Any difference between the two versions of the constructor?
– class A {
public:
A(const char *name);
private:
std::string name_;
};
// Version 1.
A::A(const char *name) {
name_ = name;
}
// Version 2.
A::A(const char *name) : name_(name) {}
• Any time when you must use initializer list
syntax?
– struct B { B(int); };
class A {
public:
A(const char *);
private:
const std::string name_;
B b;
};
A::A(const char *name) : b(1) {
name_ = name; // Okay?
}
Construction of const object
• Is this okay?
– struct A {
A() {
member = 1234; // Okay?
}
int member;
};
// Assigns to member inside ctor.
const A a;
• Inside the constructor of a const object, the this pointer is not
const, so we can assign to members.
• Makes sense in hindsight, since this must be statically typed.
Member Initializers
• Does this work?
– class A {
int position = 2;
};
– No in C++98, yes in C++11. Also can do:
• class B {
vector<int> v = {1, 2, 3};
vector<int> v2{4, 5, 6};
};
• Any advantage?
• Gives a default that all constructors use.
– class A {
A(int i) {}
A() = default;
int position = 2;
};
Constraining Object Creation
• What if we don’t want to allow an object of a particular class
to be created just anywhere?
– class A {…};
void foo() {
A a; // How to disallow this?
}
• Use private, unimplemented constructor (C++98):
– class A {
private:
A();
};
• How is the object ever created then?
– Can be created in friends, static member functions, etc.
• Note that if you define a private, non-default ctor, the default
ctor will not be generated:
– class A {
private:
A(int);
};
• In C++11, you can make this explicit with the delete
keyword.
– class A {
A() = delete;
private:
A(int);
};
Copy Constructors
• Consider the following:
– void foo(A a_param) { … }
A a_arg(2);
foo(a_arg);
– Is a_param the same object as a_arg? If not, then how
is it initialized? What function is called?
• Initialization of an object with another object is done
so often it has a special name: copy construction.
– The prototype is: A(const A &).
• If you don’t define a copy constructor, one will
be automatically defined (implicit), that has
the following definition.
– class A {
B1 b1;
B2 b2;
int i;
};
A::A(const A &a)
: b1(a.b1), b2(a.b2), i(a.i) {}
• Consider a string class.
– class String {
public:
String();
~String();
private:
char *buf;
};
String::String() : buf(malloc(10)) {
strcpy(buf, “hello”);
}
String::~String() { free(buf); }
• Okay?
– Does the implicit copy constructor do the right
thing for this class?
• If the implicit copy constructor is not correct, to
disallow copy construction, use a private,
undefined copy constructor.
– class A {
private:
A(const A &); // Not defined.
…
};
• In C++11, use delete keyword.
– class A {
A(const A &) = delete;
…
};
Delegating Constructors
•
Let’s say you have a class that needs to be initialized with a string and an integer.
– A a(“hello”, 5);
– struct A {
A(const std::string &s, int i) { /* … */ }
// …
};
•
You would like to make the integer default to 1 if not supplied.
– A a(“hello”);
– struct A {
A(const std::string &s, int i = 1) { /* … */ }
// …
};
•
Also, you’d like to make the string default to “hello” if not supplied.
– A a(5);
– struct A {
A(const std::string &s = “hello”, int i) { /* … */ }
A(int i) { … }
// …
};
•
You could also use a constructor helper:
– struct A {
A(int i) { ctor_helper(“hello”, i); }
A(const std::string &s, int i = 1) { ctor_helper(s, i); }
private:
void ctor_helper(const std::string &, int i);
// …
};
•
•
Members are constructed, then assigned to, which is inefficient.
Doesn’t work if there are const members.
– struct A {
A(int i) : count(i) { ctor_helper(“hello”, i); }
private:
void ctor_helper(const std::string &, int i);
const std::string s;
const int count;
// …
};
• No great solution in C++98. In C++11, use delegating ctors:
– struct A {
A(const std::string &n, int c)
: name(n), count(c) { /* … */ }
A(int c) : A(“hello”, c) { /* … */ }
A(const std::string &n) : A(n, 1) { /* … */ }
private:
const std::string s;
const int count;
// …
};
Destructors
• Is this correct?
– struct A {
A();
char *buf;
};
A::A() : buf(malloc(10)) {}
• Memory leak, to fix:
– struct A {
A();
Necessary?
~A();
char *buf;
};
A::A() : buf(malloc(10)) {}
A::~A() { free(buf); buf = 0; }
• Clean up when an object goes out of scope.
– What kind of things might it do?
Assignment
• (Copy) Assignment operator is called:
– class A {…};
A a, b;
a = b;
• If no (copy) assignment operator is defined explicitly, an
implicit one will be defined by the compiler. It will be
equivalent to:
– class A { B b, c; int i; };
A &A::operator=(const A &a) {
b = a.b;
c = a.c;
i = a.i;
return *this;
}
• Consider our string class again.
– class String {
public:
String(const char *s);
~String();
private:
char *buf;
int len; // Length not including null byte.
};
String(const char *s) : len(strlen(s)) {
buf = new char[len + 1];
strcpy(buf, s);
}
~String() {
delete [] buf;
}
• Would the implicit assignment operator be correct for this?
• To disallow, make it private and undefined. Or use delete
keyword.
• What should the return type of the assignment
operator be?
– ??? MyType::operator=(const MyType &);
– Should this work?
• a = b = c; // Which way does this group?
• a = (b = c); // Can it return a value?
– For efficiency, it should return a reference. Can it be a
const reference?
• What about this?
– void f(MyType &);
f(a = b); // Should this work?
Value Return of Classes
• What gets executed here?
– class A {
public:
A(int);
};
class B {
public:
B(const A &);
};
A f() { return 1; }
B b(f());
• Semantics same as initialization.
OPERATORS AND CONVERSIONS
Overloading
• Operators can also be overloaded.
– Complex c1(…), c2(…), c3;
c3 = c1 + c2;
• There are complicated rules for figuring out
which overloaded function to call.
• Why overload?
– Sometimes a particular operation, like finding the
maximum of two numbers, can have different
implementations depending on the actual types.
Operators
• Consider these operators defined in the context of two classes:
– class Point {
private:
double x, y;
};
class Vector {
private:
double x, y;
};
• These classes have exactly the same data members. Is there any
point in having two classes? Why not just make them the same?
– class Pair {
private:
double x, y;
};
• Does this code do what the author intended?
– Pair s1p(…); // Position of starship 1.
Pair s1v(…); // Velocity of starship 1.
double dt = …; // Elapsed time.
// Update starship position, assuming
// that dt seconds have passed since the
// last update.
s1p = s1p + dt*s1p;
• If the author had used separate classes for points
and vectors, would it have made any difference?
Equality (==)
• Equality
– inline bool operator==(const Point &p1,
const Point &p2) {
return p1.x == p2.x && p1.y == p2.y;
}
Inequality (!=)
• Inequality:
– inline bool operator!=(const Point &p1,
const Point &p2) {
return !(p1 == p2);
}
Addition (+)
• Point + point?
– Ill-defined.
• Point + double?
– Ill-defined.
• Point + vector?
– Point operator+(const Point &p,
const Vector &v) {
return Point(p.x + v.x, p.y + v.y);
}
• Vector + point?
– inline Point operator+(const Vector &v,
const Point &p) {
return p + v;
}
Multiplication (*)
•
Point*point?
– Ill-defined.
•
Point*double?
– Ill-defined.
•
double*vector?
– inline Vector operator*(const double s, const Vector &v) {
return Vector(s*v.x, s*v.y);
}
•
vector*double?
– inline Vector operator*(const Vector &v, const double s) {
return s*v;
}
•
•
vector*vector?
What do we do about cross-product?
– Can we just “borrow” some other operator to use for cross product, such as &&?
– Vector &operator&&(const Vector &v1, const Vector &v2);
Full declaration
• Code is:
– class Vector;
class Point;
Point operator+(const Point &, const Vector &);
class Vector {
friend Point operator+(const Point &,
const Vector &);
…
};
class Point {
friend Point operator+(const Point &,
const Vector &);
…
};
Index operator ([])
• Index
– class DynamicArray {
public:
double &operator[](size_t i);
double operator[](size_t i) const;
private:
double *const data;
const size_t length;
};
double &
DynamicArray::operator[](size_t i) {
return data[i];
}
Function call (())
• Functor: Object that behaves like a function.
– class Compare {
public:
bool operator()(int i, int j) {
return i < j;
}
};
Compare cmp;
if (cmp(1, 2)) { … } // If <.
• In C++, use functors (with virtual functions if needed)
where you would normally use function pointers.
• Also can do double-duty as a multidimensional index operator:
– class Array2 {
public:
double &operator()(int i, int j) {
return data[???];
}
private:
size_t n_cols;
double *data;
};
– return data[n_cols*i + j];
Member Access and Dereference
(-> and *)
• These are somewhat special. They allow a
class to behave like a pointer.
• Is there a way to solve memory leak problems
like below by using objects?
–{
MyClass *ptr = new MyClass;
ptr->my_method();
// Oops, memory leak.
}
•
Use a “smart pointer”:
– class MyClassPtr {
public:
MyClassPtr(MyClass *p) : ptr(p) {}
~MyClassPtr() { delete ptr; ptr = 0; }
MyClass *operator->() {
return ptr;
}
MyClass &operator*() {
return *ptr;
}
private:
MyClass *ptr;
};
{
MyClassPtr sp(new MyClass);
sp->my_method();
(*sp).my_method();
// What happens here?
}
•
This is not a robust version, just for example. It is similar std::auto_ptr.
• If the member access returns an object type, it will recurse:
– struct A {
int field1;
};
struct B {
A *operator->() {
return &a;
}
A a;
};
struct C {
B operator->() {
return B();
}
};
. . .
C c_obj = . . .;
c_obj->field1;
– (C_obj.operator->().operator->())->field1;
Left and Right Shift
(<< and >>)
• These are used primarily for output operators:
– void operator<<(ostream &os,
const Point &p) {
os << “(“
<< p.x << “, “
<< p.y << “, “
<< p.z << “)”;
}
• Given the above, will this work?
– Point p1(…), p2(…);
cout << p1 << p2 << endl;
Assignments
(*=)
• How do we make this work?
– Vector v(…);
double s = …;
v *= s; // What does this do, mathematically?
– Vector &operator*=(double s) {
this->x *= s;
this->y *= s;
return *this;
}
Increment (++) and
Decrement (--) Operators
• What is the value of i in these cases?
– int
int
– int
int
j
i
j
i
=
=
=
=
3;
++j;
3;
j++;
• The postfix and prefix operators are
distinguished with a hack.
– operator++(int); // Postfix
operator++(); // Prefix
•
How would you implement 128-bit unsigned integers?
– Int128 i, j1(1), j2(1);
i = j1++; // What should the value of i be?
i = ++j2; // What should the value of i be?
– class Int128 {
public:
Int128(uint64_t h = 0, uint64_t l = 0)
: m_high(h), m_low(l) {}
??? operator++() { // Prefix
if (++m_low == 0) {
m_high++;
}
return ???;
}
??? operator++(int) { // Postfix
if (++m_low == 0) {
m_high++;
}
return ???;
}
private:
uint64_t m_high, m_low;
};
– class Int128 {
public:
Int128(uint64_t h = 0, uint64_t l = 0)
: m_high(h), m_low(l) {}
inline Int128 &operator++(); // Prefix
inline Int128 operator++(int); // Postfix
private:
uint64_t m_high, m_low;
};
inline Int128 &
Int128::operator++() { //Prefix
if (++m_low == 0) {
m_high++;
}
return *this;
}
inline Int128
Int128::operator++(int) { // Postfix
uint64_t org_high = m_high, org_low = m_low;
this->operator++();
return Int128(org_high, org_low);
}
– Int128 &Int128::operator++() { //Prefix
if (++m_low == 0) {
m_high++;
}
return *this;
}
Int128 Int128::operator++(int) { // Postfix
uint64_t org_high = m_high, org_low = m_low;
this->operator++();
return Int128(org_high, org_low);
}
• Which is more efficient? How many temporaries are created?
– Int128 i, j1(1), j2(1);
i = j1++; // What should the value of i be?
i = ++j2; // What should the value of i be?
User-Defined Conversions
• Suppose we have our Int128 class.
– class Int128 { … };
• We’d like to use some function with this prototype:
– void foo(Int128 &);
• Can we do this?
– ...
foo(1234);
• Yes, since there is a constructor:
– Int128::Int128(uint64_t h = 0, uint64_t l = 0);
• So, like this, right?
– void foo(Int128 &);
…
foo(1234);
• Hm…what happens here?
– void foo(Int128 &i) {
...
i = j;
}
...
foo(1234);
• Must be const or rvalue reference.
– void foo(const Int128 &);
...
foo(1234);
– void foo(Int128 &&);
…
foo(5678);
• So we defined a conversion from int to Int128.
Can we go the other way?
– void foo2(int);
Int128 i;
...
foo2(i);
• Yes.
– class Int128 {
public:
operator int() const;
...
};
Int128::operator int() const {
... // Convert to int.
return result;
}
• Any conversion is possible.
– class A {
public:
const operator *my_struct();
operator double();
private:
my_struct a_struct;
};
const A::operator *my_struct() {
this->a_struct.field1 = 1.234;
this->a_struct.field2 = 4.567;
return &this->a_struct;
}
A::operator double() {
return 3.14;
}
– A a(…);
void f1(double);
void f2(const mystruct *);
f1(a);
f2(a);
• To force the use of a cast, use the explicit
keyword.
– class A {
public:
explicit const operator *my_struct();
operator double();
private:
my_struct a_struct;
};
– A a(…);
void f1(double);
void f2(const mystruct *);
f1(a);
f2(a); // Error.
f2(static_cast<const my_struct *>(a)); // OK.
• Especially important with a bool conversion.
– struct A {
operator bool() { ... }
...
};
...
A a;
int i = a; // Unintended, but compiles and runs.
...
struct B {
explicit operator bool() { ... }
...
};
int j = b; // Gives compile-time error.
...
if (a) { ... } // Works.
// Also works, because it’s a boolean context.
if (b) { ... }
• Conversion is still implicit if in boolean context.
• Replaces the “safe bool idiom” in C++98.
Member or friend?
•
Member or (friend/non-friend) free?
– Vector v1, v2;
v1 = v2*s;
– Vector operator*(const Vector &, double);
– Vector Vector::operator*(double) const;
– v1 = s*v2; // ?
•
Consider a complex number example.
– class Complex {
Complex(double real, double img = 0);
Complex operator*(const Complex &);
...
};
Complex c1 = 4*c2; // Syntax error.
– Complex operator*(const Complex &, const Complex &);
class Complex {
Complex(double real, double img = 0);
...
};
Complex c1 = 4*c2; // OK.
Temporaries
• Consider the addition operator for vectors:
– Vector
operator+(const Vector &v1, const Vector &v2) {
return Vector(v1.x + v2.x, v1.y + v2.y);
}
• In the expression below, how many temporaries are generated?
– v = v1 + v2 + v3;
• Any solution?
– Not in C++98, but move semantics in C++11 can help.
• What is the lifetime of a temporary?
– struct A {
A(int);
void method();
};
void foo1(const A &);
A foo2();
foo1(1); // A ref is passed to foo().
foo2().method(); // Call a method on temp?
– const A &ar(foo2());
ar.method(); // Okay??
Summary
• Cannot be overloaded:
–
–
–
–
–
–
–
?: (conditional)
. (member selection)
.* (member selection with pointer-to-member)
:: (scope resolution)
sizeof (object size information)
typeid (object type information)
Cast operators: (type), static_cast, dynamic_cast,
reinterpret_cast, const_cast
• Must be member function:
–
–
–
–
= (assignment)
() (function call)
[] (subscripting)
-> (member access)
• If something already has a clearly defined meaning, then
you can’t overload it.
–
–
–
–
–
int operator&&(int, int); // Okay?
int operator&&(MyClass a, int); // Okay?
int operator&&(MyClass *ap, int); // Okay?
int operator&&(MyClass &a, int); // Okay?
enum Foo { RED, GREEN, BLUE };
int operator&&(Foo, int); // Okay?
Special Values
• Suppose you had a smart pointer class. How
would you check it for being null?
• Suppose you had a time class. How would you
get the current time?
• [Show special_ values]
• Comparison against zero could use a regular object with zero value:
– class Time { static Time zero; };
if (t == Time::zero) {…}
• Or it could use a tag struct. In this case, any object of the type
means zero.
– class ZeroTime {} zero_time;
if (t == zero_time) { ... }
• Or could overload comparison to int:
– if (t == 0) { ... }
• But in this case it would still be called, even if it was 1234 instead
of 0.
• Can get now time by a static function.
– Time t = Time::now();
• Or can create a set-to-now member function:
– t.setToNow();
INHERITANCE
Inheritance
• A class may be derived from (inherit from) another class. The
class that is derived from is the base class.
– Which is more general, the base class or the derived class?
– Why inherit? What do we gain by adding inheritance to a language?
What would we lose if we took it out?
• Main thing is layered abstraction. Consider a hierarchy of animals,
including felines, canines, and mammals. Code that doesn’t care if it is a
dog or cat can deal with just mammals.
• Inheritance defines what we call the Is-A relationship.
Mammal
Cat
Dog
Open-Closed Principle
• Software should be open for extension, closed
to modification.
– Hard to accomplish in practice.
Liskov Substitution Principle (LSP)
If D is a subtype of B,
- then objects of type B can be replaced everywhere with
objects of type D,
- without impacting any of the desired properties of the
program.
• In other words,
– if D derives from B,
• you should be able to replace objects of type B
everywhere with objects of type D,
• and nothing will “go wrong”.
• So using derived type object should still work.
– void do_something(B *);
B b;
do_something(&b);
D d; // D derives from B.
do_something(&d);
• A rectangle has four lines, each angle is 90 degrees.
• A square has four lines, each of the same length.
– Each angle is 90 degrees.
• Is a square a rectangle?
• Then to model this, we should derive square from
rectangle:
– class Square : public Rectangle {
// …
};
• Should this work?
– Rectangle rect;
Square sq;
void do_something(Rectangle *r);
do_something(&rect);
do_something(&sq);
• Consider:
– class Rectangle {
public:
void setWidth(double x);
void setHeight(double y);
// ...
};
– void do_something(Rectangle *r) {
r->setWidth(10);
r->setHeight(5);
// ...
}
Rectangle rect;
do_something(&rect);
– class Square : public Rectangle { /* ... */ };
Square sq;
do_something(&sq);
• Ways to resolve:
– Changing either width or height of a square
changes the other.
– A Square object is not a Rectangle object.
– Don’t use mutators. (Use a FP style.)
– Allow object to change type.
Flat or Deep?
• Should a checking account and a savings
account use separate classes or the same
classes?
– Checking is positive fee, zero interest.
– Savings is zero fee, non-negative interest.
• Student and staff?
• Generally flat is preferred.
Defining the Hierarchy
• To inherit:
– class B {
// Accessible to derived classes.
protected:
int i;
private:
int j;
};
class A : public B { … };
void A::some_func() {
i; // Allowed.
j; // Error.
}
• To prevent inheritance, use final keyword (C++11).
– class A final {
/* … */
};
class B : public A {// Syntax error.
/* … */
};
• Can also have protected and private inheritance.
– class Derived : protected Base { /* … */ };
– class Derived : private Base { /* … */ };
Sub-objects
• An instance of derived class contains the members
from the base class as what we call subobjects.
– class A {…};
class B : public A {…};
class C : public B {…};
A part
B part
C part
Inheriting
• A derived class can access data members in base
classes, if given protected access.
• A member function defined in a base class is
automatically inherited by the derived class.
– class Base {
public:
void func();
};
class Derived : public Base {};
Derived d;
d.func(); // Calls Base::func().
Hiding
• Consider:
– class B {
public:
void func();
};
class A : public B {
public:
void func();
};
A a;
a.func(); // Calls which?
• A function that is defined in the derived class hides the same function
defined in the base class.
• How to call the B version?
– // Use resolution operator to call base class.
a.B::func();
• Which ones are called?
– struct Base {
void func(double);
void func(int);
};
struct Derived : public Base {
void func(int);
};
Derived d;
d.func(1234); // Which does this call?
d.func(12.34); // Which does this call?
• Which ones are called?
– struct Base {
void func(double);
void func(int);
};
struct Derived : public Base {
void func(int);
private:
void func(double);
};
Derived d;
d.func(12.34); // Which does this call?
• Normally, there is no overloading of hidden names. Can get this via
“using”.
– struct Base {
void func(double);
void func(int);
void func(const char *);
};
struct Derived : public Base {
using Base::func;
void func(int);
private:
void func(const char *);
};
Derived d;
d.func(1234); // Which does this call?
d.func(1.23); // Which does this call?
d.func(“hello”);
• Note derived class still gets precedence if declared in both.
•
•
[Show using_overloading.]
This code compiles on g++, gives ambiguity error on clang++:
– #include <iostream>
struct B {
void func(double) { std::cout << "B::func(double)" << std::endl; }
void func(int) { std::cout << "B::func(int)" << std::endl; }
};
struct D1 : public B {
void func(double) { std::cout << "D1::func(double)" << std::endl; }
};
struct D2 : public D1 {
using B::func;
using D1::func;
void func(int) { std::cout << "D2::func(int)" << std::endl; }
};
int main() {
D2 d2;
d2.func(1);
d2.func(1.0);
}
• All base overloads must be accessible to derived
class.
– struct Base {
void func(double);
protected:
void func();
private:
void func(int);
};
struct Derived : public Base {
using Base::func;
void func(int);
};
• Access is determined by the point at which the using
declaration occurs:
– struct Base {
void func(double);
protected:
void func();
};
struct Derived : public Base {
private:
using Base::func;
public:
void func(int);
};
derived.func(1.1); // Compile-time error.
Construction
• A derived object has a sub-object that is a instance of the base
class.
– When does the sub-object constructed?
• Which should be constructed first?
• Generally speaking, it makes more sense to construct the base class
first.
– class Base {
protected:
Base();
};
class Derived : public Base {
public:
Derived();
};
Derived d;
• Consider:
– class Base {
protected:
Base(int);
};
class Derived : public Base {
public:
Derived() { … }
};
• Will it compile?
• Calling constructor of base classes.
– If we wish to call a non-default constructor, use a
constructor initialization list:
– class B {
public:
B(int);
};
class Derived : public B {
public:
Derived();
private:
B b;
};
Derived::Derived() : B(123), b(456) {}
– struct A {
A(int, int);
A(const char *);
};
struct B : public A {
B();
A a;
};
B::B() : A(1, 2), a(“a”) {…}
Inheriting Constructors (C++11)
• Constructors can be inherited in C++11.
– struct Base {
Base(int);
};
struct Derived : public Base {
using Base::Base;
};
Derived d(1);
Destructors
• Destructors of base classes are called.
• What order should destructors be called?
– class Base {
public:
~Base();
};
class Derived : public Base {
public:
~Derived();
};
Polymorphism
• What does the word literally mean?
• What does it mean in terms of C++?
Virtual Functions
• A virtual function is one that when you call it through a pointer or a
reference to a base class, calls the implementation in the most
derived class.
– class Base {
public:
virtual void foo() { printf(“Base\n”); }
};
class Derived : public Base {
public:
virtual void foo() { printf(“Derived\n”); }
};
Derived d;
Base b;
Base &br_d(d), &br_b(b), *bp = 0;
bp = &b;
bp->foo();
bp = &d;
bp->foo();
br_d.foo();
br_b.foo();
• Do we need the virtual in the derived class?
– class Base {
public:
virtual void foo1();
void foo2();
};
class Derived : public Base {
public:
/* virtual */ void foo1();
void foo2();
}
• Which functions get called?
– class A {
public:
void foo();
};
class B : public
public:
virtual void
};
class C : public
public:
virtual void
};
C c;
A *ap = &c;
B *bp = &c;
ap->foo();
bp->foo();
bp->A::foo();
c.B::foo();
A {
foo();
B {
foo();
• What happens here?
– class Base {
public:
virtual void foo();
};
class Derived : public Base {
private:
void foo();
};
Derived d;
Base &br(d);
br.foo();
• As a thought experiment, let’s say that we wanted to
disallow this. Is this practical/wise?
•
Not all overloads of a function must be virtual:
– class Base {
public:
virtual void foo(int);
void foo(double);
void foo(const char *);
};
class Derived : public Base {
public:
void foo(int);
void foo(double);
void foo();
};
Derived d;
Base &br(d);
br.foo(1);
br.foo(1.1);
br.foo(“hello”);
br.foo();
d.foo(1);
d.foo(1.1);
d.foo();
d.foo(“hello”);
•
Such code is unlikely to be a good idea, but it may happen unintentionally.
Virtual and using declaration
• using declarations still result in dynamic dispatch.
– struct Base {
virtual void func(double);
};
struct Derived1 : public Base {
private:
virtual void func(double);
};
struct Derived2 : public Derived1 {
using Derived1::func;
Base::func;
void func(int);
};
int main() {
Derived2 d2;
d2.func(1.0);
}
Operators Can Be Virtual
• Recall that operators are just functions. So they can be virtual:
– struct Log {
virtual Log &operator<<(const char *);
};
struct RemoteLog : public Log {
virtual Log &operator<<(const char *) override;
};
void emergency(Log &l) {
l << “Computer on fire!”;
}
Forcing/Preventing Overriding (C++11)
• To flag an error when you intend to override, but actually aren’t, use the
override keyword.
– struct Base {
virtual void foo(int);
};
struct Derived : public Base {
virtual void foo(double) override;
};
– Without override, the above would compile.
• To prevent overriding, use the final keyword.
– struct Base {
virtual void foo(int) final;
void goo() final;
};
struct Derived : public Base {
virtual void foo(int); // Syntax error.
void goo(); // Syntax error.
};
Virtual Destructors
• Will this do the right thing?
– Base *b = new Derived;
delete b;
• To cause the destructor for the derived class to be called, use
a virtual destructor:
– class Base {
public:
virtual ~Base() {}
};
• You almost always want a virtual destructor if you have a
polymorphic class.
Default Arguments
• What default arguments will be used?
– class Base {
public:
virtual void foo(int i = 0);
};
class Derived : public Base {
public:
virtual void foo(int i = 1);
};
Derived d;
Base *b = &d;
b->foo(); // Will this pass one or zero?
Parameter-Based Virtual Dispatch
• Which output operator does this call?
– class Base { public: virtual ~Base(); … };
ostream &operator<<(ostream &os, const Base &) {
// Output for Base class.
}
class D : public Base { … };
ostream &operator<<(ostream &os, const D &) {
// Output for D class.
}
D d;
Base b, &br_d(d);
cout << b; // Which does this call?
cout << d; // Which does this call?
cout << br_d; // Which does this call?
• Problem is that C++ does virtual dispatch only
on the object type of the member function,
not on any parameters.
• Solution?
– [param_dispatch/]
– Turn it into a member function call.
• Redirected dispatch.
– ostream &operator<<(ostream &os, const Base &b) {
b.print(os);
return os;
}
class Base {
virtual void print(ostream &os); … };
class D : public Base {
virtual void print(ostream &os); … };
D d;
B b, &br_d(d);
cout << b; // Which does this call?
cout << br_d; // Which does this call?
Constructors and Virtual Functions
• What does this call?
– class Base {
Base();
virtual void helper();
};
class Derived : public Base {
virtual void helper();
};
Base::Base() {
// Does this call Derived::helper(), or
// Base::helper()?
this->helper();
…
}
– Hint: At the point of call, has the constructor for Derived been called
yet?
– Is it safe to call a method on an object that has not been constructed?
Pure Virtual Functions
• A base class can indicate that the class of any instantiated object
must override the function.
– struct Base {
virtual void f() = 0;
};
struct D1 : public Base { … };
struct D2 : public D1 {
virtual void f();
}
struct D3 : public D2 { … };
Base b; // Okay?
D1 d1; // Okay?
D2 d2; // Okay?
D3 d3; // Okay?
• Called an abstract class.
•
Is this allowed? What does it mean? Could the implementation ever be called?
– struct Base {
virtual void f() = 0;
};
// An implementation of a pure virtual function.
void Base::f() {…}
•
Used to provide helper functions.
– void Derived::f() {
// Call base class version first.
this->Base::f();
…
}
•
Note that calling PVF from base is undefined behavior.
– Base::Base() {
f(); // Tries to calls Base::f() during construction.
}
• Can you have a pure virtual destructor? What
does it mean? Why?
– class Base {
public:
// Can I do this?
virtual ~Base() = 0;
};
// Can I do this?
Base::~Base() { … }
• Summary:
– A pure virtual function does NOT mean that you
didn’t define it.
– But you can never instantiate an class that does
not have all PVFs defined.
Cloning
• If you have a pointer to a derived type, it is
easy to make a copy of it:
– D *copy_of_d = new D(*d);
• What if you only have a base class pointer?
– B *bp = …; // Might point to a D.
How to make a copy of it?
• Need a clone function:
– B *copy = bp->clone();
Accessing Derived From Base
• What if you want to have a base class function access
derived class information, kind of like this?
– class Base {
public: void func() {
printf(“%d\n”, m_color); }
};
class D1 : public Base {
public:
const int m_color;
};
class D2 : public Base {
public:
const int m_color;
};
– Obviously no way to access a derived class data member.
What we really want to access is information, though.
•
Need to pass to base class ctor, or use a virtual function.
– class Base {
public:
Base(int color) : m_color(color) {}
void func1() { printf(“%d\n”, m_color); }
void func2() { printf(“%d\n”, color()); }
virtual int color() const = 0;
private:
const int m_color;
};
class D1 : public Base {
public:
D1() : Base(1) {}
virtual int color() const { return 1; }
};
class D2 : public Base {
public:
D2() : Base(2) {}
virtual int color() const { return 2; }
};
•
•
Which one is more efficient?
Which one is less error-prone?
• Can get efficiency and robustness this way:
– class Base {
public:
Base() : m_color(color()) {}
virtual int color() const = 0;
private:
const int m_color;
};
class D1 : public Base {
public:
D1() = default;
virtual int color() const { return 1; }
};
class D2 : public Base {
public:
D2() = default;
virtual int color() const { return 2; }
};
– Well, not really. The derived type has not been constructed yet, so this
is undefined behavior.
•
Could also be a reference:
– struct E { virtual ~E() = default; ... };
struct E1 : public E { ... };
struct E2 : public E { ... }
struct Base {
Base(E &e) : m_e(e) { m_e.some_method(); } // Okay?
void func() { m_e.some_method(); } // Okay?
E &m_e;
};
struct D1 : public Base {
D1() : Base(m_e1) {}
E1 m_e1;
};
struct D2 : public Base {
D2() : Base(m_e2) {}
E2 m_e2;
};
(Co|Contra|In)variance
• Let’s say that we have class Animal and a
class Dog. Dog derives from Animal.
• Is the Dog class a subtype of the Animal
class?
• Does this code compile?
– Dog d[10];
void foo(Animal *);
...
foo(d);
• Should it?
• Problem?
– Dog d[10];
void foo(Animal *ap) {
ap[2].some_method();
...
}
foo(d);
• Should an array of Dog objects be a subtype
of an array of Animal objects?
• Covariance:
– If B is a subtype of A, then a type composed from
B is a subtype of the same composition based on
A.
• Contravariance:
– If B is a subtype of A, then a type composed from
B is a supertype of the same composition based
on A.
• Invariance:
– If B is a subtype of A, then a type composed
composed from B is completely unrelated to the
type of the same composition based on A.
• How about this?
– Dog *d[10];
void foo(Animal **ap) {
ap[2]->some_method();
...
}
foo(d);
• Should an array of Dog * be a subtype of an
array of Animal *?
• How about this?
– void foo(vector<Animal *> &);
vector<Dog *> d;
... // Populate d.
foo(d);
• So here’s the implementation of foo().
– void foo(vector<Animal *> &v) {
v.push_back(new Cat;);
}
• How about this?
– void foo2(const vector<Animal *> &);
vector<Dog *> d;
... // Populate d.
foo2(d);
• How about this?
– Animal *get_animal();
void foo2(Dog *(*func)());
...
foo2(&get_animal);
• How about this?
– Dog *get_dog();
void foo(Animal *(*func)());
...
foo(&get_dog);
• How about this?
– void addAnimal(Animal *);
void foo2(void (*func)(Cat *));
…
foo2(&addAnimal);
• How about this?
– void addCat(Cat *);
void foo(void (*func)(Animal *));
…
foo(&addCat);
• Is this okay?
– class Base {
public:
virtual double func();
...
};
class Derived : public Base {
public:
virtual int func();
};
• Suppose you have a class hierarchy. What should
the return type of clone() be?
– struct B {
virtual ??? *clone() const;
};
struct D : public B {
virtual ??? *clone() const;
}
– struct Animal {
virtual Group *getGroup() const;
};
struct Bird : public Animal {
virtual Flock *getGroup() const;
};
struct Flock : public Group { ... };
•
What about parameters?
– struct X { … };
struct Y : public X { … };
struct Z : public X { … };
struct A {
virtual void foo1(X
virtual void foo2(Y
};
struct B : public A {
virtual void foo1(Y
Virtual void foo2(X
};
…
X x;
Y y;
Z z;
B b;
A &ar(b);
ar.foo1(&x); // ?
ar.foo1(&y); // ?
ar.foo1(&z); // ?
ar.foo2(&x); // ?
ar.foo2(&y); // ?
ar.foo2(&z); // ?
*);
*);
*); // Safe?
*); // Safe?
• C++ does not support contravariance of
parameter types in overridden virtual
functions.
Mutable
Immutable
Pointers-toArrays/Vectors Arrays/Vectors Members
Return
Types
Parameters
Type-safety
Invariant
Covariant
Contravariant
Covariant
Contravariant
C++ support
Partial
No
Yes
Partial
No
Missing vtable/typeinfo Errors
•
Caused by missing definitions of virtual functions.
– $ cat foo.cpp
class A {
public:
virtual void foo() const {}
};
class B : public A {
public:
virtual void foo() const;
};
int
main() {
B b;
}
$ g++ foo.cpp
/tmp/ccg3JJkc.o: In function `B::B()':
foo.cpp:(.text._ZN1BC1Ev[B::B()]+0x1c): undefined reference to
`vtable for B‘
collect2: ld returned 1 exit status
Efficiency
• Are virtual functions slow?
• If you don’t use a virtual function, you almost always
need an if-statement anyway.
– // Do some prior computation to set-up
// the if-test.
if (…) {
foo->do_version_A();
} else {
foo->do_version_B();
}
– Versus:
foo->do_it();
• [Show cost_of_virt.]
• Virtual call:
– for (int i = 0; i < N; i++) {
a[i]->foo();
}
• Non-virtual (regular) call:
– for (int i = 0; i < N; i++) {
switch (a[i]->type);
case Base_nv::D1:
static_cast<D1_nv *>(a[i])->foo();
break;
case Base_nv::D2:
static_cast<D2_nv *>(a[i])->foo();
break;
}
}
• Inlined:
– for (int i = 0; i < N; i++) {
switch (a[i]->type);
case Base_nv::D1:
static_cast<D1_nv *>(a[i])->inline_foo();
break;
case Base_nv::D2:
static_cast<D2_nv *>(a[i])->inline_foo();
break;
}
}
Derivation for Implementation
• Suppose a car has an engine. You need an engine in your car.
– Also, engines need a start() method, but also you want a start()
method on your car.
• So you could do this, and automatically get your start method.
– class Engine {
public:
void start();
…
};
class Car : public Engine {
public:
// Get the start() method for free.
…
};
• Does this obey the LSP?
– Probably not. But you can fix by using private inheritance.
– Or, just don’t do it. Use composition/aggregation.
• class Car {
private:
Engine engine;
};
Private and Protected Inheritance
• To derive for implementation, use private or protected
inheritance:
– // All in
class A :
– // All in
class A :
B are private now.
private B { … };
B is protected now.
protected B { … };
• Can also selectively make more or less restrictive.
– class B {
void priv_func();
public:
void foo();
};
class A : public B {
private:
using B::foo; // Make B::foo private.
};
class A2 : private B {
public:
using B::foo; // Make B::foo public.
};
• Also, something that is not publically inherited will not be
automatically converted to base class pointer or reference:
– class Base { ... };
class Derived_priv : private Base {
...
};
class Derived_pub: public Base {
...
};
void foo(Base &);
Derived_priv dpriv;
Derived_pub dpub;
foo(dpriv); // Syntax error.
foo(dpub); // Okay.
Interfaces vs. Classes
• What is the difference between an interface
and a class?
• In common OOP usage:
– Interface: What the methods are named, the
parameters they take, return types, and the
semantics.
– Class: The implementation of the interface, the
actual data members, method implementation
code, etc.
• Does Java support polymorphism/virtual-functions?
1. A Java interface cannot be instantiated, any C++ class with a nonoverridden pure virtual function cannot be instantiated.
2. All Java methods are polymorphic. In C++, only virtual functions are
polymorphic.
3. In C++, individual functions can be specified as part of the interface, by
making them pure virtual. In Java, it is all (interface), or none (class).
• Does Java have interfaces? Does C++ have interfaces?
• In C++, there is greater ability to mix and match the features
of interfaces and classes, so interface is somewhat implicit.
– Virtual functions and abstract base classes can be used to make them
more explicit.
– A class with just pure virtual functions and no data members is
essentially an interface.
• Note that Java abstract base class has some relationship.
• Example:
1. You properly separate interface from class.
2. You create an interface.
– Java: Use interface keyword.
– C++: Make all functions pure virtual and make the class have no data
members.
3. Create 4 classes that implement the interface.
4. You notice that all 4 classes have the same implementation of a
particular function.
5. What do you do?
– Java: Create a new base class that implements the interface.
– C++: Move the function into the interface class as non-pure virtual
function.
– In C++, the decision as to whether or not a particular function
is part of the interface or implementation (class) is made on a
function-by-function basis.
• Java:
– interface I {
// Everything in here is part of interface.
…
};
– class A implements I {
// Everything here is part of the implementation.
…
};
• C++
– class Base {
public:
virtual f1() = 0; // Part of interface.
virtual f2() = 0; // Part of interface.
void common_func(); // Part of interface AND
// implementation. All
// classes share the same
// implementation, so make it
// non-virtual.
…
};
• What is the interface of this class?
– struct A {
void f(int);
};
• Do these two classes have the same interface?
– struct
void
};
struct
void
};
D1 {
f(int);
D2 {
f(int);
• Do E1 and E2 have the same interface?
– struct Interface {
virtual void f(int) = 0;
;
struct E1 : public Interface {
virtual void f(int) { … }
};
struct E2 : public Interface {
virtual void f(int) { … }
};
• When we use the word ‘interface’, we
usually mean to include semantics. But
the programming language only enforces
syntactic.
• Program to the interface, not to the
implementation.
Fragile Base Class
• Often, seemingly safe changes to a base class
cause things to break in the derived classes.
• Example:
• Someone in your company, but in a different division, writes a string
class.
– class String {
public:
virtual void append(char);
void length() const {
return strlen(buf);
}
protected:
char *buf;
};
• Your boss says that your app runs too slow. You look into, and
discover that the length() function is taking 90% of the time.
– You don’t control the String class. The author, Joe, is unresponsive
because the app for his division runs fine.
– What do you do?
•
•
•
•
Steal Joe’s office chair and hold it hostage till he fixes String.
Tell your boss that you need to buy faster computers.
Tell your boss that you need to create your own standalone String class.
Derive an optimized version from String.
• You make it more efficient for length:
– class String2 : public String {
public:
virtual void append(char) {
m_length++;
this->String::append(c);
}
void length() const {
return m_length;
}
private:
int m_length;
};
• Good? Obeys LSP?
– void foo(String *s);
String2 s;
foo(&s); // Okay?
s.length();
• Joe decides to add a convenience function to allow the user to
append a complete string at once.
– class String {
public:
virtual void append(char);
void append(const char *str) {
for (int i = 0; i < strlen(str);
i++) {
this->append(str[i]);
}
}
void length() const {
return strlen(buf);
}
private:
char *buf;
};
• Okay?
– Cannot call append(const char *) on String2 object (without
a using declaration in String2), but that won’t break your existing code.
• Joe decides that it is much faster to append the complete
string at once.
– class String {
public:
virtual void append(char);
void append(const char *str) {
strcat(buf, str);
}
void length() const {
return strlen(buf);
}
protected:
char *buf;
};
• Does this still obey LSP?
Dynamic Type vs Static Type
• Static type: What something is declared as,
statically.
• Dynamic type: What something actually is (i.e.,
the most derived type).
– class A { … };
class B1 : public A { … };
class B2 : public A { … };
A *ap = …;
// Static type of *ap is A, but the
// dynamic type is not known at
// compile time.
(*ap).foo();
• In general, C++ is a statically-typed language.
Dynamic typing is enabled by polymorphism.
– struct A {
virtual void foo();
};
struct B : public A {
virtual void foo();
};
B b;
A *ap = &b;
(*ap).foo();
Run-Time Type Identification (RTTI)
• Sometimes you need to know the actual type
of an object, when you have just a pointer to
the base class.
• How do you do inheritance in C?
• Inheritance in C:
– struct A {
int a_member; };
struct B1 {
struct A A_sub;
int b1_member; };
struct B2 {
struct A A_sub;
int b2_member; };
• Upcasting and downcasting:
– struct B1 b1;
B1_ctor(&b1);
A *ap = (A *)
B1 *b1p = (B1
A *ap = …; //
B2 *b2p = (B2
&b1; // Upcast
*) ap; // Downcast
Pointer to A obtained somehow.
*) ap; // Safe?
• Inheritance in C:
– struct A {
int a_member; };
struct B1 {
struct A A_sub;
int b1_member; };
struct B2 {
struct A A_sub;
int b2_member; };
• How do we be safe? Try to make sure of type.
– A *ap = …; // Pointer to A obtained somehow.
if (/* ap is really a B1 */) {
B1 *b1 = (B1 *) ap;
// Do something with b1 that is B1 specific.
} else if (/* ap is really a B2 */) {
B2 *b2 = (B2 *) ap;
// Do something with b2 that is B2 specific.
}
• Use type ID of some kind.
– struct A {
enum { T_B1, T_B2 } id;
int a_member; };
struct B1 {
struct A A_sub;
int b1_member; };
struct B2 {
struct A A_sub;
int b2_member; };
• Check ID before downcast.
– A *a = …; // Pointer to A
if (a->id == T_B1) {
B1 *b1 = (B1 *) a;
// Do something with b1
} else if (a->id == T_B2)
B2 *b2 = (B2 *) a;
// Do something with b2
}
obtained somehow.
that is B1 specific.
{
that is B2 specific.
• Error prone: where is the ID set?
– struct A {
enum { B1_T, B2_T } id;
…
};
struct B1 {
struct A A_sub; };
struct B2 {
struct A A_sub;
};
B1 b1; // No constructor
b1.A_sub.id = B1_T;
• If using C++, can do it in the constructor.
– struct A {
const enum { B1_T, B2_T } id;
A(enum Id i) : id(i) {}
…
};
struct B1 {
B1() : A_sub(B1_T) {}
struct A A_sub; };
struct B2 {
B2() : A_sub(B2_T) {}
struct A A_sub;
};
B1 b1;
• What are more idiomatic C++ solutions?
• What does this do?
– struct A { virtual ~A() {} };
struct B1 : public A { … };
struct B2 : public A { … };
B1 b;
A *a = &b;
B2 *bp = dynamic_cast<B2 *>(a);
bp == ??; // What is the value of bp?
• Can use dynamic casting.
– dynamic_cast downcast only works on
polymorphic types.
• Can also use RTTI:
– #include <typeinfo>
struct A { virtual ~A() {} };
struct B1 : public A { … };
struct B2 : public A { … };
B1 b;
A *a = &b;
if (typeid(*a) == typeid(B1)) {
…
} else if (typeid(*a) == typeid(B2)) {
…
} else if (typeid(*a) == typeid(B3)) {
…
}
• The typeid operator returns a reference to
an object of class type_info.
• The type_info object has a string name
that can sometimes be helpful for debugging.
– struct A { virtual ~A() {} };
struct B1 : public A { … };
struct B2 : public A { … };
B1 b;
A *a = &b;
cout << typeid(*a).name() << endl;
•
There is no standard meaning for the string, but usually it’s meaningful and usually
it can be decoded. In g++, you can demangle by doing:
– #include <cxxabi.h>
#include <typeinfo>
#include <stdlib.h>
class A {
public:
virtual ~A () {}
};
class B : public A { };
int main() {
B b;
A *ap = &b;
int ec;
const char *demangled_name
= abi::__cxa_demangle(typeid(*ap).name(), 0, 0, &ec);
printf("%s\n", demangled_name);
free((void *) demangled_name);
}
• Is this efficient?
– A *a = …; // Obtained somehow.
if (typeid(*a) == typeid(B1)) {
…
} else if (typeid(*a) == typeid(B2)) {
…
} else if (typeid(*a) == typeid(B3)) {
…
} … {
} else if (typeid(*a) == typeid(B100)) {
…
}
• Solution?
• You could push the code into the object:
– // Original version.
if (typeid(*a) == typeid(B1)) {
// Some code to do XYZ.
} else if (typeid(*a) == typeid(B2)) {
// Some code to do ABC.
}
– // Code moved into a virtual function in the
// object.
virtual void B1::doit() {
// Code to do XYZ.
}
virtual void B2::doit() {
// Code to do ABC.
}
…
a->doit(); // Outside of the object.
• Disadvantage?
– Intrusive, however.
• The problem is to efficiently map from the type
to the code that should be executed for that type.
– struct Code {
virtual ~Code() = default;
};
struct Code_A {
virtual void operator()(A *) const = 0;
};
struct Code_A_code1 : public Code_A {
virtual void operator()(A *) const {
// Do something specific.
}
};
map<const type_info *, Code *> type_map;
Code &code = *type_map.lookup(&typeid(*a));
dynamic_cast<Code_A &>(code)(a);
– Okay?
• In order to efficiently store type_info in a
map, what operation do we need?
– The type_info object has before() method.
• Use the before() method to create a
comparator object.
– struct Cmp {
bool operator()(const type_info *ti1,
const type_info *ti2) {
return ti1->before(*ti2);
};
map<const type_info *, Code *, Cmp> type_map;
Code &code = *type_map.lookup(&typeid(*a));
code(a);
• type_info objects do not have a copy constructor nor an
assignment operator.
• This will fail:
– map<type_info, SomeType> table;
•
In C++11, can use type_index, which is a convenience wrapper.
– #include
#include
#include
#include
#include
<typeindex>
<typeinfo>
<map>
<string>
<iostream>
using namespace std;
int
main() {
map<type_index, string> table;
table.insert(make_pair(type_index(typeid(int)),
"It's an int."));
table.insert(make_pair(type_index(typeid(double)),
"It's a double."));
table.insert(make_pair(type_index(typeid(char)),
"It's an char."));
cout << table.find(typeid(int))->second << endl;
cout << table.find(typeid(double))->second << endl;
cout << table.find(typeid(char))->second << endl;
}
• Can also use the hash code, for hash tables
(C++11):
– size_t type_info::hash_code();
Object Slicing
• The derived part of objects is sliced off when used non-polymorphically.
• May not be avoidable, be aware!
– struct Base {
~Base();
virtual void method();
};
struct Derived : public Base {
~Derived();
virtual void method();
};
Derived *dp = new Derived;
Base *bp = dp;
delete bp; // Calls?
• What about this?
– struct Base {
virtual void method();
};
struct Derived : public Base {
virtual void method();
};
Derived d;
void foo(Base b) {
b.method();
}
foo(d); // Calls which method()?
• What happens here?
– struct Base {
// …
int base_var;
};
struct Derived : public Base {
// …
int derived_var;
};
int main() {
Derived d1(…), d2(…);
Base &b1_ref(d1), &b2_ref(d2);
b1_ref = b2_ref;
}
• Solution?
• No great solution. RTTI seems to be the best choice.
– struct Base {
Base(int b) : base_var(b) {}
virtual Base &operator=(const Base &) = 0;
int base_var;
};
struct Derived : public Base {
Derived(int b, int d) : Base(b), derived_var(d) {}
virtual Derived &operator=(const Base &);
Derived &operator=(const Derived &);
int derived_var;
};
Derived &Derived::operator=(const Base &o) {
return this->operator=(dynamic_cast<Derived &>(o));
}
int main() {
Derived d1(1, 2), d2(3, 4);
Base &b1_ref(d1), &b2_ref(d2);
b1_ref = b2_ref;
}
Forward and Backwards Compatibility
• What do they mean?
• Suppose we are writing a web browser. Should it be able to
read in old versions of HTML?
– How to ensure?
• Suppose you are writing a web browser. Should the browser
be able to handle future versions of HTML?
– How do we ensure this?
• Forward compatibility: The ability of an application to accept
future versions of input.
• Backward compatibility: The ability of an application to accept
previous versions of input.
• Which is harder?
ABI (Application Binary Interface) vs.
API
• Consider a module within an application.
– You design the module interfaces carefully.
– Version 2, implementation changes, but not the
interfaces.
• Does the rest of the application need to be modified?
• Does it need to be recompiled?
– Why does this matter?
• Original:
– class A {
public:
void foo();
private:
int i;
};
• Modified:
– class A {
public:
void foo();
private:
int i, j;
};
• Client code:
– A a;
• Recompile?
•
Original:
– class A {
public:
void foo();
private:
int i;
};
•
Modified:
– class A {
public:
void foo();
void foo2();
private:
int i;
};
•
Client code:
– A a;
a.foo();
•
Recompile?
•
Original:
– class A {
public:
virtual void foo();
private:
int i;
};
•
Modified:
– class A {
public:
virtual void foo();
virtual void foo2();
private:
int i;
};
•
Client code:
– A a;
a.foo();
•
Recompile?
• Original:
– void A::foo() {
printf(“%d\n”, 1234);
}
• Modified:
– void A::foo() {
printf(“%d\n”, 5678);
}
• Client code:
– A a;
a.foo();
• Recompile?
• In general:
– Header file change  recompile
– Implementation file change  recompile
– Basically, this is what the standard states.
×
• However...more specifically:
– Existing machine code breaks  recompile.
– Existing machine code doesn’t break  recompile.
– Platform dependent, NO GUARANTEES.
×
• Is Node v2 backwards binary compatible with v1?
– struct Node {
char version;
double x;
int i;
int p1, p2, p3; // Padding for extensibility.
};
struct Node { // v2
char version;
double x;
int i;
double y;
};
• [See /usr/include/gtk-2.0/gtk/gtkwindow.h]
• Can also be achieved with wrappers (PImpl idiom).
– // A.hpp
class Aimpl;
class A {
public:
void method1();
private:
Aimpl *impl;
};
– // A.cpp
void A::method1() { impl->method1(); }
– // Aimpl.hpp
class Aimpl { … };
– What does a client need to include?
#include “A.hpp”
#include “Aimpl.hpp” // Needed?
– Modify A.cpp:
• Recompile rest of program?
– Modify Aimpl.hpp:
• Recompile A.cpp?
• Recompile rest of the program?
• Binary compatibility is important in these
situations:
– Large application with plug-ins/modules/extensions:
• Want to ship bug fixes/new versions to customers.
• With no binary compatibility, what happens? With binary
compatibility?
– Designing an OS:
• When you upgrade the OS, what happens to apps?
– Libs and dlls:
• What happens if there is a bug in the C library on Windows
or Linux?
• Binary compatibility is guaranteed by adhering to
an ABI (Application Binary Interface).
check makeup time
• What about linking?
– Not an issue as long as run-time linking is used.
TYPES
Declarations
• Declarations associate a name with a type.
• A declaration does not actually allocate
storage, while a definition does.
• For any given variable or function, there must
be only a single definition, but there may be
multiple declarations. (One Definition Rule)
Names
• Maximum length is implementation-defined.
• Do not use leading underscores or double
underscores.
– Do not use _DEBUG. Why not?
• Rule of Thumb: Short names in short scopes.
Long names in long scopes.
Booleans
• bool
• Two values: true or false
– What is relation of truthiness to numerical and pointer values?
• // What values do they get?
int i = true, j = false;
• if (10) { ... } else { ... }
if (-10) { ... } else { ... }
if (0) { ... } else { ... }
if (0.0) { ... } else { ... }
int *a = ...;
if (a) { ... } else { ... }
if ("") { ... } else { ... }
• true has the value 1, false value 0.
• Non-zero is true, 0 is false.
• Floating point 0.0 is also false.
• Non-null pointer is true, otherwise false.
• The type of the string literal (“”) is an array, but it decays to a pointer to the beginning of
the literal. Since it is non-null, it is true.
Character Types
• char holds a character of the implementation’s character set.
• sizeof(char) is defined to be 1.
– What if a character takes 12 bits? Does sizeof a char return 1.5?
• May be signed or unsigned, depending on implementation.
– char c = 0;
c = c – 1;
// Output below depends on signedness of char.
printf("%d\n", int(c));
• If you need something specific, can specify it.
– signed char c = 0;
c = c – 1;
printf(“%d\n”, (int) c); // Always -1.
– unsigned char c = 0;
c = c – 1;
cout << int(c) << endl; // Always 255.
• 'a' is a character literal. 'abcd' is a multicharacter literal.
Integer Types
•
Integer types:
–
int, short, long, long long (usually 64-bit)
– signed, unsigned
•
Literals:
– 0xff, 123, 073, 123U, 1234L, 1234LL
– Note that there is no way to specify a literal short, but you can cast: short(1).
•
What does this print?
– #include <stdio.h>
int main() {
int i = 1000000;
printf("%d\n", (4000*i)/4000);
}
– Prints -73741.
– [Show overflow/]
•
•
Technically, overflow of signed integers is undefined. Commonly assumed to be benign, however.
If during the evaluation of an expression, the result is not mathematically defined or not in the range of
representable values for its type, the behavior is undefined, unless such an expression is a constant expression
(5.19), in which case the program is ill formed. [Note: most existing implementations of C++ ignore integer
overflows. Treatment of division by zero, forming a remainder using a zero divisor, and all floating point
exceptions vary among machines, and is usually adjustable by a library function. ]
Floating-Point Types
• Floating point types:
– float, double (usually 8 bytes), long double (usually more
than 8 bytes)
• 3.14 (defaults to double), 1.23f, 3.4L
• float pi_f = 3.14f;
double pi_d = 3.14;
long double pi_l = 3.14L;
printf(“%f, %f\n”, pi_f, pi_d);
printf("%lf\n", pi_f);
printf("%lf\n", pi_l); // Okay?
printf("%Lf\n", pi_l); // Okay?
• Alignment is to 8, usually, for doubles.
• How are floating point numbers actually represented, in terms of
actual bits?
Type Aliases
• typedef:
– typedef char *foo;
– typedef long long int64;
– Syntax rule to remember is that the name of the
type goes where the name of the variable would
normally go.
• Alias declaration (additional functionality with
templates) (C++11):
– using foo = char *;
– using int64 = long long;
• Can be used to define types for arrays:
– typedef int array_t[5];
using array2_t = int [5];
– The length is part of the type.
• Can also be used define function types and
function pointer types.
– typedef int f(double);
using fp = int (*)(double);
int func(double);
f foo; // What does this do?
foo = func; // Okay?
fp foo2; // What does this do?
foo2 = func; // Okay?
Literal Constants
• If you write:
– printf(“%d\n”, 15);
• Where are such constants stored in the
executable?
– Some constants are immediate operands (stored
in the instruction).
– Some are stored in data segment.
Structures
• Structure defined with:
– struct foo { int i; double x; };
• Fields are accessed with:
– struct foo f, *fp = &f;
fp->x and f.x;
• Initialized like this (same as arrays):
– struct foo f = {1, 3.14};
• Can be returned, assigned, etc.
– struct foo g; g = f;
– struct foo f() { struct foo f; ...; return f; }
struct foo obj;
obj = f(); // Dangerous?
– Okay, since it is returned by value.
• Structures can have padding between fields, so the size of a structure is
typically more than the sum of the size of each field.
– Purpose of the padding is to maintain alignment.
– Typically, a variable must start at an address that is a multiple of the size.
• There is also padding at the end of a struct.
– For arrays, discussed later.
• Type equivalence:
– Does this compile?
– struct T1 { int i; }; struct T2 {int i;};
T1 *p1 = ...;
T2 *p2 = p1;
– Does not compile, since they are different types even with same members.
• Let’s suppose you want to put an array in a struct, but the size might be
different. What do you do?
– Flexible array member.
– struct foo { int i; double a[]; };
struct foo *fp
= malloc(sizeof(struct foo) + n*sizeof(double));
fp->a[n – 1] = 3.14;
•
Can you make this compile?
– struct A {
int i;
B b_field;
};
struct B {
double x;
A a_field;
};
•
Similar case:
– struct A {
int i;
struct A a; // Need the struct?
};
– Can get same effect:
struct A {
int i;
A *inner;
};
•
Structures can refer to each other recursively using pointers, but not contain each
other recursively. One link of the recursion must be by pointer.
Enumerations
• Holds a set of values specified by the user.
– enum state { LETTER = 1, SPACE };
• Why might you want to begin with 1?
– The values can be used as constants:
• foo = SPACE;
int a[SPACE]; // Array of length 2.
– Can reset.
• enum Color { RED = 1, BLUE, GREEN = 1 };
• The scope of an unscoped enumerator is the same as enumeration
itself, and also in the “enum” scope.
– enum PotionType { HEALING, SPEED, POISON };
enum StatType { DEXTERITY, HEALTH };
int HEALTH = 10; // Error.
StatType st = HEALTH;
StatType st = StatType::DEXTERITY
st2 = DEXTERITY;
enum WandType { SPEED, FIREBALL }; // Error.
• C++11 adds scoped enumerations (enum classes):
– enum class PotionType {
HEALTH, SPEED, POISON };
enum struct StatType { DEXTERITY, HEALTH };
int HEALTH = 10;
StatType st = StatType::HEALTH;
PotionType pt = PotionType::HEALTH;
• Enumerations can be used in overloading:
– enum Color { R, G, B };
void foo(Color);
void foo(int);
Color c;
foo(c);
foo(1);
• Unscoped enums will implicitly convert to an integral type, but not
scoped.
– void goo(int);
goo(c); // Okay, implicit conversion.
enum struct Vehicle {
CAR, TRUCK
} v(CAR);
goo(v); // Error.
• C++11 allows you to specify the size of an enum:
– enum Color : char { R, G, B };
– enum Part : char {
Widget = 10000 }; // ?
• If you don’t specify it:
– For unscoped enums, the type is unknown.
– For scoped enums, it is int.
• You can also forward declare enums in C++11, but you must specify
the size:
– enum Color; // Error.
enum Color : char; // Okay.
// Okay, defaults to int.
enum class AccountType;
Lvalues and Rvalues
• Some values:
–1
89
a
b + c
sin(3.1)
• Do all values have equal status?
– Can a appear anywhere that 89 can appear?
• Assume a has been defined as an int.
• Some values have storage associated with
them. You can assign to them.
– a = 2;
• Others are just values.
– 2 = a;
References
• A reference is an alternate name, or alias. Arguably syntactic sugar.
• Implemented with pointers: At the implementation level, a pointer
that doesn’t look like one. Defines another name for a variable.
– int i, &alias = i, &alias2(i);
i = 2;
alias = 3; // Accessing the same variable.
• const int &i = 1; // Okay?
• int &j = 1; // Okay?
– Initializer of non-constant reference must be lvalue.
– Initializer of constant reference may be expression.
• Functions that return references can be used on the left-hand side
of an assignment.
– double &at(int i) {
static double a[10];
return a[i];
}
at(1) = 3.14159;
• Cannot be re-bound, unlike a pointer.
– int &i = j;
i = &k; // Error.
&i = k; // Error.
Pointers
•
Exampless:
– int *i_ptr, **i_pptr, ****i_pppptr;
A *a_ptr;
char *buf;
•
Is a pointer just an address?
– A type that points to an lvalue of another type. Essentially a typed address.
•
Address-of operator (&): What can you take the address of?
– Smart-alecky answer: Anything that has an address (i.e., any lvalue, more or less).
– int var;
&var, &(*ptr), &(ptr + 2), &(*(ptr + 2)), &(*(int *) 0xfff01234)
– Address of reference:
int var, &ref(var), &ref2 = var;
&var is the same as &ref.
– int i;
int **ip = &(&i);
int i, *ip = &i, **ipp = &ip;
– int *ip = &(1 + 2);
•
Dereference operator (*): What can you dereference?
– Anything that is of pointer type.
• Example of using pointers to pointers:
– Suppose you have a singly linked list [interactive]:
• struct Node {
int value;
Node *next;
};
Node *head = 0;
– One way to append to it:
• Node *end = 0;
void append(Node *n) {
n->next = 0;
if (end == 0) {
head = end = n;
} else {
end->next = n;
end = n;
}
}
– Another way:
• Node **end = &head;
void append(Node *n) {
n->next = 0;
*end = n;
end = &n->next;
}
Function Pointers
• Suppose you have a sort function, kind of like:
– void sort(int *array) { … }
• Can you write code that you can use for both ints, doubles, or your
own struct type?
– [Editor]
–
–
// Sort in ascending order.
void sort(void *array, int n, int sz, bool (*less)(void *, void*)) {
...
// Compare i-th and j-th element.
char *a = (char *) array;
if ((*less)(a + i*sz, a + j*sz)) {
...
}
bool Person_less(void *a, void *b) {
Person *p1 = (Person *) a;
Person *p2 = (Person *) b;
return strcmp(p1->name, p2->name) < 0;
}
...
Person *table = malloc(n_people*sizeof(Person));
...
sort(table, n_people, sizeof(Person), Person_less);
•
Suppose you now want to be able to sort in increasing order or decreasing order.
What do you do?
– Change the comparison function.
– // Sort in ascending order.
void sort(void *array, int sz, bool (*less)(void *, void*)) {
...
// Compare i-th and j-th element.
char *a = (char *) array;
if ((*less)(a + i*sz, a + j*sz)) {
...
}
– bool Person_greater(void *a, void *b) {
Person *p1 = (Person *) a;
Person *p2 = (Person *) b;
return strcmp(p1->name, p2->name) > 0;
}
...
Person *table = malloc(n_people*sizeof(Person));
...
// Sort in descending order.
sort(table, sizeof(Person), Person_greater);
...
// Sort in ascending order.
sort(table, sizeof(Person), Person_less);
• Can be reassigned, of course:
– int foo1(double x) { ... }
int foo2(double x) { ... }
void foo3(double x) { ... }
int (*fp)(double);
fp = &foo1;
(*fp)(3.14); // Calls foo1().
fp = &foo2;
(*fp)(3.14); // Calls foo2().
• Types must match:
– fp = &foo3; // Syntax error.
Null Pointers
• What is the value of i?
– char *p = 0;
int i = int(p);
• What is the value of a null pointer?
– It's actually unspecified.
• But wait, is it not 0?
– Not really. 0 is a special code to the compiler. When it is used in a pointer
context, the compiler automatically converts it to whatever the null pointer
value is.
• Consider:
– char *p = 0;
int i = int(p); // Is i 0?
– int zero = 0;
char *p = (char *) zero; // Is p null?
– char *p = 0; int *i = 0;
(unsigned long long) p ?= (unsigned long long) i
• In C++11, a new keyword was introduced, nullptr. It’s best to use this.
• What about NULL?
– It’s a macro.
– Let’s assume it is defined as (void *) 0. Does this work?
• char *p = NULL;
– Let’s assume it is defined as 0. Does this work?
• char *p = NULL;
– On Linux, it is defined as follows:
• #ifndef _LINUX_STDDEF_H
#define _LINUX_STDDEF_H
#undef NULL
#if defined(__cplusplus)
#define NULL 0
#else
#define NULL ((void *)0)
#endif
#endif
• Consider the execlp() system call:
– int execl(const char *, const char *arg0, ...);
execl(“./a.out”, “a.out”, “arg1”, “arg2”, 0);
• Is this correct usage?
– Not correct usage because the compiler has no way of knowing that
the last argument is actually a null pointer. So need to cast.
– execl(“./a.out”, “a.out”, “arg1”, “arg2”,
(const char *) 0);
Arrays
• Must be contiguous in memory. Define one like this:
– int a[4] = { 1, 2, 3, 4 };
int a[10]; // Initialized?
int a[] = {1, 2};
int a[2] = {1, 2, 3}; // Error
int a[2] = {1}; // Remainder are 0 initialized.
// Technically an error, but a common extension.
int a[0];
• Can take the sizeof. What does this print?
– int a[4];
printf(“%d\n”, sizeof a);
printf(“%d\n”, sizeof(int [2000*1000*1000]));
– Prints:
16
-589934592
– // Should be:
printf(“%zu\n”, sizeof(int [2000*1000*1000]));
• Are arrays passed in and returned by copy or reference?
– void foo(int a[10]) { a[9] = 0; }
a[9] = 1;
foo(a); // What is a[9] now?
– // What does the return type of foo2() need to
// be?
... foo2() { static int a[10]; return a; }
– You can’t pass arrays, actually what you is a pointer to the first element. So
passing arrays is essentially pass-by-reference.
• Which lines compile?
– void foo(int a1[10]) {
int a2[10];
a2 = 0; // ???
a1 = 0; // ???
}
• How do you pass in and return arrays by copy then?
– Wrap in a struct:
• struct Array { int a[10]; };
Array foo(Array a) { ...; return some_array; }
Type of an Array
• What is the type of an array?
– int a[2];
– Trick question: The type of an array is a just “an array of the contained type”.
• It is NOT a pointer. However, it very easily “decays” into a pointer pointing
to the first element.
– int a[4], *ap = a;
void foo(int *);
foo(a);
• Note that the & of an array is not the same:
– int *p = &a; // Syntax error.
• More examples:
– typedef int array_t[4];
typedef int *ptr_t;
array_t a; // Defines an array.
ptr_t ip; // Defines a pointer to an int.
Arrays and Pointers
• Arrays and pointers are closely related. Pointer arithmetic is closely
related to array indexing.
– Assume that we have: int a[10]; int *ip = &a[0];
– Then a[2] is equivalent to *(ip + 2) which is equivalent
to *(a + 2).
• Addition and subtraction:
– int
int
int
int
int
int
int
int
int
int
a[10], *ip = a; // What does ip point to?
*ip2 = ip + 3; // What does ip2 point to?
*ip3 = ip2 – 1; // ?
i1, i2;
n = &i1 - &i2; // Okay?
nn = &a[10] - &a[3]; // Okay?
n2 = &a[3] - &a[10]; // Okay?
n3 = &a[3] + &a[1]; // Okay?
a2[3];
n4 = &a[3] - &a2[0]; // Okay?
• Which ones are okay?
– int
ip1
ip1
2 +
ip2
2 –
ip2
*ip1 = …, *ip2 = …;
+ 2;
+ ip2;
ip2;
– 1;
ip1;
– ip1;
• Subtracting two pointers into an array is the same as
subtracting the indices:
– &a[i] - &a[j]
== &(*(a + i)) – &(*(a + j))
== (a + i) – (a + j))
== (a – a) + (i – j)
== i - j
Pointers and Memory Layout
• Consider a variable like this. How is it laid out in memory?
– int i = 0x01020304, *i_ptr = &i;
• What is byte-ordering? What kinds can you have?
– Which is big-endian and which is little-endian?
Address
• How many different orderings are there?
• What is the value of i_ptr?
103
1
4
3
102
2
3
4
101
3
2
1
100
4
1
2
One
possible
layout
Another
possible
layout
PDP-11
Memory of
variable i
• What is printed out?
– int i = 1;
char *p = (char *) &i;
printf(“%d\n”, (int) *p);
Increasing
address
1
0
0
0
0
0
0
1
One
possible
layout
Another
possible
layout
Memory of
variable i
• How do you swap byte order? [Editor]
– int i = ...;
i =
((i >> 24)&0x000000ff)
| ((i >> 8)&0x0000ff00)
| ((i << 8)&0x00ff0000)
| ((i << 24)&0xff000000);
– int i = ..., j;
char *p1 = (char *) &i,
*p2 = (char *) &j;
p2[0] = p1[3];
p2[1] = p1[2];
p2[2] = p1[1];
p2[3] = p1[0];
Complicated Definitions/Declarations
• Array of function pointers to functions that take one double
parameter and return an int.
– int (*a[10])(double);
• A function that take an int parameter and returns a function pointer
to a function that takes a double and returns an int.
– int (*f1(int i))(double){ … }
• A function that takes an int and returns a pointer to an array of 10
ints.
– int (*func(int i))[10] { ... }
• Array of 10 function pointers to functions that take an int
parameter and returns a function pointer to a function that takes a
double and returns an int.
– int (*(*a[10])(int))(double);
• When in doubt, use typedefs.
– Array of function pointers to functions that take one double parameter and return
an int.
• int (*a[10])(double);
• typedef int (*fp_t)(double);
fp_t a[10];
– A function that take an int parameter and returns a function pointer to a function
that takes a double and returns an int.
• int (*f1(int i))(double){ … }
• typedef int (*fp_t)(double);
fp_t f1(int i) { ... }
– A function that takes an int parameter and returns a pointer to an array of 10 ints.
• int (*func(int i))[10] { ... }
• typedef int (*array_ptr)[10];
array_ptr func(int i) { ... }
– Array of function pointers to functions that take an int parameter and returns a
function pointer to a function that takes a double and returns an int.
• int (*(*a[10])(int))(double);
• typedef int (*fp_t)(double);
typedef fp_t (*fp2_t)(int);
fp2_t a[10];
Multidimensional Arrays
• Defining multidimensional arrays:
– int a[2][3] = { 1, 2, 3, 4, 5, 6 };
– int a[10][20];
– They are really arrays of arrays. For example,
int a[2][3] is really an array of size 2 of arrays of
size 3.
• What is the type of the result of the index operation
a[0][0]?
• What is the type of the result of the index operation a[0]?
– This is two indexing operations.
• a[1][2]
• Arrays have rows and columns. Memory, however, is linear.
Thus, a 2-D array must be “linearized” to be stored in
memory.
• There are theoretically many ways to do linearization, but
only two are common.
– Which one does C/C++ use?
Array a[2][3]
a0,0
a0,1
a0,2
a1,0
a1,1
a1,2
Column major
Row major
Row 0
a0,0
a0,1
Col 0
Row 1
a0,2
a1,0
a1,1
a1,2
a0,0
Increasing address
a1,0
Col 1
a0,1
a1,1
Col 2
a0,2
a1,2
• Another way to look at it.
int a[2][3];
Row major
a0,0
a1,0
a0,1
a1,1
Column major
a0,2
a0,0
a0,1
a0,2
a1,0
a1,1
a1,2
a1,2
Col 0
Row 0
a0,1
Col 2
Row 1
a0,0
a0,0
Col 1
a0,2
a1,0
a1,1
a1,2
a1,0
a0,1
a1,1
a0,2
a1,2
Puzzle Question
• Array indexing is equivalent to pointer arithmetic at even a
syntactic level, which leads to some strange things:
– int a[10];
– a[2] equivalent to *(a + 2).
a[2]  *(a + 2)  *(2 + a)  2[a].
– So, we should be able to write:
2[a] = 12345; // Right?
• Given an array int a[3][3], how many ways can you index
the first element, using only the characters 0, [, ], and a?
–
–
–
–
a[0][0]
0[a][0]
0[a[0]]
0[0[a]]
Pointers to Arrays
• Tricky concept, but especially useful as an educational exercise.
– If you understand them, then you really understand pointers and arrays.
• ip is a pointer to what? ap is a pointer to what?
• Where does ip + 1 point? Where does ap + 1 point?
int *ip = ...;
? bytes
int (*ap)[3] = ...;
? bytes
ip
11
ap
21
ap+1
ip+1
ip+2
31
•
sizeof
sizeof
sizeof
sizeof
sizeof
ip == ??
ip[1] == ??
ap == ??
ap[1] == ??
ap[1][1] == ??
12
13
21
22
23
31
32
33
ap+2
...
...
• What is?
11
• More examples:
– int (*p1)[10];
int a1[10];
p1 = &a1; // Okay?
p1[0] = 1; // Okay?
(*p1)[0] = 1; // Okay?
p1[0][0] = 1; // Okay?
– int (*p2)[8];
p2 = &a1; // Okay?
• Can get some complex/weird looking definitions/declarations:
– A function that returns a pointer to an array of 10 ints.
• int (*func())[10];
– An array of 10 pointers to functions that take an int and return a pointer to an
array of doubles:
• double (*(*a1[10])(int))[20];
• typedef double array_t[20];
typedef array_t *ptr_to_array_t;
typedef ptr_to_array_t (*fp_t)(int);
fp_t a2[10];
• You can usually just use a pointer instead of a pointer
to an array:
– int a1[10], a2[10];
int *p;
p = a1;
p[1] = 1234;
p = a2;
p[1] = 1234;
– int a1[10], a2[10];
int (*ap)[10];
ap = &a1;
(*ap)[1] = 1234;
ap = &a2;
(*ap)[1] = 1234;
• However, in the case of multidimensional, dynamic
arrays, pointers to arrays can do things that simple
pointers cannot.
• Can also have a reference to an array.
– int a[10], (&alias)[10](a);
– Mainly of use later on in templates.
Multidimensional Array Type Decay
• An array containing type T decays to a pointer to
type T.
– void f1(int *);
int a[10];
f1(a); // Okay?
– void f2(MyClass *);
MyClass a[10];
f2(a); // Okay?
– void f3(int **);
int a[10][20];
f3(a); // Okay?
• An array of ints decays to a pointer to an int.
– int a[10];
// a decays to int *.
void f1(int *);
f1(a); // Works.
• An array of structs decays to a pointer to the struct.
– MyClass a[10];
// a decays to MyClass *.
void f2(MyClass *);
f2(a); // Works.
• A multidimensional array is an array of arrays. So, a
multidimensional array decays to a pointer to an array, not a
pointer to a pointer.
– int a[10][20];
// a decays to int (*)[20].
void f3(int (*ap)[20]);
void f4(int **);
f3(a); // Works.
f4(a); // Syntax error.
Dynamic Arrays
• The “array of pointers” way.
– Does each row need to have the same number of columns?
Number of columns
2-D
111
112
113
121
122
123
131
132
133
Number of rows
...
...
...
...
No.
Number of planes
3-D
311
312
313
321
322
323
331
332
333
...
...
...
...
...
Plane 2
111
112
113
121
122
123
131
132
133
...
...
...
Plane 0
211
212
213
221
222
223
231
232
233
...
...
Number of rows
Number of columns
Plane 1
...
...
...
• The code for the “array of pointers” way.
– void f_3ptr(int ***);
int ***a = (int ***) malloc(np*sizeof(int **));
for (size_t i = 0; i < np; i++) {
a[i] = (int **) malloc(nr*sizeof(int *));
for (size_t j = 0; j < nr; j++) {
a[i][j] = (int *) malloc(nc*sizeof(int));
}
}
f_3ptr(a);
for (size_t i = 0; i < np; i++) {
for (size_t j = 0; j < nr; j++) {
free(a[i][j]);
}
free(a[i]);
}
free(a);
• If only one dimension needs to be dynamic, you can use a pointer to an
array.
– void f(int (*const a)[2][3]);
int (*a)[2][3] = (int (*)[2][3])
malloc(np*sizeof(int [2][3]));
f(a);
free(a);
Col 0
Col 1
Col 2
Number of columns must be
known at compile-time
Row 0
111
112
113
Row 1
121
122
123
Row 0
211
212
213
Row 1
221
222
223
Row 0
311
312
313
Row 1
321
322
323
a
Number of rows
must be known
at compile-time
Plane 0
Plane 1
Plane 2
...
np planes
• 2D usage: A dynamically-determined number of rows, but a fixed number
of columns.
– // Pointer to an array of 10 columns.
int (*a)[10];
// Use it as an array with n_rows and 10 columns.
a = (int (*)[10]) malloc(sizeof(int [10])*n_rows);
– a[0] refers to the first array of 10.
a[1] refers to the second array of 10.
a + 1 points to the second array of 10.
a + 2 points to the third array of 10.
a[0][2] refers to the third column in the first array.
a[1][3] refers to the fourth column in the second array.
(*(a + 2))[5] refers to the sixth column in the third array.
• In C99, can use variable length arrays.
• The “array of pointers” way is slower, but
more flexible.
C Strings
• A string in C is just an array of characters that is terminated by
a 0 element.
• Note that you can have an array of characters that is not 0
terminated, and thus not really a string.
• What is the difference between?
– char a1[] = “abcd”;
const char *a2 = “abcd”;
char a3[4] = {'a', 'b', 'c', 'd'};
sizeof a1 == ? 5
sizeof a2 == ? Size of a pointer
sizeof a3 == ? 4
a2[0] = 'z'; // Okay? No, can’t write to literal.
a1 = "a"; // Okay? Can’t assign to array.
a2 = "b"; // Okay? Yes.
a3 = "c"; // Okay? Can’t assign to array.
String Literals
• “hello“ // A string literal
• What is the type of “hello”?
– Type is “array of the appropriate number of const characters”: const
char[6]
– sizeof("hello") == 6
– What is the type in C?
• Is this okay code?
– void error(char *s) {
printf(“error: %s\n”, s);
}
…
error(“Bad syntax”);
– const char *foo() {return "hello";}
• Is this an error?
– const char *str = "This is a long "
"string.";
Void
• What is it used for?
– Function returns.
– Pointers to unknown types.
• Does this compile?
– void *vp = …;
char *cp = vp;
• What about arithmetic?
– void *vp = …;
void *vp2 = vp + 1; // Okay?
• In C, does this compile? What about C++?
– int f1() { return 1; }
int main() {
f1(1);
}
– int f2();
int main() {
f2(1);
}
– int f3(void);
int main() {
f3(1);
}
• In C, void in function definition is redundant, but not in a
declaration.
• In C++, void in either a function definition or declaration
is redundant.
– int f4(void) { return 1; };
Constness
• const int foo = 30;
int const foo = 30; // Same thing.
– Cannot assign to foo.
– foo = 10; // No.
• const int *foo;
– Cannot assign to *foo, but can assign to foo itself.
– *foo = 1; // No.
foo = &some_int_var; // Okay.
• int *const foo = &some_int;
– Cannot assign to foo (which is a pointer), but can assign to what is
pointed to.
– foo = &some_other_int_var; // No.
*foo = 1234; // Okay.
• const int *const foo = &some_int;
– Cannot assign to anything.
• int ** const *** const * const *p;
– p = ...; // Okay?
*p = ...; // Okay?
**p = ...; // Okay?
***p = ...; // Okay?
****p = ...; // Okay?
*****p = ...; // Okay?
******p = ...; // Okay?
*******p = ...; // Okay?
constexpr
• In C++03, there is no way to cleanly say that something is a compile time
constant.
– const
const
const
const
int
int
int
int
i1
i2
i3
i4
=
=
=
=
1;
3*4;
MyClass<2, 4>::RED;
product_if_odd(3, 4, 5);
• Furthermore, you can never call a function to compute a compile time
constant.
• C++11 has constexpr to fix this:
– constexpr int i1 = 1;
// Body must be just single return statement.
constexpr int product_if_odd(int i, int j, int k) {
return i%2 == 1 ? i*j*k : 0;
}
// Syntax error if foo() is not constexpr.
constexpr int i2 = foo(3);
constexpr int i3 = product_if_odd(3, 4, 5); // Okay.
• C++14 greatly relaxes the restrictions on
constexpr:
– constexpr int
count_a(const char *s) {
int c = 0;
for (; *s != '\0'; s++) {
if (*s == 'a') {
c++;
}
s++;
}
return c;
}
• Another C++14 example:
– constexpr bool
is_prime(int n) {
for (auto i = 2; i*i <= n; i++) {
if (n%i == 0) {
return false;
}
}
return true;
}
• Can also have constexpr arrays and objects, as
long as the objects are of literal type.
– struct A {
int i, j;
};
constexpr A foo() { return {1,2}; }
constexpr A a(foo());
constexpr A aa[2] = { {1, 2}, {3, 4}
};
Volatile
• [Show flag.]
• int *flags = some_special_hardware_address;
while (true) {
…
if (*flags & 0x1) { … }
…
}
• Does above work?
– Does *flags get reloaded every iteration?
• volatile int *flags =
some_special_hardware_address;
while (true) {
…
if (*flags & 0x1) { … }
…
}
decltype
• Sometimes you want to get the type of an object or expression, and use it
in a declaration/definition.
– int i;
decltype(i) j;
int *ip;
decltype(ip) ip2;
int &r = i;
decltype(r) r2(j); // r2 is a reference.
• The decltype of an lvalue is a reference (except if it is just the variable).
– int i1(11);
decltype(i1) i2(22); // i2 is an int.
decltype((i1)) r1(i2); // r1 is a ref.
decltype(i1 + 1) i3(i2); // i3 is ?.
decltype(*(&i1 + 1)) i4(i2); // i4 is ?.
– const int c1(11);
decltype(c1) c2(22); // c2 is a const int.
• The decltype of a function is a function.
Can use this to simplify function pointer
definitions/declarations.
– int f(double) { … }
decltype(f) f2; // int f2(double);
decltype(f) *f3(int) { … }
auto
• auto was originally just a storage class specifier
indicating that storage should be non-persistent
(stack):
– void foo() {
register int i1;
extern int i2;
static int i3;
auto int i4a;
int i4b; // Exactly the same.
• Since it was the default anyway, it was pretty
useless.
• It now has an additional new meaning, which is that the
type of the variable being defined should be based on the
type of the initializer.
– auto i = 1;
int &r(i);
auto i2 = r; // ref or not?
auto &i3 = r;
auto *i4 = &r;
auto i5 = &r;
const int i6(1234);
auto i7(i6);
i7 = 567; // Okay or not?
auto &i8(i6);
i8 = 567; // Okay?
– const int *const ip1(&i6);
auto ip2(ip1);
*ip2 = 567; // Okay?
ip2 = &i; // Okay?
• The deduced type must be consistent for every variable:
– const int i(1234);
auto i1(i), &i2(i); // Okay?
• Very handy for things like iterators:
– for (map<string, Myclass>::iterator it
= map.begin(); …) { … }
– for (auto it = map.begin(); …) { … }
• In C++14, can get the same rules for decltype as for
auto:
– decltype(auto)
Type Conversions
• Implicit conversions
– They are “automatic”, in the sense that you don’t need to
add anything to make them happen.
– What are some?
• int to double
• Pointer to derived to pointer to base (upcast)
• Two situations where conversions come into play.
1. Converting to a given type, such as assignment or
argument passing.
2. Two operands of an arithmetic operator.
• Arithmetic conversions: signed/unsigned
combinations are tricky:
– If both operands are same size, the signed is converted to
the unsigned.
– Otherwise, it’s more or less the smaller to the larger.
• int vs. unsigned long
– cout << -1 + 1UL << endl;
cout << (-1 < 1UL) << endl;
cout << -2 + 1UL << endl;
cout << (-2 < 1UL) << endl;
cout << -1 + 2UL << endl;
cout << (-1 < 2UL) << endl;
cout << -2 + 2UL << endl;
cout << (-2 < 2UL) << endl;
– On 32-bit Linux g++:
•
•
•
•
•
•
•
•
-1 + 1UL == 0
-1 < 1UL == false
-2 + 1UL == 4294967295
-2 < 1UL == false
-1 + 2UL == 1
-1 < 2UL == false
-2 + 2UL == 0
-2 < 2UL == false
• int vs. unsigned long
– cout << -1 + 1UL << endl;
cout << (-1 < 1UL) << endl;
cout << -2 + 1UL << endl;
cout << (-2 < 1UL) << endl;
cout << -1 + 2UL << endl;
cout << (-1 < 2UL) << endl;
cout << -2 + 2UL << endl;
cout << (-2 < 2UL) << endl;
– On 64-bit Linux g++:
•
•
•
•
•
•
•
•
-1 + 1UL == 0
-1 < 1UL == false
-2 + 1UL == 18446744073709551615
-2 < 1UL == false
-1 + 2UL == 1
-1 < 2UL == false
-2 + 2UL == 0
-2 < 2UL == false
• long int vs. unsigned int
– cout <<
cout <<
cout <<
cout <<
cout <<
– On 64-bit:
-1L + 1U << endl;
// L1
-1L + 1U - 1 + 2LL << endl; // L2
-1L + 1U + 2LL - 1 << endl; // L3
-2L + 1U << endl;
// L4
(-1L < 1U) << endl;
// L5
-1L + 1U == 0
-1L + 1U – 1 + 2LL == 1
-1L + 1U + 2LL – 1 == 1
-2L + 1U == -1
-1L < 1U == true
– On 32-bit:
-1L + 1U = 0
-1L + 1U – 1 + 2LL == 4294967297
-1L + 1U + 2LL – 1 == 1
-2L + 1U == 4294967295
-1L < 1U == false
• What does this print?
– size_t s3 = 3, s5 = 5;
size_t s10 = 10;
long long ll10 = 10;
s10 += s3 - s5; // L1
ll10 += s3 - s5; // L2
cout << s10 << “, “
<< ll10 << endl;
– size_t is 64-bit unsigned on 64-bit platforms, and
32-bit unsigned on 32-bit platforms.
– long long is a 64-bit signed integer on both
platforms.
– On 64-bit:
8, 8
– On 32-bit:
8, 4294967304
• What does this print?
– cout << 2000000*2000*1L << endl;
cout << 1L*2000000*2000 << endl;
– Intel 32-bit with g++:
• -589934592
• -589934592
– Intel 64-bit with g++:
• -589934592
• 8000000000
bool conversions
• Does this print “Yes” or “No”?
– int i = 10;
if (i) {
cout << “Yes” << endl;
} else {
cout << “No” << endl;
}
• What about this?
– int i = 10;
if (i == true) {
cout << “Yes” << endl;
} else {
cout << “No” << endl;
}
Numerical Conversions
• 3.9.1/4 Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2n where n is the number of bits in the value representation of that particular size of integer.
• 4.5 Integral promotions [conv.prom]
1.
2.
3.
4.
5.
An rvalue of type char, signed char, unsigned char, short int, or unsigned short int can be converted to an rvalue of type int if int can represent all the values of the source type; otherwise, the source rvalue can
be converted to an rvalue of type unsigned int.
An rvalue of type wchar_t (3.9.1) or an enumeration type (7.2) can be converted to an rvalue of the first of the following types that can represent all the values of its underlying type: int, unsigned int, long, or
unsigned long.
An rvalue for an integral bitfield (9.6) can be converted to an rvalue of type int if int can represent all the values of the bitfield; otherwise, it can be converted to unsigned int if unsigned int can represent all the
values of the bitfield. If the bitfield is larger yet, no integral promotion applies to it. If the bitfield has an enumerated type, it is treated as any other value of that type for promotion purposes.
An rvalue of type bool can be converted to an rvalue of type int, with false becoming zero and true becoming one.
These conversions are called integral promotions.
• 4.6 Floating point promotion [conv.fpprom]
1.
2.
An rvalue of type float can be converted to an rvalue of type double. The value is unchanged.
This conversion is called floating point promotion.
• 4.7 Integral conversions [conv.integral]
1.
2.
3.
4.
5.
An rvalue of an integer type can be converted to an rvalue of another integer type. An rvalue of an enumeration type can be converted to an rvalue of an integer type.
If the destination type is unsigned, the resulting value is the least unsigned integer congruent to the source integer (modulo 2n where n is the number of bits used to represent the unsigned type). [Note: In a
two’s complement representation, this conversion is conceptual and there is no change in the bit pattern (if there is no truncation). ]
If the destination type is signed, the value is unchanged if it can be represented in the destination type (and bitfield width); otherwise, the value is implementation defined.
If the destination type is bool, see 4.12. If the source type is bool, the value false is converted to zero and the value true is converted to one.
The conversions allowed as integral promotions are excluded from the set of integral conversions.
• 4.8 Floating point conversions [conv.double]
1.
2.
An rvalue of floating point type can be converted to an rvalue of another floating point type. If the source value can be exactly represented in the destination type, the result of the conversion is that exact
representation. If the source value is between two adjacent destination values, the result of the conversion is an implementation defined choice of either of those values. Otherwise, the behavior is undefined.
The conversions allowed as floating point promotions are excluded from the set of floating point conversions.
• 4.9 Floating-integral conversions [conv.fpint]
1.
2.
An rvrvalue of an integer type. The conversion truncates; that is, the fractional part is discarded. The behavior is undefined if the truncated value cannot be represented in the destination type. [Note: If the
destination type is bool, see 4.12. ]
An rvalue of an integer type or of an enumeration type can be converted to an rvalue of a floating point type. The result is exact if possible. Otherwise, it is an implementation defined choice of either the next
lower or higher representable value. [Note: loss of precision alue of a floating point type can be converted to an occurs if the integral value cannot be represented exactly as a value of the floating type. ] If the
source type is bool, the value false is converted to zero and the value true is converted to one.
• 5/9 Many binary operators that expect operands of arithmetic or enumeration type cause conversions and yield result types in a similar way. The purpose is to yield a common type, which is
also the type of the result. This pattern is called the usual arithmetic conversions, which are defined as follows:
–
–
–
–
–
–
–
–
–
–
If either operand is of type long double, the other shall be converted to long double.
Otherwise, if either operand is double, the other shall be converted to double.
Otherwise, if either operand is float, the other shall be converted to float.
Otherwise, the integral promotions (4.5) shall be performed on both operands.
Then, if either operand is unsigned long the other shall be converted to unsigned long.
Otherwise, if one operand is a long int and the other unsigned int, then if a long int can represent all the values of an unsigned int, the unsigned int shall be converted to a long int;
otherwise both operands shall be converted to unsigned long int.
Otherwise, if either operand is long, the other shall be converted to long.
Otherwise, if either operand is unsigned, the other shall be converted to unsigned.
[Note: otherwise, the only remaining case is that both operands are int ]
Object Identity
• Let’s say that you have two references to two objects belonging to
some struct (or class). How can you tell if they refer to the same
object?
– struct Foo { int i; double x; };
void some_func(const Foo &r1, const Foo &r2) {
// Are r1 and r2 actually the same object?
if (&r1 == &r2) { ... }
}
• Two objects are the same object if and only if they have the same
address.
sizeof empty struct
• [empty_struct/]
• What does this print in C?
– struct Empty {};
int main() {
struct Empty a[10];
printf("distance: %d\n",
(int) (&a[1] - &a[0]));
}
– This causes a numerical exception.
• What is should sizeof return for this?
– struct Empty {};
• If it returned 0, then…
– Empty a[10];
Empty *a1 = &a[1];
Empty *a2 = &a[2];
if (a1 == a2) {
printf(“Same object!\n”);
}
• &a[i] - &a[j] ?== (i – j)
OPERATORS AND EXPRESSIONS
Operators
• Arithmetic: + - / * %
– -10/3 == ?
-10%3 == ?
– Must always be true: (a/b)*b + a%b == a.
• Relational: < <= > >= == != && ||
– Is this code safe?
int *ip = …;
if (ip != 0 && *ip == 1) { … }
•
•
•
•
Negation: !
Increment and decrement: -- ++
Bitwise: & | ^ ~ << >>
Assignment: = =+ =/ …
– Value of an assignment operator is value of the result.
– int a;
printf(“%d\n”, a = 1); // Prints 1
printf(“%d\n”, 3*(a += 2)); // Prints 9.
– Also an lvalue (but not in C):
• (a = 1) = 3;
• Conditional expression:
–i = a > b ? 1 : 2
• Is this a syntax error?
– i = f(1), g(2);
• sizeof, &var, * (dereference)
Precedence and Associativity
• What is this code trying to do? Is it correct?
– if (a << 1 + 1 == c & 0xf) { … }
– Actual precedence: if (((a << (1 + 1)) == c) & 0xf) { … }
• Precedence is which operator gets applied first.
– x*y + a
– The * has higher precedence, so the y operand is bound to the *.
• Associativity is which operator gets executed first when the precedence is
the same.
– a + b + c
• (a + b) + c
– a – b + c
• (a – b) + c
– a + b – c
• (a + b) – c
– a/b/c
• (a/b)/c
– i = j = k = 1234;
• ((i = j) = k) = 1234;
• i = (j = (k = 1234)); // This is correct.
• Tip: Look at the operand, not the operator.
– A left associative operator means that an operand
goes with the operator on the left.
a+b+c
• Suppose (hypothetically) that + was left
associative and – was right associative. Then
how would this be evaluated?
–a – b + c
Baking Recipe
•
•
•
•
•
•
Prepare mixture A (takes 10 minutes). Let stand 50 minutes.
Prepare mixture B (takes 20 minutes).
Prepare mixture C (takes 30 minutes). Let stand 20 minutes.
Whip B and C together producing D.
Gently fold A into D.
Expression: cake = make_A() FOLD make_B() WHIP make_C()
– Precedence?
•
•
Expression: cake = make_A() FOLD ( make_B() WHIP make_C() )
Best preparation order?
FOLD
Evaluation order is analagous
to what order you prepare A,
B, and C. You can prepare A
first, even though it is used
last in the expression.
WHIP
A
B
C
Evaluation Order
•
•
[Show eval_order.]
Consider:
– int &f(int i) {
cout << i << endl;
static int x;
return x;
}
•
How does this associate?
– f(1) = f(2) = f(3);
– f(1) = (f(2) = (f(3) = 1234));
•
•
What gets printed?
Associativity does not mean evaluation order! Associativity and precedence are
about grouping.
– Why allow this?
•
•
A few operators guarantee evaluation order.
Evaluation order is not specified.
– (e1) + (e2) + (e3)
– If no side effects, evaluation order cannot be detected anyway.
– Regardless, associativity is not the same.
• You could have left associative, but right-to-left evaluation order.
• Given:
– int &f(int i) {
cout << i << endl;
static int x;
return x;
}
• These two will print what?
– f(1) = f(2) = f(3);
– func(f(1), f(2), f(3));
• On Linux, g++:
– 1, 2, 3 and 3, 2, 1
• On Linux, clang++:
– 3, 2, 1 and 1, 2, 3
• On Sun:
– 1, 2, 3 and 1, 2, 3
Sequence Points
• What is the value of i?
– int i = 0;
++i = i++ + i++;
– Linux with g++: 4
– Solaris with g++: 2
– Solaris with Sun: 1
• More examples:
– i++ / i-i = a[i++];
f(i++, i++)
• Usually only a problem when you have side effects.
• C/C++ defines sequence points.
– All side effects are executed at sequence points.
– You cannot read or write to the same lvalue multiple times between
sequence points, or else you get undefined behavior.
• What are some sequence points?
– End of statement
– Function call, beginning and end
– Comma operator
• a = 1, b = 2;
– Short-circuiting logical operator: && and ||
Casts
• Syntax is cast<T>(…), but it is not a template. Syntax just kind of
makes it look like one.
– static_cast
• Used for casts that are “reasonable”, but not implicit. Like a cast from void *.
Loss of precision casts.
– const_cast
• Only used to change the const-ness of something.
– dynamic_cast
• Cover later
– reinterpret_cast
• Used to do things that seem to make no sense.
• C-style
– (T) val
T (val)
– Anything to anything.
– Precedence is very high, right after () (function call), [], ->,
and . (member access).
• const_cast can useful where you want to leverage something
that returns const reference to something that you know is not
actually const.
– const string &
shorterString(const string &, const string &);
– string &
shorterString(string &, string &) {
return
const_cast<string &>(
shorterString(
const_cast<const string &>(s1),
const_cast<const string &>(s2)
)
);
}
STATEMENTS
Simple and Compound
• The simplest statement is just a ;
• A compound statement is enclosed in curly braces,
with no terminating ;
– { s1; s2; }
– Often useful for short, temporary, copy-and-paste code.
• // Not copyable.
int i = ...;
double x = ...;
// ... Some statements here.
• // Copyable.
{
int i = ...;
double x = ...;
// ... Some statements here.
}
Declaration Statement
• Can be placed anywhere, not just at the top of a block.
• We call it a declaration statement, but it is usually also a
definition.
– extern int i;
int j;
• What is point of declaration?
– class A { int i, j, k; … };
void A::func(int i) {
int ii = i;
int j1 = i, j2 = j;
int k = k, k2 = k;
…
}
– ~kchiu/init.cpp
if Statement
• You can have a declaration/definition in it.
– if (Obj *p = lookup(...)) {
…
}
• What does this print?
– int n = -1;
if (n >= 0)
for (int i = 0; i < 4; i++)
if (i%2 == 0)
printf(“%d is even.\n“, i);
else
printf(“n is negative.\n");
• The else is attached to the nearest if. Defensive
programming: always use curly braces.
Integral
Expression
switch statement
Constant
label
Exit switch
• switch (e) {
case 1:
stmt1;
Fall through
break;
case 3:
Fall through
stmt2;
case 4:
case 5:
stmt3;
break;
default:
break; // Redundant.
}
• How is this code?
– enum State {
START, STATE1, STATE2
} state;
while (not_done) {
switch (state) {
case START:
...
break;
case STATE1:
...
break;
case STATE2:
...
break;
}
}
• Better:
– enum State {
START = 1, STATE1, STATE2
} state;
while (not_done) {
switch (state) {
case START:
...
break;
case STATE1:
...
break;
case STATE2:
...
break;
default:
assert(false); abort();
break;
}
}
• Correct:
– enum State {
START = 1, STATE1, STATE2
} state = START;
while (not_done) {
switch (state) {
case START:
...
break;
case STATE1:
...
break;
case STATE2:
...
break;
default:
assert(false); abort();
break;
}
}
• Does this compile?
– switch (e) {
case 1:
int i = 1;
// … Some code here…
break;
case 3:
// … Some other code here…
break;
default:
assert(false); abort();
break;
}
• This is a jump across an initializer, and won’t compile.
• What’s the good practice to be learned?
• Use blocks:
– switch (e) {
case 1:
{
int i = 1;
// … Some code here…
}
break;
case 3:
{
// … Some other code here…
}
break;
default:
assert(false); abort();
break;
}
• General syntax:
– switch (expr) {
int i;
// Any sequence of any type of statements,
// including further compound statements, flow
// control, etc.
// Case labels may be interspersed.
}
– switch (expr) {
int i, j;
if (cond) {
some_statement1;
case 1: some_statement2;
stmnt2;
} else {
case 3: some_statement3;
}
default: some_statement4;
}
Show odd_switch/
• Which is more efficient?
– if (a == 900) {
…
} else if (a == 2) {
…
} else if (a == 93) {
…
} else {
…
}
– switch (a) {
case 900: …; break;
case 2: …; break;
case 93: …; break;
default: …; break;
}
– [Show switch_jump/]
• Which is more efficient?
– if (a == 1) {
...
} else if (a == 2) {
...
} else if (a == 3) {
...
} else if (a == 4) {
...
} else if (a == 5) {
...
} else {
...
}
– switch (a) {
case 1: …; break;
case 2: …; break;
case 3: …; break;
case 4: …; break;
case 5: …; break;
default: …; break;
}
for Statement
• for (int i = 0, j = 0; j < 0; j++, i += 2) {
if (some_cond) {
j = 0;
}
...
}
• // Search for something in a loop.
for (int i = 0; i < v.size(); i++) {
if (v.at(i) == what_we_are_looking_for) {
break;
}
}
• How can one tell whether or not we found what we were looking for?
• C++11:
– pos = find_if(std::begin(array), std::end(array),
[&](const MyClass &o) { … });
• Range-based for (C++11):
– list<MyClass> a_list;
for (auto it : a_list) { … }
– for (list<MyClass>::iterator it
= a_list.begin();
it != a_list.end();
++it) {
…
}
– int a[] = {1, 2, 3, 4};
for (int &i : a) {
if (i == 3) { i++; }
}
– #include <initializer_list>
for (int i : {1, 2, 3, 4}) {
…
}
while Statement
• Can also have a declaration in it.
– while (int i = j – 3) { … }
do-while Statement
• do { … } while (expr);
• Used for multi-statement macros.
– #define m(…) \
do {
\
…
\
} while (false)
break and continue Statements
• break will immediately exit the nearest
enclosing loop.
• continue will immediately re-test and
possibly continue the nearest enclosing loop.
• Can this code be simplified?
– bool keep_going = true;
while (keep_going) {
...
if (...) {
keep_going = false;
} else {
...
}
}
– Simplification:
while (true) {
...
if (...) {
break;
}
...
}
goto Statement
• goto label;
label: statement;
• Is it a good idea?
• How would you rewrite this?
– while (expr1) {
while (expr2) {
if (expr3) { goto exit; }
…
}
…
}
exit:
• Also have jump over initialization issues.
• What about this?
– again:
Connection c(url);
if (!c.connect()) {
goto again;
}
FUNCTIONS
Overview
•
Why use functions?
– It’s a way of parameterizing a piece of code.
– Does slightly different things, depending on the
parameters.
– Does it save memory? Does it save effort?
•
What happens when you call a function?
1.
2.
3.
4.
5.
•
Pushes parameters on the stack (or in registers).
Pushes return location.
Makes a jump.
Returns a value somewhere.
Pops stack, jumps back.
How do functions affect performance?
– Some cost, but can help keep code in instruction cache.
• Examples:
– int f(int p, double, int i) { … }
void f(int i, int j);
• What is the difference between a parameter
and an argument?
– int f(int p) { … }
…
f(1);
– Parameter is what it is usually called in the
function. Argument is what you pass to it.
Prototypes
• Before a function can be called, it must be declared via a
prototype.
–
–
–
–
–
ret_type func(T1 p1, T2 p2);
Return type
Function name
Parameter list
Where should the prototype go? Does the compiler need to see it
before it calls the function?
• Sequence of parameter types is known as the function
signature.
– Slightly different from some definitions of function signature, which
might include the function name and return type.
• Declaration vs. definition
– Prototype is also the declaration. Actual definition has the body.
Return Type
• ret_type foo();
• Examples:
– int foo();
int *foo();
MyClass foo();
int foo();
• Okay?
– int *foo() { int i; return &i; }
int &foo() { int i; return i; }
int *foo() { static int i; return &i; }
int *foo() {
const static int i = 2; return &i;}
• How do you return an array?
– int foo()[] { int array[5]; return array; }
• What does this do?
– int &foo() { static int i; return i: }
foo() = 3;
– Since it returns a reference, a function call can act as an lvalue. It
assigns to the static int inside the function.
• Any difference between these?
– return expr;
return (expr);
• There are three types involved.
– MyType foo() { …; return val; }
…
ret = foo();
– There is MyType, the type of val, and the type of
ret.
•
The return type can trail (C++11):
– auto func(int i) -> int (*)[10];
– Trailing return types are in class scope for member functions.
– class A {
class B { int f(); … };
B b;
…
};
auto A::func(int i) -> B { … }
auto A::func2() -> decltype(b.f()) { … }
•
In C++14, the return type can be deduced:
– auto odd_or_even(const int i) {
if (i%2 == 1) {
return “odd”;
} else {
return “even”;
}
}
– In C++11, the return type of lambdas can also be deduced, but only if just a return statement.
Parameter List
• Are these the same?
– int
int
– int
int
foo();
foo(void);
foo() {…}
foo(void) {…}
• Is this okay?
– int foo(int i); // Prototype
int foo(int j) { … } // Actual definition
• Type checking/conversion
– void foo(int, int);
foo("a", "b"); // What happens?
foo(3.14, 4); // What happens?
Argument Passing
• Semantics is initialization.
– void f(int i);
f(x); // Same as int i = x;
– void f2(A a);
f2(3); // Same as A a(3);
• C and C++ are pass by value. Is this efficient?
– struct A { int a[1000000]; };
void f(A a);
Default Arguments
• Functions can define default arguments to be used when arguments are
missing.
– void foo(int i = 0);
foo(1);
foo(2);
foo();
– void print(int v, int base=10);
print(31);
print(31, 10);
• Is this okay?
– void foo(int i = 0, int j = 1, int k);
foo(2, 3);
• No, put defaults at the end.
– void foo(const char *s = “hello”, int i = 3) {}
foo(5);
• Doesn’t work.
Ellipses
• void foo(const char *, …);
– Need one parameter in C, but not in C++.
• Use <stdarg.h>.
• Example:
– #include <stdarg.h>
#include <stdio.h>
void print_strings(const char *s0, ...) {
printf("%s\n", s0);
va_list ap;
va_start(ap, s0);
char *s;
while ((s = va_arg(ap, char *)) != 0) {
printf("%s\n", s);
}
va_end(ap);
}
int main() {
print_strings("string1", "string2", NULL);
// Is below safe?
print_strings("string1", "string2", 0);
}
initializer_list
• Another way to pass a variable number of arguments.
• An initializer_list is a library type that the compiler
creates automatically.
– #include <initializer_list>
#include <string>
#include <iostream>
using namespace std;
void func(initializer_list<string> l) {
for (auto s : l) {
cout << s << endl;
}
}
…
func({“a”, “b”, “c”});
Pointers, References, and Function
Arguments
• Pointers or references can be used to return more
than one value.
– int foo(double *xp, double &y);
double x, y;
int ret = foo(&x, y);
– Which is better?
– Is there another way?
• Can write swap of two pointers/references like this:
– void swap(int *&x, int *&y) {
int *t = x;
x = y; y = t;
}
– Java?
• Which of f1() or f2() is better?
– struct Data {
int data[10000];
};
void f1(Data d);
void f2(const Data &d);
– Second is much more efficient, since the first will
copy the data.
Inline Functions
• Suppose we want to compute the maximum
of two numbers.
• Where do they go?
– Must go in the header file. Why?
• Two benefits:
– Eliminating the function call overhead.
– Maximizing opportunities for compiler
optimizations.
Function Overloading
• Multiple functions that share the same name
can be defined.
– Then how can we the compiler tell which one to
call?
– Why do this?
Overloaded Function Names
• Two functions with different arguments, but same
names
– There are some complicated rules for matching.
• How does the linker handle it?
– [Show linking_overload.]
Function Signatures
• Overload resolution is based on function signatures,
which is the parameter list.
– void
void
void
void
foo(int i);
//
foo(double x);
//
foo(const char *); //
foo(int i, int j); //
Function
Function
Function
Function
foo(1); // Calls which?
foo(1.0); // Calls which?
foo("hello"); // Calls which?
foo(1, 2); // Calls which?
1
2
3
4
Overloading Resolution
• When there is an exact match, it is very clear which function is called.
When not, the rules are very complicated.
– void foo(short s);
void foo(int i, int j = 1);
void foo(double x);
foo(1); // Calls which?
– Calls one with default parameter value.
– void foo(short s);
void foo(double x);
foo(1); // Calls which?
– Ambiguous, both are considered equally good.
• Overloading and scopes. Which one is called?
– void f(int);
void g() {
void f(double);
f(1);
}
– Name hiding, calls the inner one.
• Basic process is:
– Generate list of “viable” functions. Those are ones
that have conversions that could be applied.
– Then rank them in terms of preference.
– If two have the same preference, then it is
ambiguous, and won’t compile.
• The rules for overload resolution from the C++ Standard.
const in Overloading
• Is this okay?
– void f1(int i) { … }
void f1(const int i) { … }
– Which one would be called? Would calling the other one
violate any programming language semantics?
• f1(1); int a; f1(a);
– Would you ever use the second one?
• Is this okay?
– void f2(int *i) { … }
void f2(const int *i) { … }
– Which one would be called? Would calling the other
violate any programming language semantics?
• const int k = 1; f2(&k); int a; f2(&a);
Return Type in Overloading
• What does this do?
– void foo(int);
int foo(double x);
…
int i = foo(1);
• Return types are ignored, so above would be a
syntax error.
• What about this?
– void foo(int);
int foo(int);
– Cannot even declare them, since any call foo(1) will
be ambiguous.
Pointers To Overloaded Functions
• Pointers to functions must match exactly during
assignment.
– In other words, there are no conversions.
– double f(int);
double f();
double (*fp1)(int) = &f; // Okay?
double (*fp2)(short) = &f; // Okay?
Return Type Deduction
•
In C++11, there is limited return type deduction in lambdas.
– auto f = []() { return 1; }
•
In C++14, this has been extended to non-lambdas and generalized:
– auto f() {
…
return expr1;
…
return expr2;
…
}
– All return expressions must deduce to the same type.
•
You can have just a declaration, but can’t be called until the body is seen in the
translation unit:
– auto
…
f();
auto
…
f();
f();
// No, body not seen yet.
f() { … }
// Okay.
• Recursion okay, but must have a non-recursive
return first.
– auto f()
…
return
...
return
…
return
}
{
f(); // No.
1;
f(); // Okay.
Command Line Options
• int main(int argc, char *argv[]) {
// argv[0] is usually the command name.
// argv[1] is first arg.
// argc is the number of args + 1.
printf(“%d, %s, %s\n”, argc, argv[0], argv[1]);
}
• Example execution:
– $ ./a.out foo
2, ./a.out, foo
SCOPE AND LIFETIME (STORAGE
DURATION)
Scope
• Scope is the context where a name is “visible”.
• Static (lexical) scope:
– void foo() {
int i, j;
…
goo();
}
void goo() {
int j;
... i ...; // Access i.
... j ...; // Access j.
}
• Dynamic scope:
– void foo() {
int i, j;
…
goo();
}
void goo() {
int j;
... i ...; // Access i.
... j ...; // Access j.
}
• Another example:
– int x = 0;
int f() { return x; }
int g() { int x = 1; return f(); }
– What does g return if static scoping is used? What about
dynamic?
• Returns 1 if dynamic scoping is used, 0 if lexical scoping is used.
Scope vs. Lifetimes
• Names have scope, objects have lifetimes.
• Your parents might call you “Sweetie Pie” at
home. But when you are not at home, that
name is (thankfully) out of scope.
– Do you cease to exist?
• Scopes and lifetime are conceptually distinct,
though some combinations make no sense.
C++ Scopes and Lifetimes
• Three types of scope:
– Local (block)
– Namespace (outermost is global)
– Class
• Three types of lifetimes:
– Automatic
– Static
– Dynamic
Local Scope
• Function or block or statement
– void func() {
int i;
{
int i;
for (int i = 0; i < 10; i++) { … }
}
}
• What is the purpose of introducing another block?
Why do it?
– Sometimes cleaner
– Force a destructor to be called.
• Name in local scope defines a local object.
– Three kinds:
• Automatic (stack)
• Static
• Register
• Automatic
– Automatic storage duration
– How long is the lifetime?
• The end of the block.
– Are they zero-initialized?
• No.
– Is this valid?
• int *foo() {
int i;
return &i;
}
• No.
• Register
– void foo() {
register int index;
for (index = 0; index < 10; index++) {
// …
}
// …
– How many have used this?
– This is mainly of historical interest, most modern code
doesn't use it because compilers are very good at
optimizing, and usually know better than us what to put
into a register.
• Static local objects: Is this safe?
– int *func() {
static int i = 1;
i++;
return &i;
}
• What does it return the first time it is called? Second
time?
• We say that these have static storage duration.
(Global objects also have static storage duration.)
• Guaranteed to be initialized to zero (or null, if it is a
pointer), if not specifically initialized to something.
• Is it thread-safe?
• What does this do? When is the constructor called?
– int func2() {
static A a(1234);
// accessor1() is read-only function.
return a.accessor1();
}
– When is the destructor called?
– Is it thread-safe?
Static Storage Duration
• Objects that have static storage duration are objects that are
not necessarily marked with static keyword, but are in
“permanent” storage that persists for the life of the program.
Examples?
–
–
–
–
–
Global
Namespace
Unnamed namespace
Class static
Function static
• Initialization of non-local, static storage duration objects is
guaranteed before main is invoked, but order between
translation units is not guaranteed.
– Will revisit this.
Linkage
• Linkage refers to how a name is visible during
linking.
• External vs. internal:
– External: Visible outside of the translation unit.
– Internal: Not visible outside of the translation
unit.
Linkage Directives: extern “C”
• Does this work?
– Compiled with gcc –c foo.c:
int foo() { return 1; }
– Compiled with g++ -c main.cpp:
int foo();
int main() {
foo();
}
– Link it all together:
g++ -o exec foo.o main.o
• To make a symbol link with C, need a linkage
directive:
– Calling C function from C++:
• Compiled with gcc –c foo.c:
int foo() { return 1; }
• Compiled with g++ -c main.cpp:
extern “C” int foo();
int main() {
foo();
}
• Link it all together:
g++ -o exec foo.o main.o
– Calling C++ function from C:
• Compiled with gcc –c foo.c:
int foo() { return goo(); }
• Compiled with g++ -c goo.cpp:
extern “C” int
goo() { ... }
• Link it all together:
g++ -o exec main.o foo.o goo.o
• Can wrap a whole set of declarations.
– extern “C” {
// Lots of stuff can go here.
}
• Let’s say you have written a library in C, for
whatever reason (maybe it runs on avionics, or
embedded system, etc.).
• You have created a header file for it. How is this?
MyHeader.h
#ifndef MY_HEADER_H
#define MY_HEADER_H
void my_lib_func1(int);
#endif
main.c
#include “MyHeader.h”
int main() {
my_lib_func1(1234);
}
main.cpp
#include “MyHeader.h”
int main() {
my_lib_func1(1234);
}
• The problem is that the C++ compiler will
generate mangled symbol names, to handle
overloading.
• Need to wrap in extern “C”. How is this?
MyHeader.h
#ifndef MY_HEADER_H
#define MY_HEADER_H
extern “C” {
void my_lib_func1(int);
}
#endif
main.c
#include “MyHeader.h”
int main() {
my_lib_func1(1234);
}
main.cpp
#include “MyHeader.h”
int main() {
my_lib_func1(1234);
}
• The problem is that the C compiler doesn’t
understand extern “C”. So need to use
conditional compilation.
MyHeader.hpp
#ifndef MY_HEADER_HPP
#define MY_HEADER_HPP
#ifdef __cplusplus
extern “C” {
#endif
main.c
#include “MyHeader.h”
int main() {
my_lib_func1(1234);
}
void my_lib_func1(int);
#ifdef __cplusplus
}
#endif
#endif
main.cpp
#include “MyHeader.h”
int main() {
my_lib_func1(1234);
}
const Objects Linkage
• Internal, unless declared extern.
– // File a1.cpp.
const int k1 = 3; // Not visible to other TUs.
// File b1.cpp.
extern const int k1;
int i = k1; // Linker error.
• To define with extern, initialize it.
– // File a2.cpp.
extern const int k2 = 4; // Visible to other TUs.
// File b2.cpp.
extern const int k2;
int i = k2; // Okay.
• To initialize an object with default constructor, do:
– extern const A a = {};
Dynamically Allocated Objects
• Lifetime of global, local objects strictly
defined. Cannot be changed dynamically.
• Dynamically allocated objects can be explicitly
created and destroyed at runtime.
• Where do they come from? Where are they
stored?
Virtual Memory
2 GB
• A process has a range of possible
memory addresses. Typically?
– 0-2GB, 4G, etc.
• What happens when you write or
read from an address?
– If it is not mapped, a page fault, then
OS finds some disk space for it.
– Page/swap can be huge, can be many
GB.
0
Memory Regions
• Regions
Stack
Invalid
Heap
Data
Code
(Text)
– Stack is used for function calls.
– Heap is used for dynamically needed
memory
– Data is for memory that is “static”, like
global variables, etc.
– Text (code) is program machine code.
– How about threads?
– Is it all writable? Executable? Readable?
• What happens when you call new or
malloc(), in Java or C++?
• Memory allocation: first check to see
if any valid, but unused.
– If none available, then request more
valid memory regions from OS, and use
those.
Invalid
Used
Available
• Key point: There are two stages of
memory allocation.
– First, you have to make the memory
valid from the OS point of view.
– Then you have to get the memory from
the user-mode memory manager
(typically malloc())
– malloc() is a manager.
– Why two stages?
• Efficiency
• Flexibility
– What happens if you try to use the
available memory without going
through malloc()?
• How do you get memory from the
OS?
Stack
– In older versions of UNIX, it is a limit
known as the “break”. Anything below
this is valid.
– Newer versions (and likely Windows)
allow regions to be requested via
mmap().
mmap’ed
• When you free or delete something
in Java or C++, will the OS report less
memory usage?
mmap’ed
break
– Not usually, because the user-level
memory manager keeps control of it.
new
• Use new to allocate an object (primitives are also often
referred to as objects).
– A *a = new A;
– int *ip = new int;
• Is the int *ip initialized to anything? What about the
object *a?
– No default initialization for *ip, but any default constructor will
be called for *a.
– Use this syntax to give the int a value:
• int *ip = new int(123);
int *ip2 = new int();
• Can also pass parameters to constructor:
– A *a = new A(1, 2);
• What happens if all the memory is used up? Is it a
good idea to check for that?
– int *ip = new int(123);
if (ip == NULL) {
fprintf(stderr, "Free store”
“ exhausted, go home...\n");
abort();
}
– Turns out that it will throw an exception.
delete
• To free memory, use delete:
– A *a = new A;
int *ip = new int;
int *null = 0;
// …
delete a;
delete ip;
delete null; // Okay?
– Standard guarantees that deleting null pointer is okay.
• Is the destructor called? Is the memory zero-ed out?
– Should it be?
– Why might we desire that the memory be zero-ed out?
(Hint: Think defensive programming.)
• Lifetime of pointer vs. lifetime of object pointed to:
– int *ip;
int *get() {
if (ip == 0) {
ip = new int;
}
return ip;
}
void free_it() {
if (ip != 0) {
delete ip;
}
}
– What is the lifetime of ip?
– What is the lifetime of the object allocated?
– Is it thread-safe?
– How might you improve the defensive programming aspect of the
above code?
• Some delete examples. Which are errors? Which are
run-time vs. compile-time?
– void f() {
int i;
string str = "bananas";
int *pi = &i;
short *ps = 0;
double *pd = new double(33);
delete
delete
delete
delete
}
str; // ?
pi; // ?
ps; // ?
pd; // ?
Arrays and New
• Two-dimensional arrays in C are really an array of arrays:
– int a[3][4];
// How is it laid out in memory?
0 1 2 3
4 5 6 7
8 9 10 11
•
•
•
0 1 2
3 4 5
6 7 8
9 10 11
[Show array_layout.]
C arrays are row major, which means that the left one is correct.
How do you compute the address of a[i][j], given a pointer to char named base?
• base + i*sizeof(int [4]) + j*sizeof(int)
• Which dimension was not needed?
• 3-D arrays are similar:
– int a[2][3][4];
Plane 0
0 1 2 3
Planes
Columns
Rows
4 5 6 7
8 9 10 11
Plane 1
12 13 14 15
16 17 18 19
20 21 21 22
•
How do you compute the address of a[i][j][k], given a pointer to char named base?
• base + i*sizeof(int [3][4]) + j*sizeof(int [4])
+ k*sizeof(int)
• Which dimension was not needed?
• Arrays allocated like this:
– int *ia = new int[10];
int (*two_d)[10] = new int[4][10];
A *a = new A[10];
– Are the arrays initialized?
• No.
• Does this work?
– int (*alloc(int n))[10] {
return new int[n][10];
}
– Yes.
• How about this?
– new int[n][m];
– Why not? Think of what the compiler has to do. What is the index expression?
0 1 2 3
...
?
?
?
?
...
?
?
?
?
...
a[i][j]?
base + i*sizeof_of_row + j*sizeof(int)
• Write a function to implement a 2 by 4 array from a linear 8 element array.
– int *linear_array = …;
int index(int row, int col) {
return *(linear_array + row*n_cols + col);
}
• Arrays need to be deleted with a special syntax.
– int *i_array = new int[10];
A *a_array = new A[10];
delete [] i_array;
delete [] a_array;
• Global new and delete:
– void *::operator new(size_t);
void ::operator delete(void *);
void *vp = operator new(10);
operator delete(vp);
• Does this work?
– struct Foo { double x; };
Foo *f = (Foo *) ::new(sizeof(Foo));
– How safe is it? What if Foo has a constructor or
destructor?
Placement New
• Suppose you have two processes:
– Want to share memory between them.
– Want to put C++ objects in that memory.
– What do you do?
• Suppose you are working on an embedded system.
– You want to construct objects in special memory.
– You know the memory begins at location 0x8000000.
– What do you do?
• In each of these cases, you want to construct an object in
special memory.
– How?
• What we want to do is to construct an object, but only at a specific
location in memory. We can use placement new to do that:
– SpecialObjClass *o
= new (special_addr) SpecialObjClass(...);
• Can we delete it like this?
– delete o;
• No, because that will try to return the memory to the free memory
pool. Need to make explicit destructor call.
– o->~SpecialObjClass();
Overloaded new and delete
• These can be overloaded to provide special
functionality.
• [Show overloaded_new.]
Summary
Scope
Namespace
Namespace,
unnamed
Static global
Global
Local, automatic
Local, static
New
Class
Class, static
Lifetime
Linkage
Summary
Scope
Lifetime
Linkage
Namespace
Translation unit Static
External
Namespace,
unnamed
Translation unit Static
Internal
Static global
Translation unit Static
Internal
Global
Translation unit Static
External
Local, automatic
Block
Block
Internal
Local, static
Block
Static
Internal
New
N/A
Dynamic
N/A
Class
Class
Same as
associated
object
Same as
associated
object
Class, static
Class
Static
External
NAMESPACES
Name Clashes
• Suppose you are using someone’s library for graph
algorithms.
– They might have a class called Node.
• Suppose you want to distribute these algorithms
over the network, so you also use someone’s
network library.
– They might also have a class called Node.
• Suppose you have a single implementation file
(.cpp) that needs to use both of these classes.
What will happen? What is the solution?
– Suppose no namespaces.
Namespaces
• The solution in the old days, before
namespaces, was to use some unique prefix.
– joes_graph_alg_Node *node1;
janes_network_lib_Node *host;
– What is the disadvantage of this?
• Namespaces are designed to provide a
programming language means to separate and
organize names.
• The global scope is known as the global namespace scope.
• Within that global scope, we can define namespaces.
– extern int a;
namespace ns1 {
extern int b;
class A {…};
void f() {…}
}
• Can be re-opened.
– namespace ns1 { … }
namespace ns2 { … }
namespace ns1 { … }
• Scope resolution operator.
– Outside of a namespace, you can refer to an namespace member with
the :: resolution operator.
• namespace ns1 { int a; …}
ns1::a = 1;
• Nested namespaces
– namespace ns1 {
namespace ns2 {
int a;
}
}
– ns1::ns2::a = 2;
• Suppose you want to access a variable from several different
functions (or classes).
– Maybe you just want it to be accessed from functions all in a single
translation unit file.
– But not visible to anything outside of the translation unit.
– How do you do it?
• Unnamed namespace
– namespace {
int a;
}
static int b; // Same effect, but deprecated.
• Namespace aliases
– namespace International_Business_Machines {
int a;
}
namespace ibm = International_Business_Machines;
ibm::a = 1;
Using Declarations
• Using declarations
– namespace ns1 {
void f1();
void f2();
}
namespace ns2 {
using ns1::f2;
}
void func2() {
f1(); // Syntax error.
using ns1::f1;
f1();
using ns2::f2;
f2(); // Transitive.
}
• Using declarations introduce the name at the point of the
declaration, as if it had been redeclared at that point.
Using Directives
• Using directives
– namespace ns1 {
void some_func();
}
void f1() {
some_func(); // Error.
}
void f2() {
using namespace ns1; // Okay.
some_func();
}
– Using directives have the effect of removing the namespaces from
names, at the point where they were declared/defined in the
namespace.
• Example: using namespace std;
– Can you put a using directive in a header file? What happens if you
do?
• Suppose Jane has code like:
– #include <lib1.hpp>
class map { … };
…
• lib1.hpp was written by someone else and has inside of it
somewhere:
– … std::map …
• Jane decide that there is some useful functionality in your library, so
they decide to use it. You have a using namespace std
directive in your header file.
– #include <YourLib.hpp>
#include <lib1.hpp>
class map { … };
– What would happen?
– If you have using namespace std in your header file this
means that merely including your header file would result in syntax
errors in totally unrelated header files.
• Using directives cannot be in class scope.
• Technically, the names are injected into the nearest scope
that includes both the directive and the namespace being
injected.
– namespace ns1 {
namespace ns2 {
namespace ns3 { … }
}
namespace ns4 {
// Injected into ns1.
using namespace ns2::ns3;
}
}
• Using directives are transitive. This can lead to ambiguity. However,
qualified name lookup will cause a priority search instead.
– namespace N {
int i1;
int i2;
}
namespace M {
int i1;
using namespace N;
}
namespace L {
using namespace M;
}
int main() {
using namespace L;
i1 = 3; // Ambiguous.
i2 = 3; // Ambiguous.
L::i1; // Okay.
L::i2; // Okay.
}
• namespace ns1 {
int i;
}
namespace ns2 {
using namespace ns1;
int j = i;
int i = 3;
}
int main() {
using namespace ns2;
i = 2;
ns2::i = 1;
}
Using Declarations vs. Using Directives
• Using declarations make a single name visible. Using directives
make a whole namespace visible.
• Declarations:
– namespace ns1 {
void f();
}
void f2() {
using ns1::f;
…
}
– As if function had been declared:
void f2() {
void f();
…
}
• Directives:
– namespace ns1 {
void f();
}
void f2() {
using namespace ns1;
}
– Same as:
void f();
void f2() {
…
}
• A using declaration re-declares the name as it
exists at the point of re-declaration.
– namespace ns {
void foo(double);
}
using ns::foo;
namespace ns {
void foo(int);
}
int main() {
foo(3); // Calls?
}
• A using directive essentially “unwraps” the
namespace, even after the directive.
– namespace ns {
void foo(double);
}
using namespace ns;
namespace ns {
void foo(int);
}
int main() {
foo(3); // Calls?
}
Overloading and Namespaces
• When you use a using declaration, it is the same as
redeclaring the name in the associated scope.
– namespace my_lib {
int max(int, int);
double max(double, double);
}
char max(char, char);
namespace my_lib {
short max(short, short);
}
void func() {
max(87, 65);
max(35.5, 76.6);
max('J', 'L');
max(short(1), short(2));
}
– namespace my_lib {
int max(int, int);
double max(double, double);
}
char max(char, char);
using my_lib::max;
namespace my_lib {
short max(short, short);
}
void func() {
max(87, 65);
max(35.5, 76.6);
max('J', 'L');
max(short(1), short(2));
}
– namespace my_lib {
int max(int, int);
double max(double, double);
}
char max(char, char);
namespace my_lib {
short max(short, short);
}
using my_lib::max;
void func() {
max(87, 65);
max(35.5, 76.6);
max('J', 'L');
max(short(1), short(2));
}
– namespace my_lib {
int max(int, int);
double max(double, double);
}
char max(char, char);
namespace my_lib {
short max(short, short);
}
void func() {
using my_lib::max;
max(87, 65);
max(35.5, 76.6);
max('J', 'L');
max(short(1), short(2));
}
– namespace my_lib {
int max(int, int);
double max(double, double);
}
char max(char, char);
using namespace my_lib;
namespace my_lib {
short max(short, short);
}
void func() {
max(87, 65);
max(35.5, 76.6);
max('J', 'L');
max(short(1), short(2));
}
– namespace my_lib {
int max(int, int);
double max(double, double);
}
char max(char, char);
namespace my_lib {
short max(short, short);
}
void func() {
{
using namespace my_lib;
max(87, 65);
max(35.5, 76.6);
max('J', 'L');
max(short(1), short(2));
}
max(87, 65);
}
Name Hiding and Overloading
• Which function does this call?
– void foo(const char *);
namespace ns {
void foo(double x);
void goo() {
foo("hello");
}
}
Scope Resolution Operator and
Namespaces
•
There are some subtle interactions:
– namespace ns {
void foo(int);
void goo(int);
void moo(int);
}
using ns::foo;
void foo(int) {} // Syntax error.
using namespace ns;
void goo(int) {} // Okay.
int main() {
goo(1); // Syntax error, ambiguous.
::goo(1); // Okay, calls global.
::moo(1); // Okay, calls ns::moo.
}
Another Example
• Consider:
– namespace blip {
int bi = 16, bj = 15, bk = 23;
};
int bj = 0;
void manip() {
using namespace blip; // Clash on bj?
++bi; // ?
++bj; // ?
++::bj; // ?
++blip::bj; // ?
int bk = 97; // Clash?
++bk;
}
• Consider:
– namespace ns {
int k;
};
using namespace ns;
int k; // Okay?
void foo() {
using ns::k;
int k; // Okay?
// ...
}
Linkage
• How is linkage of namespace members implemented?
– // file1.cpp
namespace A {
int i;
}
int i;
– // file2.cpp
namespace A {
void f() {
int j = i; // Reads A::i.
…
}
}
void f() {
int j = i; // Reads ::i;
…
}
• Name mangling again.
MULTIPLE INHERITANCE AND
VIRTUAL INHERITANCE
Casting To and From void *
• Casts are dumb.
– They often don’t require any machine instructions.
– They just change the type of a pointer.
• Consider:
– struct A {
int i;
};
struct B {
char buf[10];
int i;
};
A *ap = new A;
ap->i = 1234;
B *bp = (B *) ap;
// Are bp and ap actually different addresses?
cout << ap->i << endl;
cout << bp->i << endl;
• Consider:
– class Base {… };
class Derived : public Base { … };
void foo(void *vp) {
Base *bp = (Base *) vp;
...
}
Derived *dp = new Derived;
foo(dp); // Okay?
– (Derived *) (void *) dp == dp; // ?
Base *bp = dp;
(Base *) (void *) dp == bp; // ?
– [Show void_star_cast.]
Multiple Inheritance
• Do we have it in the real world?
• A class in C++ can inherit from multiple base
classes.
– Members with same name do not conflict unless
they are used in an ambiguous way.
• An attempt to call, from the derived class, a method
that is defined in both base classes would be
ambiguous, for example.
– Scope resolution operator (::) can be used to
disambiguate.
struct
struct
struct
struct
struct
B1 { void foo1(); … };
B2 { void foo2(); … };
B3 : public B1, public B2 { void foo3(); … };
B4 { void foo4(); … };
D : public B3, public B4 { void foo5(); … };
B1:
void foo1();
B2:
void foo2();
B3:
void foo3();
B4:
void foo4();
D:
void foo5();
• What functions are available at D?
• What might the layout of a derived object look like in single
inheritance and no polymorphism? Consider:
– class A {…};
class B : public A {…};
class C : public B {…};
• What is needed to upcast or downcast? What do you expect the
following code print?
– C c;
C *cp = &c;
B *bp = &c;
A *ap = &c;
printf(“C: %p, B: %p, A: %p\n”,
(void *) cp, (void *) bp, (void *) ap);
Complete
C object
B subobject
A subobject
B part
C part
The A
subobject
begins at
address 16
•
What does the layout of a derived object look like in multiple inheritance?
Consider:
– struct B1 { int b1; };
struct B2 { int b2; };
struct B3 : public B1, public B2 { int b3; };
struct B4 { int b4; };
struct D : public B3, public B4 { int d; };
B1 subobject
begins at address 16
B3 subobject
Complete
D object
B4 subobject
B1 subobject:
b1
B2 subobject:
b2
B3 part:
b3
B4 subobject:
b4
D part:
d
B1
b1
B2
b2
B3
b3
B4
b4
D
d
•
What is needed to upcast or downcast? What does the following code print?
– D d;
B1 *b1p = &d; B2 *b2p = &d; B3 *b3p = &d; B4 *b4p = &d;
printf(“D:%p, B1:%p, B2:%p, B3:%p, B4:%p\n”,
(void *) &d, (void *) b1p, (void *) b2p,
(void *) b3p, (void *) b4p);
B1 subobject
begins at address 16
B3 subobject
Complete
D object
B4 subobject
B1 subobject:
b1
B2 subobject:
b2
B3 part:
b3
B4 subobject:
b4
D part:
d
B1
b1
B2
b2
B3
b3
B4
b4
D
d
• Revisit casting to/from void *:
– D *dp = 16;
void *vp = (void *) 16;
(B4 *) vp ==? what address;
(B4 *) (void *) dp ==? (B4 *) dp;
B1 subobject
begins at address 16
B3 subobject
Complete
D object
B4 subobject
B1 subobject:
b1
B2 subobject:
b2
B3 part:
b3
B4 subobject:
b4
D part:
d
B1
b1
B2
b2
B3
b3
B4
b4
D
d
• What order are base class constructors called?
– struct B1 {
B1(B2 *);
…
};
struct B2 {
…
};
class D : public B1, public B2 {
…
};
D::D() : B2(…), B1(this) { // Okay?
…
}
• Which foo() gets called?
– struct B1 {
void foo();
};
struct B2 {
void foo();
};
struct D : public B1, public B2 {};
D d;
// Does this call B1::foo() or B2::foo()?
d.foo();
• Ambiguous or not?
– class B1 {
private:
void foo();
};
class B2 {
public:
void foo();
};
struct D : public B1, public B2 {};
D d;
// Does this call B1::foo() or B2::foo()?
d.foo();
• Which foo() gets called?
– struct B1 {
void foo(int);
};
struct B2 {
void foo(double);
};
struct D : public B1, public B2 {};
D d;
d.foo(12); // What happens?
• Conversions to base class pointer may be ambiguous:
– struct B1 { … };
struct B2 { … };
struct D : public B1, public B2 { … };
extern foo(const B1 &);
extern foo(const B2 &);
D d;
foo(d); // What happens?
• The ambiguity is “latent”.
– struct B1 { void foo(); };
struct B2 { void foo(); }:
struct D : public B1, public B2 {
void goo();
};
D d; // Is this okay?
d.foo(); // Is this okay?
• Error doesn’t happen unless/until you actually
try to call an ambiguous function.
Resolving Ambiguities
• You can always use a scope resolution operator.
– struct B1 { void foo(); };
struct B2 { void foo(); }:
struct D : public B1, public B2 {};
D d;
d.B1::foo();
• But in this case, the user must know which one is correct.
Better for class designer to resolve it by forwarding.
– struct B1 { void foo(); };
struct B2 { void foo(); }:
struct D : public B1, public B2 {
// Forwarding function.
void foo() { B1::foo(); }
};
D d;
d.foo();
• Or use a using declaration.
– struct B1 { void foo(); };
struct B2 { void foo(); }:
struct D : public B1, public B2 {
// Using declaration.
using B1::foo;
};
D d;
d.foo();
Virtual Functions
• Multiple inheritance can be used with virtual
functions.
– The actual function called is determined by following the
inheritance tree downwards from the type used in
invocation.
• B *b = …;
b->func(); // If func is virtual, follow the
// tree down from B.
• class B1 {
public: virtual void foo1();
virtual void foo();
};
class B2 {
public: virtual void foo2();
virtual void foo();
};
class D : public B1, public B2 {
public: virtual void foo1();
virtual void foo2();
virtual void foo();
};
D d; B1 &b1(d); B2 &b2(d);
b1.foo1(); // Calls ?
b2.foo2(); // Calls ?
b1.foo(); // Calls ?
B1
B2
D
•
class A1 {
public: virtual void foo() = 0;
};
class A2 {
public: virtual void foo() = 0;
};
class B1 : public A1 {
public: virtual void foo();
};
class B2 : public A2 {
public: virtual void foo();
};
class C : public B1, public B2 {};
C c;
c.foo(); // Okay?
static_cast<A1*>(&c)->foo(); // Calls
static_cast<A2*>(&c)->foo(); // Calls
A1:
foo() = 0
A2:
foo() = 0
B1:
foo()
B2:
foo()
C
which foo()?
which foo()?
Pure Virtual Functions
(Abstract Base Class)
• MI can be mixed with pure virtual functions.
– For a class to be instantiable, all PVFs must be
defined.
– class B1 {
public: virtual void f1() = 0;
};
class B2 {
public: virtual void f2() = 0;
};
class D : public B1, public B2 {
public: virtual void f1() {}
};
class E : public D {
public: virtual void f2() {}
};
D d; // Okay?
E e; // Okay?
B1
B2
D
E
MI with Repeated Base Class
• How many A subobjects in a C object?
– struct
struct
struct
struct
A { int i_var; };
B1 : public A {};
B2 : public A {};
C : public B1, public B2 {};
A
A
B1
B2
B1 subobject
Complete
C object
B2 subobject
C
• Which i_var does this access?
– C c;
c.i_var; // Which i_var?
A subobject
B1 part
A subobject
B2 part
C part
Virtual Base Classes
• The subobjects are different, unless the base class is
virtual.
– This is an overloading of the use of the term virtual.
• Example
– class A { public: int a; };
class B1 : virtual public A {};
class B2 : virtual public A {};
class C : public B1, public B2 {};
C c;
c.a; // Only one copy.
• How many A subobjects in a C object?
– class
class
class
class
A { public: int a_member; };
B1 : virtual public A { int b1;};
B2 : virtual public A { int b2; };
C : public B1, public B2 { int c; };
A
B1
B2
C
Complete
C object
B1 subobject
B2 subobject
Diamond inheritance
• No more ambiguity
– C c;
c.a_member; // Which a_member?
A subobject
B1 part
B2 part
C part
Address 0
A
B1
B1 subobject
B2
Complete
C object
C
B2 subobject
A subobject
B1 part
B2 part
C part
Address 0
A
B0
B1
C
A subobject
B2
Complete
C object
B1 subobject
B2 subobject
B0 part
B1 part
B2 part
C part
B0 subobject
• [Show vb_cast.]
• Under virtual inheritance, a cast may be a
function call.
Construction under Virtual Inheritance
• Okay?
– struct A {
A(const char *l) { … }
};
struct B1 : public A { // Non-virtual
B1() : A(“B1”) {}
};
struct B2 : public A { // Non-virtual
B2() : A(“B2”) {}
};
– How about this?
• struct C : public B1, public B2 {};
• Okay?
– struct A {
A(const char *l) { … }
};
struct B1 : virtual public A { // Virtual
B1() : A(“B1”) {}
};
struct B2 : virtual public A { // Virtual
B2() : A(“B2”) {}
};
• How about this?
– struct C : public B1, public B2 {};
• What parameter is passed to the constructor of
A?
• The most derived type must call the ctor:
– struct A {
A(const char *l) { … }
};
struct B1 : virtual public A { //
Virtual
B1() : A(“B1”) {}
};
struct B2 : virtual public A { //
Virtual
B2() : A(“B2”) {}
};
struct C : public B1, public B2 {
C() : A(“C”) {}
};
Other Patterns
• Can have other different inheritance patterns:
A
A
B1
B1
B2
B2
A
A
B3
B4
C
C
Initialization of Static-Storage Objects
• What are they?
• Static storage objects are objects that are not
necessarily marked with static keyword, but are in
“permanent” storage that persists for the life of the
program. Examples?
–
–
–
–
–
Global
Namespace
Unnamed namespace
Class static
Function static
• Are these okay?
– class A { int foo(); … };
class B { B(int); … };
A a;
B b(a.foo()); // Okay?
extern A a2;
B b2(a2.foo()); // Okay?
A a2;
• What will happen here?
– class C { C(int); int foo(); … };
extern C c1, c2;
C c1(c2.foo());
C c2(c1.foo());
• How about these?
– // file1.cpp
extern A a2;
B b1(a2.foo());
A a1;
– // file2.cpp
extern A a1;
B b2(a1.foo());
A a2;
• Note that if there are no cycles, it would be
plausible to require that the compiler/linker
do a topological sort so that objects are
always constructed before use.
Static Initialization vs. Dynamic
Initialization
• Two kinds for static storage duration objects:
– Static initialization: POD type, 0 or with constant.
• int i(123);
struct A { int i, j; }
A a = {1, 2};
– Dynamic initialization: All else.
• A a; // With ctor.
int i = foo();
Local Objects
• The rule is:
Non-Local
• The rules are:
// File1
#include “a.h”
#include “b.h”
B b;
A::A() { b.Use(); }
// File2
#include “a.h”
A a;
// File3
#include
#include
extern A
extern B
“a.h”
“b.h”
a;
b;
int main() {
a.Use();
b.Use();
}
• The gist of it is:
– The initialization order of static storage objects
within a translation unit is in the order in which
their definition appears in the translation unit.
There is no ordering guarantee for objects in
different translation units.
• Solutions?
– A &useA() {
static A a;
return a;
}
Temporaries
•
Consider this String class:
– class String {
public:
String(const char *s = “”)
: str(strdup(s.str)), size(strlen(s) { }
String(const String &s)
: str(strdup(s.str), size(s.size) { }
~String() { free(str); }
String &operator=(const String &s) {
delete [] str;
str = strdup(s.str);
size = s.size;
}
private:
const char *str;
size_t size;
};
String s;
s = “hello”;
Rvalue References
• Rvalue references bind only to temporaries.
• Thus, you can overload on whether or not the
argument is a temporary.
• This allows you to steal the resources of a
temporary, since it has no use for it anyway.
“Move” Constructors/Assignment
• With move functions:
– class String {
public:
String(const char *s = “”)
: str(strdup(s.str)), size(strlen(s)) { }
String(String &&s) : str(s.str), size(s.size) {
s.str = nullptr;
s.size = 0;
}
~String() { free(str); }
String &operator=(const String &s) {
delete [] str;
str = strdup(s.str);
size = s.size;
}
String &operator=(String &&s) {
swap(str, s.str);
swap(size, s.size);
}
private:
const char *str;
size_t size;
};
String s;
s = “hello”;
Is an rvalue Reference an rvalue?
• Consider:
– void foo(A &&a) { … }
void foo(A &a) { … }
void goo(A &&a) {
foo(a); // Calls which overload?
cout << a << endl;
}
– The type of an rvalue reference is not an rvalue
reference!
– The rule is that if it has a name, then it is an lvalue.
Move Constructors under a Base Class
• Consider a class with a base class:
– struct Base {
Base(Base &&b); // Move ctor.
…
};
struct Derived : public Base {
Derived(Derived &&d) : Base(d) { … }
…
};
– Works?
– struct Derived : public Base {
Derived(Derived &&d)
: Base(static_cast<Base &&>(d)) { … }
• This is done often enough that there is a std::
function for it:
– struct Base {
Base(Base &&b); // Move ctor.
…
};
struct Derived : public Base {
Derived(Derived &&d)
: Base(std::move(d)) { … }
…
};
Operators
•
Consider:
– template <typename T>
class Vector {
public:
Vector(size_t sz) : (new T[sz]), size(sz) { }
Vector &operator=(const Vector &v) {
// Copy to data.
return *this;
}
private:
Vector(T *d, size_t sz) : data(d), size(sz) { }
T *const data;
const size_t size;
};
template <typename T>
Vector<T>
operator+(const Vector<T> &v1, const Vector<T> &v2) {
T *d = new T[v1.sz];
// Fill.
return Vector<T>(d, v1.sz);
}
– v1 = v2 + v3 + v4;
•
Write “move” version:
–
–
•
template <typename T>
Vector<T> &&
operator+(const Vector<T> &&v1, const Vector<T> &v2) {
for (size_t i = 0; i < v1.size; i++) {
v1.data[i] += v2.data[i];
}
return std::move(v1);
}
v1 = v2 + v3 + v4;
This requires a separate version, if, for example, v2 is the rvalue instead of v1. Need:
–
template <typename T1, typename T2>
auto
operator+(T1 &&v1, T2 &&v2) -> decltype(std::move(v1)) {
Vector<T> &&rv(the_rvalue(v1, v2));
Vector<T> &lv(the_lvalue(v1, v2));
for (size_t i = 0; i < v1.size; i++) {
rv.data[i] += lv.data[i];
}
return std::move(rv);
}
•
Also consider:
– template <typename T, size_t N>
class Vector {
public:
Vector &operator=(const Vector &v) {
// Copy to data.
return *this;
}
private:
T data[N];
};
template <typename T, size_t N>
Vector<T, N>
operator+(const Vector<T,N> &v1, const Vector<T,N> &v2) {
Vector<T, N> v;
// Fill v.data.
return v;
}
– v1 = v2 + v3 + v4;
Example: swap
• [Show rvalue_swap.]
• Critique this:
– template <typename T>
void swap(T &o1, T &o2) {
T tmp(o1);
o1 = o2;
o2 = tmp;
}
• Using std::move:
– #include <utility>
template <typename T>
void swap(T &o1, T &o2) {
T tmp(std::move(o1));
o1 = std::move(o2);
o2 = std::move(tmp);
}
Forwarding
• What if we want to write a template as generally
as possible, but also need to call some other
functions:
– // For non-rvalues.
template <typename T>
void foo(const T &o) {
goo(o);
}
– // For rvalues.
template <typename T>
void foo(T &&o) {
goo(std::move(o));
}
• What if we gave more parameters, each of which may either be movable
or not:
– template <typename T>
void foo(const T &o1, const T &o2) {
goo(o1, o2);
}
template <typename T>
void foo(T &&o1, const T &o2) {
goo(std::move(o1), o2);
}
template <typename T>
void foo(const T &o1, T &&o2) {
goo(o1, std::move(o2));
}
template <typename T>
void foo(T &&o1, T &&o2) {
goo(std::move(o1), std::move(o2));
}
• This is obviously rather unmanageable.
• Two part solution: First, create special deduction
rules for rvalue ref parameters.
– template <typename T>
void foo(T &&o) { … }
– T is A & if called on lvalue of type A. T is A if called on
an rvalue of type A. T is const A & if called on const
lvalue of type A.
• So:
– A a;
const A a2;
foo(a); // T is A &.
foo(get_an_A()); // T is A.
foo(a2); // T is const A &.
• Then, we need special rules for “collapsing” references.
– If T is A &, then what is T &&?
• Rules are:
–
–
–
–
A& & becomes A&
A& && becomes A&
A&& & becomes A&
A&& && becomes A&&
• So, we can then write:
– template <typename T>
void foo(T &&o1, T &&o2) {
goo(static_cast<T&&>(o1), static_cast<T&&>(o2));
}
– This is done often enough such that there is a standard function for it:
std::forward.
– template <typename T>
void foo(T &&o1, T &&o2) {
goo(std::forward<T>(o1), std::forward<T>(o2));
}
Pointers to Members
• Say that you have a class with two similar methods, op1 and op2.
– class A {
…
void op1(); // The two are similar but not
void op2(); // the same.
};
• Now you want to write a function to repeat any operation N times.
How would you do this?
– All problems in computer science can be solved with another level of
indirection.
– Butler Lampson
•
This suggests function pointers. How is this?
– void repeat(int n_reps, void (*fp)()) {
for (int i = 0; i < n_reps; i++) {
(*fp)();
}
}
…
repeat(10, &op1); // Do op1 ten times.
repeat(11, &op2); // Do op2 eleven times.
– How about?
repeat(10, &A::op1);
repeat(11, &A::op2);
– Where’s the object?
•
How about this below?
– void repeat(int n_reps, A *a, void (*fp)()) {
for (int i = 0; i < n_reps; i++) {
a->(*fp)();
}
}
…
repeat(10, &a, &A::op1);
– More reasonable, but syntax is wrong, because a function pointer is very different from a
pointer to a member.
• Can you do this?
– struct A {
void f1() { … }
};
void (*func_ptr)();
func_ptr = &A::f1; // Okay?
• Pointers to member functions. Examples:
– struct A {
int f1(int i) { … }
int f2(int i) { … }
};
int (A::*fp)(int);
A a;
fp = &A::f1;
(a.*fp)(1); // Calls A::f1(1).
fp = &A::f2;
(a.*fp)(1); // Calls A::f2(1).
– void foo(A *ap, int (A::*fp)(int));
foo(&a, &A::f1);
• #include <stdio.h>
class A {
public:
int f(int) {
printf("Called A::f().\n"); }
int g(int) {
printf("Called A::g().\n"); }
};
void func(A *ap, int (A::*ptm)(int)) {
(ap->*ptm)(0);
}
int main() {
A a;
func(&a, &A::f);
func(&a, &A::g);
}
• Pointer to static member function: Not associated
with object, so same as regular function pointer.
– struct A { static void f(); };
void (*fp)() = &A::f;
• Can also have pointers to data members.
– struct A { int i, j; };
A a;
int A::*ip;
ip = &A::i;
a.*ip = 1234;
ip = &A::j;
a.*ip = 5678;
• A pointer-to-member of a base class can be converted
to one of the derived class, but not vice versa:
– struct A {
void foo1();
};
struct B : public A {
void foo2();
};
void (A::*ptm1)() = &B::foo2; // Error.
void (B::*ptm2)() = &A::foo1; // Okay.
PtM Example
• Suppose you were writing the code for the computer-controlled player in
a game.
– class Player {
public:
void fire_long_bow();
void fire_crossbow();
...
};
if (complicated_decision_to_use_longbow) {
while (complicated_decision_to_keep_fighting) {
npc->fire_long_bow();
}
} else {
while (complicated_decision_to_keep_fighting) {
npc->fire_crossbow();
}
}
• Could make the decision once, then use a flag:
– bool use_long_bow = false;
if (complicated_decision_to_use_longbow) {
use_long_bow = true;
}
while (complicated_decision_to_keep_fighting) {
if (use_long_bow) {
npc->fire_long_bow();
} else {
npc->fire_crossbow();
}
}
• Gets messy with lots of weapons.
– while (complicated_decision_to_keep_fighting) {
switch (weapon_type_decided_in_code_above) {
case LONG_BOW:
npc->fire_long_bow();
break;
case CROSSBOW:
npc->fire_crossbow();
break;
case SLING:
npc->fire_sling();
break;
default:
npc->uh_oh_run_away();
}
• Use pointer-to-member:
– void (Character::*fire)();
if (complicated_decision_to_use_longbow) {
fire = &Character::fire_long_bow;
} else {
fire = &Character::fire_crossbow;
}
while (complicated_decision_to_keep_fighting) {
(npc->*fire)();
}
TEMPLATES
Introduction
• How is a template different from normal
source code?
– void foo() {…}
template <typename T>
void foo1() {…}
– Template definitions are not really “compiled”.
• Just cause things to be remembered.
Templates Are Like Super Macros
• Where do you put templates, header files or
implementation files?
– Every use must be preceded in the same
translation unit by its definition.
– Private template could be in an implementation
file.
• A template is just that, a template or “pattern”.
– Essentially a macro on steroids.
• Normal source code is compiled on a one-to-one
basis.
void
f(int i) {
…
}
One function in
source code
f:
Compilation
save_regs
ld r0, sp(0)
add
ret
One function
assembly
language
• A single template serves as a pattern, so it can be
used multiple times to create multiple
“instantiations”.
template <typename T>
void f(T i) {… }
One function in
source code
Compilation &
instantiation
f:
f:
save_regs
ld r0, sp(0)
add 4
ret
f:
save_regs
ld r0, sp(4)
add 8
ret
save_regs
ld r0, sp(8)
add 16
ret
Multiple functions in assembly language
Compilation
Instantiation
template
<typename T>
void
f(T i)
{…}
void
f(char i)
{…}
f<char>:
save_regs
ld r0, sp(0)
add 4
ret
void
f(int i)
{…}
f<int>:
save_regs
ld r0, sp(4)
add 8
ret
void
f(double i)
{…}
f<double>:
save_regs
ld r0, sp(8)
add 16
ret
• What happens when compiler encounters a
normal function definition? A template
definition?
– void foo() {…} // Normal function.
template <typename T>
void foo1() {…}
– Template definitions are not directly “compiled”
when encountered by the compiler.
• Just cause things to be remembered, for later
instantiation.
Templates and Classes as Models
• Both are “models”. (What is a model?)
– Classes are models for objects. An object:
•
•
•
•
Has source code (member functions).
Has data (member variables).
But source code never differs.
Data layout never differs. Only the values differ.
– Templates go back one step. They are models for classes or
code. You first instantiate a template to fix a particular
source code and data layout.
• The source code of different instantiations can differ.
• The data layout of different instantiations can differ.
• Sometimes known as parametric polymorphism (compared to
subtype polymorphism).
Example
• Suppose you want to define a function to find
the minimum of two integers:
– int min(int i1, int i2) {
return i1 < i2 ? i1 : i2; }
• Now how about for doubles:
– double min(double x1, double x2) {
return x1 < x2 ? x1 : x2; }
• Now how about long longs…
– Solution?
• Could use a macro:
– #define min(x, y) \
((x) < (y) ? (x) : (y))
• Disadvantages?
– Side effects, due to double evaluation.
– Hard to debug, especially for multiline.
– Code bloat, since they are inherently inlined.
• Function template:
– template <typename T>
// Same as “template <class T>”
T min(T v1, T v2) {
return (v1 < v2) ? v1 : v2; }
– Is this right?
• g++ standard library definition:
– template<typename _Tp>
inline const _Tp&
min(const _Tp& __a, const _Tp& __b) {
if (__b < __a) return __b;
return __a;
}
– Why the underscores?
• Why do we have parentheses around the
parameters?
– #define min(x, y) \
((x) < (y) ?
(x)
:
(y))
• Because substitution is purely lexical. Without
parentheses, it would be translated as:
– #define min(a, b) (a < b ? a : b)
min(x & 0xff, y)
Translated to
a
b
a
b
(x & 0xff < y ? x & 0xff : y)
• Do we need to do the same thing with templates?
– template<typename T>
inline const T&
min(const T& a, const T& b) {
if ((b) < (a)) return (b);
return (a);
}
– min(x & 0xff, y)
• No, because template instantiation is not lexical.
– In some sense, you could say that the compiler inserts the
parentheses for you.
Four Kinds
• Alias templates
– Patterns for type aliases (typedefs).
– template <typename T>
using ptr = T *;
ptr<int> ip; // ip is a pointer to an int.
• Function templates
– “Patterns” for free-standing functions
– template <typename T1, typename T2>
void f(const T1 &o1, const T2 &o2) { … }
• Class templates
– “Patterns” for an entire class, including member functions and member
variables.
– template <typename T1, typename T2>
class A { … };
• Member templates
– “Patterns” for a single member function inside a class (which may or
may not be a templated class).
– struct A {
template <typename T1>
void f(const T1 &) {…}
…
};
Template Parameters
• Each template has a list of template parameters. When the
template is actually used, the parameters are filled in with
real things, and an actual function or class is generated. This is
known as an instantiation.
– template <typename T1, typename T2>
void func();
• In normal functions, each parameter is replaced with a value
(of a specific type).
– void print_int(int i) { cout << i; }
• In templates, each parameter is replaced with a type, or a
constant (for non-type parameters).
– template <typename T>
void print(T o) { cout << o; }
– After instantiation, it is a function:
• void print<MyClass>(MyClass o) { cout << o; }
• In normal functions, the argument to the parameter is
specified explicitly in the argument list.
– void foo(int p1, double p2, const char *p3);
foo(123, x, “hello”);
• For template parameters, the replacement can be specified
explicitly, as in functions, or they can be deduced.
– template <typename T1, typename T2>
void f(T1, T2);
f(123, 3.14);
f<double, double>(123, 3.14);
• Inside a template, a template type parameter works just like any C++ type.
– template <typename T>
void f(T v) {
T temp;
}
• A non-type parameter works like a constant value.
– template <int N>
void f() {
int i = N;
printf(“%d\n”, N);
}
• The type parameter can be used as any other type:
– struct A { typedef int foo; struct N { … }; };
template <typename T>
void func(T v) {
typename T::foo i; // Define an int.
typename T::N n; // Define an N object.
…
}
Non-Type Parameters
• These look like ordinary parameter declarations, but
must be instantiated with a constant value.
– template <int N> …
– template <char *s> …
• Why might this be useful?
– template <typename T, int N>
void sort(T (&a)[N]) {
T save[N];
if (1 < N) {…}
}
– Will the if stay in the compiled code?
• Another example:
– template <const char *pref>
void msg(const char *m) {
cerr << pref << ": " << m << endl;
}
extern const char warning_s[] = "Warning";
void (&warn)(const char *) = msg<warning_s>;
extern const char error_s[] = "Error";
void (&error)(const char *) = msg<error_s>;
int
main() {
warn("Danger, Will Robinson!");
error("That does not compute.");
}
ALIAS TEMPLATES
• template <typename T>
using ptr = T *;
ptr<int> p; // Defines a pointer to an int.
– template <typename T>
typedef T *ptr; // Syntax error.
• template <typename T>
using my_map_t = std::map<int, vector<T>>;
my_map_t<std::string> m1;
my_map_t<const char *> m2;
FUNCTION TEMPLATES
• Function templates are “patterns” for freestanding functions.
– Allow a function to be parameterized by type.
• The syntax is:
– template <typename T1, typename T2>
void f(…) { … }
• Inside the function body, and in the parameter list, you can
use T1, etc. Example:
– template <typename T1, class T2>
T1 f(const T2 &p1, const T2 p2, T2 (*fp)(T1)) {
T1 t1;
T2 t2;
…
Can be used
return t1;
multiple times.
}
• More examples:
– template <typename T>
const T &min(const T &a, const T &b) {
return a < b ? a : b;
}
– i = min(j, k);
std::string first, s1(…), s2(…);
first = min(s1, s2);
• Another example:
– template <typename T, int size>
T min(T (&array)[size]) {
T m = array[0];
for (int i = 1; i < size; i++) {
if (array[i] < m) {
m = array[i];
}
}
return m;
}
• Will the above work for all classes? If not, how can it be improved?
– template <typename T, int size>
const T &min(T (&array)[size]) {
int min_index = 0;
for (int i = 1; i < size; i++) {
if (array[i] < array[min_index]) {
min_index = i;
}
}
return array[min_index]
}
Template Parameters
• Template parameter hides global.
– int T;
template <typename T>
void foo() { … T … } // Refers to template parameter.
• Cannot define object with same name.
– template <typename T>
void foo() {
int T; // Error.
}
• Can be used to specify the return type.
– template <typename T> T foo() { … }
• Cannot be used twice in one declaration or definition.
– template <typename T, typename T> void foo() { … }
• Can be reused across definitions.
– template <typename T> void foo() { … }
template <typename T> void func() { … }
• Can change across declarations/definitions.
– template <typename T> void foo(T t);
template <typename U> void foo(U u);
template <typename V> void foo(V v) { … }
Instantiation
• Instantiation is the process of actually filling in the template
parameters, and constructing the actual function.
• Occurs implicitly either when a function is called, or when a
function address is taken.
– template <typename T>
void foo(T) {…}
foo(1);
void (*fp)(double) = &foo;
• During instantiation, the template parameters must be bound
to actual template arguments, during a process know as
template argument deduction.
– Compile time or run time?
Template Argument Deduction
• Deduction is more complicated than a simple replacement.
(But luckily the compiler does it.)
– template <typename T>
sort(MyList <T> &a);
MyList<int> a1;
MyList<double> a2;
sort(a1); // What is T?
sort(a2); // What is T?
– template <typename T>
void func_tmpl1(T (*f)(int));
double f1(int);
func_tmpl1(&f1); // What is T?
– template <typename T>
void func_tmpl2(int (*fp)(T));
int f1(double);
int f2(char *);
double f3(double);
func_tmpl2(f1); // What is T?
func_tmpl2(f2); // What is T?
func_tmpl2(f3); // What is T?
– template <typename T1, typename T2>
void func_tmpl3(T1 (*fp)(T2));
int f1(double);
double f2(char *);
func_tmpl3(f1); // What is T1, T2?
func_tmpl3(f2); // What is T1, T2?
• Do these compile?
– template <typename T>
const T &min(const T &, const T &);
…
min(1, 3.14);
min(1, 2U);
– template <typename T>
T min2(T *, int size);
…
int a[4] = {1, 2, 3, 4};
min2(a, 4);
– template <typename T>
T min3(const T *, int size);
…
min3(a, 4);
• How about these?
– template <typename T> void func(T *p1, T *p2);
class A {…};
class B : public A {…};
A a;
B b;
func(&a, &b); // Okay?
func(&a, static_cast<A *>(&b)); // Okay?
– template <typename T> void func(Container<T> &);
template <typename T>
class FancyContainer : public Container<T> {
… };
FancyContainer<int> fc;
func(fc);
– template <typename T> void func(T *, T *);
template <typename T>
class B {};
class D : public B<int> {};
B<int> b;
D d;
func(&b, &d);
• Arrays are converted if the parameter is not a
reference:
– template <typename T1, typename T2>
void foo(T1 p1, T2 &p2) { … }
…
int a[10];
foo(a, a);
– T1 is deduced to be int *, but T2 is deduced to be
int [10].
• Most conversions are not applied for template
argument deduction. Only conversions that are used
are:
1. Lvalue to rvalue, such as array to pointer.
• template <typename T> void f(T *);
int a[] = {1, 2};
f(a);
• Unless the parameter T is a reference!
2. Qualification conversion, such as adding const.
• template <typename T> void f(const T *);
double x;
f(&x);
3. Derived pointer or reference to base class pointer or
reference, if the classes are class templates.
• template <typename T> void f(A<T> *);
template <typename T>
class B : public A<T> { … };
B<int> b;
f(&b);
• Note that even though usual conversions are not
applied to template arguments, they are applied to
non-template arguments.
– template <typename T>
void func(T v1, T v2);
func(1, 1.23); // Okay?
– template <typename T>
void func2(T v1, double v2);
func2(1, 123); // Okay?
• Remember, there are two steps:
1. Template argument deduction
2. Overload resolution.
• Template deduction happens first!
• The return type of the function template is not
deduced. (Also not used for overload resolution.)
– template <typename T> T f();
int i = f(); // Okay?
– template <typename T> T f2(T *);
double x = f2((int *) 0); // Okay?
– template <typename T> T f3(T);
double x = f3(1); // Okay?
template <typename T> T f4(T, T);
double x = f4(1, 1.3); // Okay?
• Note that the return type of a function in a
parameter is deduced, however.
•
Deduction procedure is as follows:
1. Each function parameter is examined to see if it includes
a template parameter.
2. If so, a match is attempted, normal conversions are not
used on template arguments. They are used on nontemplate arguments.
3. If a template parameter is in more than one function
parameter, then the deduced template argument must
be the same in each function parameter.
•
There are lots of complicated rules. Usually you
only need to look into them when the compiler
does the “wrong” thing:
– It thinks the situation is ambiguous, but you don’t.
– It deduces arguments differently from what you think it
should.
Explicit Arguments
• Most of the time, you want the compiler to
deduce the arguments.
– template <typename T> T min(T v1, T v2);
min(1, 2);
min(1, 3.14); // Okay?
– template <typename T> T f();
int i = f(); // Okay?
• Solution is to use explicit arguments
– min<double>(1, 3.14);
min<int>(1, 3.14);
int j = f<int>(); // Okay?
• Suppose we have a function sum(), what should we use for
the return type?
– template <typename T1, typename T2>
T1 sum(T1, T2);
short s;
sum(s, 1); sum(1, s); // Okay?
– template <typename T1, typename T2>
T2 sum(T1, T2);
short s;
sum(s, 1); sum(1, s); // Okay?
• No good options in C++98. Any choice will not work, so the
solution is to use an explicit argument.
– template <typename RT, typename T1, typename T2>
RT sum(T1, T2);
sum<int>(s, 1); sum<int>(1, s);
• If using C++11, we can use decltype.
– template <typename T1, typename T2>
auto sum(T1 v1, T2 v2) -> decltype(v1 + v2);
sum(s, 1); sum(1, s);
• Possible without trailing return type, but ugly:
– template <typename T1, typename T2>
decltype(*(T1 *) nullptr + *(T2 *) nullptr)
sum(T1 v1, T2 v2);
sum(s, 1); sum(1, s);
– template <typename T1, typename T2>
decltype(std::declval(T1) + std::declval(T2))
sum(T1 v1, T2 v2);
• Instantiation, and template argument deduction also happens when
the address of a function is taken. What happens here?
– template <typename T, int size>
const T &min(T (&arr)[size]) { … }
typedef int (&array_int)[10];
typedef double (&array_double)[20];
void func(int &(*)(array_int));
void func(double &(*)(array_double));
…
func(&min);
• To solve:
– func(static_cast<double &(*)(array_double)>(&min));
func(&min<int, 10>);
Specialization
• Consider:
– template <typename T>
T min(T a, T b) {
return (a < b) ? a : b; }
• What happens when you call?
– min(“a”, “b”)
• Sometimes, the generic definition of a template is not right. Explicit
specializations can then be used.
– template <>
const char *
min<const char *>(const char *s1,
const char *s2) {
return strcmp(s1, s2) < 0 ? s1 : s2;
}
• Does this work?
– template <typename T>
T min(T a, T b) {
return (a < b) ? a : b; }
int main() {
const char *first = min(“a”, “b”);
}
template <>
const char *
min<const char *>(const char *s1,
const char *s2) {
return strcmp(s1, s2) < 0 ? s1 : s2;
}
• At least declaration must be seen first.
– template <typename T>
T min(T a, T b) {
return (a < b) ? a : b; }
template <>
const char *
min<const char *>(const char *s1, const char *s2);
int main() {
const char *first = min(“a”, “b”);
}
template <>
const char *
min<const char *>(const char *s1, const char *s2) {
return strcmp(s1, s2) < 0 ? s1 : s2;
}
• Must be seen by all translation units.
• Where do specializations go? In header files or in .cpp files?
– They go in .cpp files, because they are actually compiled.
Overloaded Templates
• Multiple templates can exist for a single function
name.
– template <typename T>
void func(Array<T>) {…}
template <typename T>
void func(List<T>) {…}
List<int> l;
Array<double> a;
func(l);
func(a);
• There can be more than one match:
– template <typename T>
void func(T *p) { … } // V1
template <typename T>
void func(T o) { … }; // V2
char *p;
func(1); // Okay?
func(p); // Okay? Which version?
– The most specialized version is chosen. Sometimes still
ambiguous.
• What counts as more specialized?
– Accepts fewer matches. If something matches V1, will it match V2?
What about vice versa? Which version accepts fewer matches?
– Must have same number of template parameters.
Template Mixed with Nontemplate
• Is this valid?
– template <typename T>
T sum(T, int);
template <typename T>
T sum(T, double);
double sum(double, double);
• Which one gets called?
– sum(3.14, 3.14);
– sum(3.14, 1);
– sum(1, 3.14);
• What is the advantage of a non-template over a specialization?
– The advantage is that you skip the argument deduction phase, so you avoid some
ambiguity traps.
• Suppose you have a special version of min() that you want to be called
for all integer types, such as short, etc.
– // Generic definition.
template <typename T>
T min(T v1, T v2) { … }
// Specialization
template <> int min<int>(int v1, int v2) { … }
int i = ...; short s = ...;
min(i, s); // Which does this call?
• Can use non-template to enable more conversions.
– // Normal conversions will be used.
inline int min(int v1, int v2) {
return min<int>(v1, v2);
}
– min(i, s);
min(s, s);
Summary of Resolution
• For a given invocation:
– min(…);
• The steps are:
1. For each template, try to deduce arguments. If success,
add the template to the overload list.
•
Deduction failure by itself is not an error.
2. Add all non-templated functions to the overload list.
3. Use normal overload resolution. Prefer non-templated.
•
If a specialization is selected, don’t instantiate.
Specialization Revisited
• Recall: The default option should be to pass arguments
by const reference.
– template <typename T>
const T &min(const T &a, const T &b) {
return (a < b) ? a : b; }
• We also need the specialization for strings:
– template <>
const char *
min(const char *s1, const char *s2) {
return strcmp(s1, s2) < 0 ? s1 : s2;
}
– Okay?
• Need same form. Okay:
– template <typename T>
const T &min(const T &a, const T &b) {
return (a < b) ? a : b; }
– template <>
const char *const &
min(const char *const &s1,
const char *const &s2) {
return strcmp(s1, s2) < 0 ? s1 : s2;
}
– Okay now?
• Solution?
– const char *
min(const char *, const char *);
– template <typename T, size_t N1, size_t N2>
const T *
min(const T (&a1)[N1], const T (&a2)[N2]);
CLASS TEMPLATES
• Class templates are “patterns” for classes.
– Allow a class to be parameterized by type.
• The syntax is:
– template <typename T1, typename T2>
class A …;
– T1 and T2 can be used anywhere.
• Example:
Type
parameter
Int (non-type)
parameter
– template <typename T1, typename T2,
int N>
class A : public Base<T1, T2> {
public:
Type parameter used
T2 member_func(T1);
private:
for derivation
T1 data_member;
T2 data_member;
Non-type
T1 a[N];
parameter use
};
– Type parameters can be used anywhere a type
would normally be.
– A constant int parameter can replace any
constant int.
• Member functions are defined with:
– template <typename T, int N>
class A { … };
template <typename T, int N>
void A<T, N>::func() {
T obj;
int i = N;
}
• Another example:
– template <typename T, int N>
class Array {
T a[N];
T operator[](int i) {
return a[i]; }
};
• What is the syntax to define an object using this template?
– Array<int, 10> a;
• How might you improve this?
– Add range check
– Allow the index operator to be used as an lvalue by returning a
reference
– Adding a const version to be used with const arrays.
Template Parameters
• Can have multiple ones:
– template <typename T1, class T2>
class A;
– typename or class are the same. You can actually
replace class with a fundamental type.
• template <class T> class B;
B<int> a; // T is bound to int.
• Inside a template, the name of the class refers to the
parameterized name.
– template <class T>
struct Buffer {
…
Buffer *next; // Same as Buffer<T>.
};
• Is this okay?
– Buffer<int> b1;
Buffer<double> b2;
b1.next = &b2; // Okay?
• Template parameters can have default arguments. (In C++11,
also function templates.)
– template <typename T,
typename Container_T = std::vector<T> >
class Stack {
private:
Container_T elems;
…
};
• Default arguments can be redefined.
– template <class Type, int size = 1024>
class Buffer;
Buffer<int> buf; // Size is 1024.
template <class Type, int size = 2048>
class Buffer;
Buffer<double> buf2; // Size is 2048.
Instantiation
• A class template is used by giving the template name
plus the parameters.
– template <typename T1, typename T2>
class A { … };
…
A<int, double> a;
• There is no template argument deduction for class
templates.
– template <typename T>
struct A {
A(T);
…
};
A a(1234); // Error, does not create an A<int>.
• When you write:
– Stack<int> s;
• The instantiation is this:
template <typename T>
class Stack {
private:
std::vector<T> elems;
public:
void push(const T &);
void pop();
T top() const;
};
template <typename T>
void
Stack<T>::push(const T &o) {
elems.push_back(o);
}
…
class Stack<int> {
private:
std::vector<int> elems;
public:
void push(const int &);
void pop();
int top() const;
};
void
Stack<int>::push(
const int &o) {
elems.push_back(o);
}
• An instantiated class template can be used anywhere that a
non-template class can be used.
– If you can write MyClass, you can write
MyTemplatedClass<int>.
• Instantiated only when used in a context that requires
definition to exist.
• Does this compile? Is it an instantiation?
– template <typename T> class A;
void foo(A<int> &);
– Not instantiation.
• How about this?
– void foo(A<int> &a) {
a.foo();
}
– Yes, it is an instantiation.
• Different instantiations are completely independent.
• Is this an instantiation?
– int foo(Queue<int> *p) {
}
• How about this?
– int foo(Queue<int> *p) {
return p->doit();
}
• Member functions, recall, are defined with
this syntax:
– template <typename T> class A;
template <typename T>
void A<T>::foo() { … }
• Not instantiated till called or address taken.
• So, no need for definition unless called.
Example
• Example of a class template for a stack.
– template <typename T>
class Stack {
private:
std::vector<T> elems;
public:
void push(const T &);
void pop();
const T &top() const;
};
template <typename T>
void Stack<T>::push(const T &o) {
elems.push_back(o);
}
template <typename T>
void Stack<T>::pop() {
elems.pop_back();
}
template <typename T>
T &Stack<T>::top() const {
return elems.back();
}
A Template Idiom
• Is this okay?
– class A : public Tmpl<A> { … };
• Does it cause infinite recursion?
– template <typename T>
class Tmpl {
T *ptr;
};
– template <typename T>
class Tmpl {
T t;
};
– [Show crtp/]
• Occurs often enough so that it is sometimes
referred to as the curiously recurring template
pattern (CRTP).
Function Templates Interacting with
Class Templates
• Consider:
– // Function 1
template <typename T>
void foo(const T &) { ... }
// Function 2
template <>
void foo(const int &) { ... }
// Function 3
void foo(const int &) { ... }
• What is Function 2? Function 3?
• How can I call Function 1? 2? 3?
– foo(3.14);
– foo<>(1);
– foo(1);
• Consider:
– template <typename T>
class A { ... };
// Function 1
template <typename T>
void foo(const A<T> &) { ... }
// Function 2
template <>
void foo(const A<int> &) { ... }
// Function 3
void foo(const A<int> &) { ... }
• What is Function 2? Function 3?
• How can I call Function 1? 2? 3?
– A<double> a_double;
A<int> a_int;
– foo(a_double);
– foo<>(a_int);
– foo(a_int);
Friends
• A friend can be defined in a number of ways.
– class A {
template <typename T> friend void f();
friend class B<int>;
…
};
template <typename T>
class B {
friend class C<T>;
template <typename> friend class D;
…
};
• Does this work?
– template <typename T> class A;
template <typename T>
int foo(A<T> &o) {
return o.private_member; }
template <typename T>
class A {
friend int foo(A<T> &);
int private_member;
};
• No. A function template is not the same as a non-templated
function.
– template <typename T>
int foo(T &o) {
return o.private_member; }
class A {
friend int foo<>(A &);
int private_member;
};
Static Data Members
• A template class can have static data
members.
– template <typename T>
class A {
static T static_member;
};
template <typename T>
T A<T>::static_member;
Nested Types of Class Templates
• A class template can have a nested class.
– template <typename T>
class A {
class Buffer {
T *data;
};
};
• Can only be accessed with instantiation.
– A::Buffer; // Error.
– A<int>::Buffer; // Okay.
typename keyword
• Consider
– template <typename T>
void foo(const T &) {
T::name *p; }
– Is this a syntax error?
• What if T is?
– struct A1 { static int name; };
foo(A1());
– struct A2 { typedef int name; };
foo(A2());
– Can’t tell without knowing details of T.
• Use typename keyword
– template <typename T>
void foo(T) {
typename T::name *p; }
Specialization
• As with function templates, class templates
can be specialized for a particular set of
template arguments.
– template <>
class A<int, double> { … };
• Specialization of Stack class:
– template <>
class Stack<std::string> {
private:
std::deque<std::string> elems;
public:
void push(const std::string &);
void pop();
const std::string &top() const;
};
void
Stack<std::string>::push(const std::string &o) {
elems.push_back(o);
}
void Stack<std::string>::pop() {
elems.pop_back();
}
std::string &Stack<std::string>::top() const {
return elems.back();
}
• The specialization can be completely different.
– template <typename T>
class Stack {
private:
std::vector<T> elems;
public:
void push(const T &);
void pop();
T top() const;
};
// Specialization
template <>
class Stack<int> {
private:
char a[10];
public:
double foogoo();
};
• Nothing is anything carried over from the generic
implementation.
– template <typename T>
struct A {
void generic_foo(T *) { … }
…
};
template <>
struct A<int> {
…
};
…
A <int> a;
// Implemented in generic template, okay?
a.generic_foo();
• Why not?
– What if generic_foo() uses member variables? Are they present
in the specialized class template?
• You can also specialize member functions
individually:
– template <typename T>
class A {
T foo() { … } // Generic impl.
};
// Specialization.
template <>
double A<double>::foo() {…}
• Where do these go, header or program text?
– Go in .cpp file, because they are not templates.
– Must place a declaration before point of instantiation.
Partial Specialization
• In a full specialization, all template parameters
are filled in.
• In a partial specialization, some template
parameters are filled in.
– template <typename T1, typename T2>
class MyClass {…};
template <typename T>
class MyClass<T, int> {…};
• Or, the template parameters can just be more
specific.
– template <typename T1, typename T2> // 1
class MyClass {…};
template <typename T> // 2
class MyClass<T, int> {…};
template <typename T1, typename T2> // 3
class Myclass<T1*, T2*> {…};
MyClass<int, double> obj1;
MyClass<char *, int> obj2;
MyClass<int *, double *> obj3;
MyClass<int *, double> obj4;
• Further examples:
– template <typename T, int N>
class A { … };
template <typename T>
class A<T, 2> { … };
• A bit poorly named:
– Full specialization: All parameters filled in.
– Partial specialization: Some parameters filled in, at least
one left free.
• DOES NOT MEAN: Some aspects specialized, others left
as is.
– As with full specialization, nothing is carried over from the
unspecialized template.
Partial Specialization vs. Overloaded
Function Templates
• Function templates cannot be partially
specialized, but can be overloaded.
• Class templates cannot be overloaded, but can
be partially specialized.
• Usually, the distinction is not crucial.
• Usually, the distinction is not crucial:
– template <typename T1, typename T2>
void foo(T1, T2);
template <typename T1>
void foo<T1, int>(T1, int); // No.
template <typename T1>
void foo(T1, int); // Okay.
template <typename T1, typename T2>
void foo(T1 *, T2); // Okay.
– template <typename T1, typename T2>
class A { ... };
template <typename T1>
class A { ... }; // No
template <typename T1>
class A<T1, int> { ... }; // Okay.
template <typename T1>
class A<T1 *, int> { ... }; // Okay.
MEMBER TEMPLATES
Member Templates
• Suppose we had a class that represented an output
stream. We wanted it to be able to print out any
object, but with an ID in front of it.
– class Output {
public:
void print(int v) {
os << id << “: “ << v << endl;
}
void print(double v) {
os << id << “: “ << v << endl;
}
void print(const A &obj) {
os << id << “: “ << obj << endl;
}
…
};
• What if we add a new class named B?
• Is there any way we can avoid duplicating all this
code?
• We can use a member template. A member template
is a template for a single member of a class.
– class Output {
public:
template <typename T>
void print(const T &v) {
os << id << “: “ << v << endl;
}
…
};
• Member templates can also be classes:
– class Output {
template <typename T>
class Helper { … };
…
};
• Three possibilities:
– class Output {
template <typename T>
class Helper { … };
…
};
– template <typename T>
class Output {
class Helper { … };
…
};
– template <typename T>
class Output {
template <typename U>
class Helper { … };
…
};
• To define a member template outside of a class, use
this syntax:
– class Output {
public:
template <typename T> class Helper;
template <typename T>
void print(const T &v);
…
};
template <typename T>
class Output::Helper { … };
template <typename T>
void Output::print(const T &v) {
os << id << “: “ << v << endl;
}
• If the outer class is also a template, the syntax for
defining outside of the class is:
– template <typename T>
class A {
public:
template <typename U> class Helper;
template <typename U> void foo(const U &);
…
};
template <typename T>
template <typename U>
class A<T>::Helper { … };
template <typename T>
template <typename U>
void A<T>::foo(const U &u) { … }
• Operators can also be member templates:
– class A {
template <typename T>
void operator+(const T &);
};
– A a;
a + 2; // Calls template.
Special Member Templates
• Let’s say you have an array type, named Array. Since it’s a
container, you make it templated.
– template <typename T>
class Array { … };
• What is the relationship between Array<int> and
Array<short>?
– Array<int> int_array;
Array<short> short_array;
…
int_array = short_array; // Okay?
// Okay?
Array<int> int_array2(short_array);
• Let’s say that someone else is using your Array
class. She has a class A and B, and has provided
conversion and assignment operators in both
directions A  B.
– A a(…); B b(…);
A a1(b); B b1(a);
a1 = b1;
b = a;
• What is the situation between Array<A> and
Array<B>?
– Array<A> a_array; Array<B> b_array;
…
a_array = b_array; // Okay?
Array<A> a_array2(b_array); // Okay?
• Solution is templated constructors and/or assignment operators.
– template <typename T>
class Array {
public:
template <typename U>
Array(const Array<U> &a) {
... // Do allocation, etc.
for (int i = 0; i < N; i++) {
this->data[i] = a.data[i];
}
}
};
• Let’s say there is no conversion between the types C and D.
– Array<C> c_array;
…
Array<D> d_array(c_array); // Okay?
– Where in the source code above does the error occur?
• Consider:
– template <typename T>
class A {
public:
A(int);
template <typename U> A(const A<U> &o);
private:
...
};
• What constructor is used to construct a2?
– A<int> a1(2134);
A<double> a2(a1);
A<double> a3(a2);
• Template copy constructors do not inhibit generation of implicit
copy constructor.
– Even deleting them doesn’t help.
• Conversion operators can also be templates:
– class A {
public:
template <typename T>
operator T();
};
struct B {
};
struct C {
C(int);
};
...
A a;
(int) a; // Uses the conversion operator.
int i = a; // Okay?
B b(a); // Okay?
C c(a); // Okay?
• Member templates can have explicit arguments:
– class A {
public:
template <typename T>
void foo();
template <typename T>
A();
};
– A a;
a.foo<int>(); // Okay?
A a2<double>; // Okay?
• One solution:
– class A {
public:
template <typename T>
A(T *);
};
How do you invoke the constructor?
– A a((T *) 0);
Disadvantages?
– Might conflict with an actual constructor that
takes pointers.
• A better solution:
– class A {
public:
template <typename T>
A(tag<T>);
};
How do you invoke the constructor?
– A a(tag<int>());
How is tag defined?
– template <typename T>
struct tag {};
Virtual Member Templates
• Can member templates be virtual?
– class A {
public:
template <typename T>
virtual void foo();
…
};
class B : public A {
public:
template <typename T>
virtual void foo();
…
};
• No, because instantiation is problematic.
– class A {
public:
template <typename T>
virtual void foo();
…
};
class B : public A {
public:
template <typename T>
virtual void foo();
…
};
– void foo(A &a) {
a.foo<C>(); // What is a?
}
Summary
• Member function templates:
– They behave much like normal function templates.
– Template argument deduction?
– Specialization?
• Member class templates:
– They behave much like normal class templates.
– Can have specializations and partial
specializations.
ADVANCED TOPICS
• Parsing:
1: int x=2;
2: typedef int x;
– x * y; // What does this mean?
1: int X=2;
2: template <int N> struct X { X(int); };
– X<1>(0); // What does this mean?
Template Template Parameters
• Let’s say that we want to make a stack container. It may
contain different type of objects. So we make it a template.
template <typename T>
class Stack {
private:
std::vector<T> elems;
public:
void push(const T &);
void pop();
T top() const;
};
template <typename T>
void
Stack<T>::push(const T &o) {
elems.push_back(o);
}
template <typename T>
void
Stack<T>::pop() {
elems.pop_back();
}
template <typename T>
T
Stack<T>::top() const {
return elems.back();
}
template <typename T>
class Stack {
private:
std::vector<T> elems;
public:
void push(const T &);
void pop();
T top() const;
};
template <typename T>
void
Stack<T>::push(const T &o) {
elems.push_back(o);
}
template <typename T>
void
Stack<T>::pop() {
elems.pop_back();
}
template <typename T>
T
Stack<T>::top() const {
return elems.back();
}
• This version is based on a vector. Suppose sometimes we want to use a
vector, but other times we want to use a list.
– Or maybe we want to let the user plug-in her own underlying container type.
– How to handle?
– Standard approach is to use polymorphism. (A member function template
can’t be virtual, but a class template can have virtual functions.)
template <typename T>
class Stack {
private:
Container<T> *elems;
public:
void push(const T &);
void pop();
T top() const;
};
template <typename T>
void
Stack<T>::push(const T &o) {
elems->push_back(o);
}
template <typename T>
void
Stack<T>::pop() {
elems->pop_back();
}
template <typename T>
T
Stack<T>::top() {
return elems->back();
}
• User does:
– Stack<int> stack(new MyContainer<int>);
• Possible disadvantages of this method? Can I use it with
std::vector?
– Intrusive (requires modifying the container templates), possibly
not so efficient, prevents use of member templates.
• Use another template parameter.
template <typename T, typename C>
class Stack {
private:
C elems;
public:
void push(const T &);
void pop();
T top() const;
};
template <typename T, template C>
void
Stack<T, C>::push(const T &o) {
elems.push_back(o);
}
…
Stack<int, std::vector<int> > stack;
• Not that bad in this simple example, but you might want to use a
vector of ints and a vector of int * in a single class, for example.
• No way to use this to create two different
containers with different type parameters.
template <typename T, typename C>
class SomeClass {
private:
C something; // Contains ints.
C something_else; // Contains int *.
};
SomeClass<int, std::vector<int> > obj;
• Instead, can use something known as a template template parameter.
• A normal template parameter says: I don’t know what the type of this is
yet.
• A template template parameter says: I don’t know what the type of this is
yet, but it will be a (uninstantiated) template.
template <typename T, template <typename> class CONT>
class Stack {
private:
CONT<T> elems;
…
};
template <typename T, template <typename> class CONT>
void
Stack<T,CONT>::push(const T &o) {
elems.push_back(o);
}
…
Stack<int, std::vector> s;
// Not Stack<int, std::vector<int> >
• Does this compile?
template <typename T1, typename T2>
class A { … };
template <typename T, template <typename> class CT>
class B { … };
…
B<int, A> b;
• No.
– Because the class template A has two template
parameters, but the template template parameter in B has
only one template parameter.
• If you try to use this with the standard
C++ containers, it will fail.
template <typename T, template <typename> class CONT>
class Stack {
private:
CONT<T> elems;
public:
void push(const T &);
void pop();
T top() const;
};
…
Stack<int, std::vector> stack; // Syntax error!
• Why?
– Hint: How many template parameters does
std::vector have?
• Solution is to make the template template parameter’s
template parameters match the template parameters of the
C++ standard container classes.
template <typename T,
template <typename E,
typename A = std::allocator<E> > class CT>
class Stack {
private:
CT<T> elems;
public:
void push(const T &);
void pop();
T top() const;
};
…
Stack<int, std::vector> stack; // Okay now.
• Now, the number of template parameters that
std::vector has is the same as the number of template
parameters that CT has.
• Can also be used with function templates.
– template <typename T,
template <typename E,
typename A = std::allocator<E> > class C>
void foo() {
C<T> container;
}
int main() {
foo<int, std::vector>();
}
Functions as Type and Non-Type Parameters
•
A function type is also a type.
– template <typename T>
class A {
void method() {
T func; // Okay?
func(1);
}
T *fp; // Okay?
T member_func; // Okay?
};
A<void (int)> o;
•
A function pointer is a non-type template parameter, however.
– template <typename R,
class B; // Okay?
template <typename R,
class B {
F fp; // Okay?
R (*fp2)(P) = F; //
};
int func(double);
B<int, double, &func>
typename P, R (*F)(P)>
typename P, R F(P)>
Okay?
obj;
More On Non-Type Template Parameters
• The main requirement is that it be constant.
• You can do things like this:
– template <typename T, int VAL>
T addValue(const T &x) {
return x + VAL;
}
• You cannot use doubles, or string literals:
– template <double VAL>
double func(double x) { … } // Syntax error.
– template <const char *name >
class MyClass { … };
MyClass<“hello”> obj; // Error.
extern const char s[] = “hello”;
MyClass<s> x; // Okay.
– Why are string literals not allowed?
• What does this do?
– template <typename T, int (T::*mptr)>
class Incrementor {
public:
Incrementor(T *p) : obj(p) {}
void inc() { (obj->*mptr)++; }
private:
T *obj;
};
struct A {
int value1;
int value2;
} a;
Incrementor<A, &A::value1> inc1(&a);
Incrementor<A, &A::value2> inc2(&a);
inc1.inc();
inc2.inc();
inc2.inc();
Zero Initialization
• One of the issues with templates is the distinction
between “fundamental” values, like int, double, etc.
and “objects”.
– The same code should work for both.
– In Java, one way around this the Integer class.
• In C++, this mainly shows up in initialization issues.
– template <typename T>
void foo() {
T x; // Is this initialized?
}
– Depends on whether it is a fundamental type or not.
• Solved by defining int() to be zero.
– template <typename T>
void foo() {
T x = T();
}
template <typename T>
class A {
public:
A();
private:
T x;
…
};
template <typename T>
A<T>::A() : x() {…}
.template
• In some situations, there is a similar type of
ambiguity to the typename issue.
• Is this a syntax error?
– template <int N>
void print(const bitgroup<N> &bs) {
std::cout << bs.to_string<char>();
}
• Disambiguate with template keyword.
– template <int N>
void print(const bitgroup<N> &bs) {
std::cout << bs.template to_string<char>();
}
String Literals in Template Argument Deduction
• Consider:
– template <typename T>
const T &max(const T &a, const T &b) { … }
…
max(“a”, “b”); // Okay.
max(“aa”, “bb”); // Okay.
max(“a”, “bb”); // Is this okay?
• The issue is that the type of a string literal like “a” is const
char[2]. If you use a non-reference parameter, on the other
hand, the array-to-pointer decay will occur.
– template <typename T>
T max(T a, T b) { … }
…
max(“a”, “b”); // Okay.
max(“a”, “bb”); // Okay.
• You can kind of solve this with an overloaded template, but it
doesn’t help much anyway, due to the return type.
– template <typename T, size_t N1, size_t N2>
??? max(const T (&a1)[N1], const T (&a2)[N2]) { ... }
Argument Dependent Lookup (Koenig)
• Remember that operators for objects are just
a kind of “syntactic sugar” for functions:
– if (a < b) {…}
This is a function
call!
• is exactly the same as
– if (operator<(a,b)) { … }
• Consider this:
– // Library A code.
class BigInt {…}; // Assume operator = defined.
bool operator<(const BigInt &, const BigInt &);
// Library B code.
template <typename T>
inline const T &max(const T &a, const T &b) {
return a < b ? a : b;
}
// User code.
void foo(const BigInt &bi1, const BigInt &bi2)
{
BigInt x = max(b1, b2); // Okay?
}
• Should there be namespaces somewhere here?
• So being good C++ citizens, we add namespaces:
– // Library A code.
namespace cs540 {
class BigInt {…}; // Assume operator = defined.
bool operator<(const BigInt &, const BigInt &);
}
// Library B code.
namespace std {
template <typename T>
inline const T &max(const T &a, const T &b) {
return a < b ? a : b;
}
}
// User code.
void foo(const cs540::BigInt &bi1,
const cs540::BigInt &bi2) {
cs540::BigInt x = std::max(b1, b2); // Okay?
}
• Does this still work?
• The < operator is in a different namespace
from the template.
• But ADL says that names should be looked up
in scopes associated with the arguments.
– Dependent qualified names are looked up.
– ADL is done for unqualified names.
• Using directives are ignored during ADL, but
using declarations are obeyed.
• Consider this:
– namespace cs540 {
class A { … };
void foo(const A &a);
}
std::ostream &
operator<<(std::ostream &os, const A &);
int main() {
cs540::A a;
cs540::foo(a); // Okay?
foo(a); // Also, okay?
operator<<(std::cout, a); // Okay?
}
std::cout << a << endl; // Okay?
• Consider this:
– namespace cs540 {
class A { … };
void foo(const A &a) { … }
}
// Which one does it call?
void foo(const cs540::A &a) { … }
int main() {
cs540::A a;
cs540::foo(a); // Okay?
foo(a); // Okay?
}
• Consider this:
– namespace ns {
class X {
...
};
template <int I> void select(X*);
}
void g(ns::X *xp) {
select<3>(xp); // Does ADL work here?
}
• There are two ways to parse the above:
–
Function name
Arg
select<3>(xp)
–
Comparison
Comparison
select<3>(xp)
• The question is whether or not xp is a function call argument.
– If yes, then ADL will apply.
– If not, then ADL does not apply.
– But whether or not it is a function call argument depends on whether or not
<3> is a template argument....but this depends on whether or not xp is a
function call argument...but this depends on whether or not <3> is a template
argument....
Friend Name Injection
• Consider this:
– template <typename T>
class A {
friend void f();
friend void f(const A<T> &);
};
void g(A<int> *p) {
f(); // Okay?
f(*p); // Okay?
}
• Upshot is that friend functions are found if they are
friends of classes that are part of the ADL.
Class Name Injection
• Inside a template, the class name can be used
alone:
– template <typename T>
class C {
C foo();
C<double> goo();
};
– In this case, it is considered to be shorthand for C<T>,
which is not a template. This means that o.foo()
returns an object of type C<int> if o is of type
C<int>, etc.
• template <template <typename> class TT>
class X { };
template <typename T>
class C {
C *a;
C<void> b;
X<C> c;
X<::C> d;
};
Dependent and Nondependent Names
• Within a template, there are two types of names.
– dependent: The exact meaning depends on a template parameter.
– nondependent: The exact meaning does not depend on a template
parameter.
• Which are dependent/nondependent?
– template <typename Type>
Type min(Type *array, int size) {
Type min_val = array[0];
for (int i = 1; i < size; i++) {
if (array[i] < min_val) {
min_val = array[i];
}
}
print("Min found: ");
print(min_val);
return min_val;
}
• Consider two translation units containing the
below:
– First translation unit:
template <typename T>
void foo(T v) {
func(v); // func() is not declared yet.
// print() is not declared yet.
print(“hello”);
}
– Second translation unit:
void func(int);
void print(const char *);
foo(1);
• Does this compile?
Name Resolution
• Name lookup occurs in two phases.
– In the first phase, nondependent names are
resolved where they are used.
• Thus, all names not dependent on a template must be
declared at point of template definition.
– In the second phase, dependent names are
resolved at the point of instantiation.
• Thus, all names dependent on a template not resolved
till point of instantiation.
Point of Instantiation (POI)
• The point of instantiation (POI) of a function template is
always in namespace scope, and occurs immediately after the
function that instantiated it.
– int main() {
…
min(…); // Use of a function template min().
}
// <<<< POI of the use above is here.
• What if the same function is instantiated multiple times?
– Compiler can pick any POI.
• What if in more than one file?
– Compiler can pick any one.
• Why is the POI after the use of a function template,
rather than before?
• Consider:
– template <typename T>
void f(T o) {
if (o > 0) {
g(o); // ?
}
}
…
// Possible POI 1
void g(FooType ft) {
f<FooType>(ft);
}
// Possible POI 2
• Where should the POI of a class template be?
– template <typename T>
class S {
public:
T m;
};
// Possible POI 1
unsigned long h() {
return (unsigned long) sizeof(S<int>);
}
// Possible POI 2
• The point of instantiation (POI) of a class template is always in
namespace scope, and immediately precedes the declaration
or definition that uses the instantiation.
• The POI of a member function or static data member
immediately follows it's use.
Template Aliases
• A typedef can only be made to a concrete type.
• Recall our template template parameter example:
– template <typename T>
class MySimpleContainer { … };
template <typename T,
template <typename> class C>
class A {
C<T> container;
};
int main() {
A<int, MySimpleContainer> a1;
A<int, std::vector> a;
}
– What’s the problem?
• You can solve this by creating a template alias:
– template <typename T>
class MySimpleContainer { … };
template <typename T,
template <typename> class C>
class A {
C<T> container;
};
template <typename T>
using myvector = std::vector<T, std::allocator<T> >;
int main() {
A<int, MySimpleContainer> a1;
A<int, myvector> a;
}
• std::map takes two template arguments,
the key and value.
– map<string, A *>
• Let’s say that you were tired of typing the first
template argument. You can use a template
alias:
– template <typename T>
using mymap = map<string, T>;
– mymap<int> m;
Repetitive Code
•
Suppose you are writing some code, and you see that the following lines repeated
4 times in your code within a single function:
– Local variables are in blue, code that is not the same in all four occurrences is in red.
– …
Element *e = new Element(bindings_table.lookup(String()),
String(st_name_bc_begin, p));
if (root != 0) {
element_stack.top().element->add_child(e);
} else {
root = e;
}
element_stack.push(e, String(st_name_bc_begin, p),
binding_list_head);
…
– …
Element *e = new Element(bindings_table.lookup(elem_prefix),
String(st_name_ac_begin, p));
if (root != 0) {
element_stack.top().element->add_child(e);
} else {
root = e;
}
element_stack.push(e, String(st_name_bc_begin, p),
binding_list_head);
…
Element *e = new Element(bindings_table.lookup(elem_prefix),
name);
if (root != 0) {
element_stack.top().element->add_child(e);
} else {
root = e;
}
element_stack.push(e, check_name, binding_list_head);
…
– …
Element *e = new Element(bindings_table.lookup(elem_prefix),
name);
if (root != 0) {
element_stack.top().element->add_child(e);
} else {
root = e;
}
element_stack.push(e, check_name, binding_list_head);
…
•
Pattern is:
– …
Element *e = new Element(bindings_table.lookup(str1), str2);
if (root != 0) {
element_stack.top().element->add_child(e);
} else {
root = e;
}
element_stack.push(e, str3, binding_list_head);
…
•
•
So what?
Solution?
• You could use a function:
– void create_element(
BindingTable *bt,
Element **root,
ElementStack *es,
const BindingTable::Binding *blh,
const String &pref,
const String &nm,
const String &cn) {
Element *e = new Element(bt->lookup(pref),
nm);
if (*root != 0) {
es->top().element->add_child(e);
} else {
*root = e;
}
es->push(e, cn, blh);
}
• Which would then be called with:
– create_element(&bindings_table, &root,
&element_stack, binding_list_head,
String(),
String(st_name_bc_begin, p),
String(st_name_bc_begin, p));
create_element(&bindings_table, &root,
&element_stack, binding_list_head,
elem_prefix,
String(st_name_ac_begin, p),
String(st_name_bc_begin, p));
create_element(&bindings_table, &root,
&element_stack, binding_list_head,
elem_prefix,
name,
check_name);
create_element(&bindings_table, &root,
&element_stack, binding_list_head,
elem_prefix,
name,
check_name);
• Other options?
• You could use a local class to encapsulate a function.
– struct Locals {
void create_element(const String &pref,
const String &nm, const String &cn) {
Element *e = new Element(
bindings_table->lookup(pref), nm);
if (root != 0) {
element_stack.top().element->add_child(e);
} else {
root = e;
}
element_stack.push(e, cn, binding_list_head);
}
BindingTable bindings_table;
ElementStack element_stack;
const BindingTable::Binding *binding_list_head;
Element *root;
} l;
• It would be used like this:
– l.create_element(String(),
String(st_name_bc_begin, p),
String(st_name_bc_begin, p));
l.create_element(elem_prefix,
String(st_name_ac_begin, p),
String(st_name_bc_begin, p));
l.create_element(elem_prefix,
name,
check_name);
l.create_element(elem_prefix,
name,
check_name);
… l.bindings_table.accessor() …;
• Note that you are using the local class to
create a local function that “captures” some
local variables.
• You can do that explicitly using lambda in
C++11.
Lambda
• Lambda allows you to create anonymous functions.
• Example:
– cout << [](int x){return x + 3;}(4) << endl;
– auto doit = [] (int x) { return x + 2; }
cout << doit(1) << endl;
• In the body, you can only use captured variables:
– int i, j;
auto doit = [i] () {
cout << i << endl; // Okay.
cout << j << endl; // Syntax error.
}
• You can capture by reference, also:
– int i = 1, j = 2;
auto doit = [&i, j]() {
i = 3; // Okay.
}
• You can capture implicitly (default):
– int i = 1, j = 2;
auto doit = [&, i]() {
j = 1; // Implicit capture by reference.
i = 3; // Error, captured by value.
}
– int i = 1, j = 2;
auto doit = [=, &j]() {
i = 2; // Error, implicit capture by value.
j = 3; // Okay.
}
• You change variables captured by value by creating mutable lambdas, but
it won’t change the outer:
– int i = 1, j = 2;
auto doit = [&, i]() mutable {
j = 1; // Implicit capture by reference.
i = 3; // Okay, doesn’t change outer.
}
• The return type can be inferred if just one return statement or void.
– auto l1 = [] () { return 1234; };
– auto l2 = [](int n) {
for (int i = 0; i < n; i++) {
cout << i << endl;
}
};
• Otherwise, must use a trailing return type.
– auto l3 = [](int n) mutable -> int {
if (n%2 == 0) {
return 1;
} else {
return ‘a’;
}
};
• In C++14, return type deduction works even if not just a single
return statement, and also works for non-lambda.
• A common task is to apply a small bit of code to all the
elements in some container.
– #include <iostream>
#include <array>
#include <algorithm>
using namespace std;
void f(int i) {
cout << i << endl;
}
int main() {
array<int, 5> a{{1, 2, 3, 4, 5}};
for_each(a.begin(), a.end(), f);
}
• What if we want to collect all odd
elements?
– #include
#include
#include
#include
– int main() {
<iostream>
<array>
<algorithm>
<vector>
array<int, 5> a{{1, 2,
3, 4, 5}};
vector<int> result;
CollectOdd f(&result);
using namespace std;
class CollectOdd {
public:
Odd(vector<int> *v)
: vec(v) {}
void operator()(int i) {
if (i%2 == 1) {
vec->push_back(i);
}
}
private:
vector<int> *vec;
};
for_each(a.begin(),
a.end(),
f);
for (auto i : result) {
cout << i << endl;
}
}
• Can be done with lambda.
– #include <iostream>
#include <array>
#include <algorithm>
using namespace std;
int main() {
array<int, 5> a{{1, 2, 3, 4, 5}};
vector<int> result;
for_each(a.begin(), a.end(),
[&](int i) {
if (i%2 == 1) {
result.push_back(i);
}
}
);
}
• Lambdas can be put into variables:
– auto f = [](int i) { return 2*i; };
auto j = f(2);
• To pass a lambda into a non-template function, use
std::function:
– void f(const std::function<int (int)> &f) {
int i = f(2);
…
}
f([](int i) { return 2*i; });
• In C++14, you can have generic lambdas (more or less like a
templated lambda). Handy in two ways:
– // C++11
auto sqr1 = [](int x) {return x*x; };
double x = sqr1(3.14);
// C++14
auto sqr2 = [](auto x) { return x*x; };
int i = sqr(9); // Does the right thing.
double x2 = sqr(3.14); // Does the right thing.
– // Also allows compiler to figure out
// types for you.
std::sort(cont.begin(), cont.end(),
[](auto i, auto j) {
return (i > j);
});
• Also, in C++14, you can have generalized capture:
– int i;
auto l = [&v1 = i, v2 = 2*i, v3 = 1]() mutable {
v1 = 3; // Sets i.
cout << v3++ << endl;
};
l();
l();
Variadic Templates
• In C++11, templates can have varying number of template and function
arguments.
– template <typename... Ts>
void f(Ts... params) { … }
• Example, a variadic function template to sum its args:
– template <typename T>
const T &sum(const T &v) { return v; }
template <typename T, typename... Ts>
T sum(const T &v, const Ts & ... params) {
return v + sum(params...);
}
…
sum(1);
sum(1, 2);
sum(1.1, 2.2, 3.3);
BigInt bi1, bi2, bi3;
sum(bi1, bi2, bi3, 3);
• You can get the number of parameters in the
pack with sizeof...:
– template <typename… Ts>
void foo(const Ts & … params) {
cout << sizeof…(Ts) << endl;
cout << sizeof…(params) << endl;
}
• Class templates can also be variadic:
– template <typename... Ts>
class A { … };
• Non-type parameters can also be variadic:
– template <size_t... Ns>
class A { … };
• Expansion can be a pattern:
– template <typename T>
void out(const T &v) {
cout << v << endl;
}
template <typename... Ts>
void pass(const Ts &... params) {}
template <typename... Ts>
void foo(const Ts & ... params) {
pass(out(params)...);
}
– foo(1, 1.3);
expands to
pass(out(1), out(1.3));

similar documents