From C to C++
SNU iDB Lab.
Hyoung-woo Park
March 21, 2007
Contents






History
Central Concepts
Object Orientation in C++
Standard Template Library
Summary
Reference
2
History
 C++ was designed by Bjarne Stroustrup at Bell Labs.
 Stroustrup wanted to combine the elegance, flexibility, and
type safety of Simula with the performance of BCPL
 Due to the extensibility and flexibility of C, he introduced the
concept of classes into it and named it as 'C with classes'
 According to the growth of the language , Rick Mascitti
suggested the subtle name "C++"
 Original C++ compiler produced C as its object code
 The power of C could be increased while yielding a C program as its
result
3
Contents






History
Central Concepts
Object Orientation in C++
Standard Template Library
Summary
Reference
4
Central Concepts
 The goal of C++ is to permit programmers to
express their ideas directly, conveniently, and safely
without sacrificing execution speed
 C++ programmer can define abstract data types and
manipulate objects of those types
 A carefully restricted dynamic binding facility
supports object-oriented programming
5
Contents






History
Central Concepts
Object Orientation in C++
Standard Template Library
Summary
Reference
6
Data Abstraction(1/8)
 Class
 A data structure together with a set of operations defined
on objects with that structure
 Contains member variables and member functions (methods)
 Comprises public / protected / private members
 Public members are accessible to outside of the class
 Protected members are only accessible to derived classes
 Private members are not accessible to outside of the class
7
Data Abstraction(2/8)
class Complex {
public:
double re() {
return r;
}
double im() {
return i;
}
private:
double r, i;
};
…
Complex z;
double x, y;
x = z.r;
y = z.re();
Evaluation fails to compile
Evaluation compiles
An example of a class and its usage
8
Data Abstraction(3/8)
 The this pointer
 Contains the address of the instance for which the
method was called
 Most often, the this pointer is used to disambiguate the
reference
9
Data Abstraction(4/8)
class Complex {
public:
void set(double r, double i) {
this–>r = r;
Equivalent to (*this).r = r
this–>i = i;
Equivalent to (*this).i = i
}
double re() {
return r;
}
double im() {
return i;
}
private:
double r, i;
};
An example of using this pointer
10
Data Abstraction(5/8)
 Constructors and destructors
 Constructor / destructor is a member function which
creates / destroys an object of the class
 Constructor has the same name as the class
 Constructor has no return value specification
 Destructor has the same name as the class but prefixed by
tilde (~)
 Destructor has neither arguments nor a return value
11
Data Abstraction(6/8)
class Complex {
public:
Complex(double x = 0, double y = 0) {
r = x;
i = y;
}
~Complex() {
Destroys an object
r = i = 0;
}
private:
double r, i;
};
Creates
an object
An example of constructor and destructor
12
Data Abstraction(7/8)
 Friend functions and classes
 Explicitly make private members of one class accessible to
other functions or classes
 Violate the information-hiding principle of objectorientation
13
Data Abstraction(8/8)
Allows 'conjugate'
to access r, i
class Complex {
public:
friend void conjugate(Complex &c);
friend class Pal;
…
Allows Pal class
private:
to access r, i
double r, i;
};
void conjugate(Complex &c) {
c.i = –c.i;
}
class Pal {
void negate(Complex &c) {
c.r = –c.r;
c.i = –c.i;
}
};
An example of using friend keyword
14
Inheritance(1/7)
 Inheritance
 Based on common knowledge representation paradigms
of artificial intelligence
e.g. Ross Quillian's (1968) semantic network knowledge
representation models
 Generalization / specialization relationship among
concepts
 Through inheritance designers can build new software
modules on top of an existing modules
15
Inheritance(2/7)
Person
Employee
SalesPerson
Multimedia
Student
Secretary
Audio
Video
Graphic
Images
Raster
Examples of inheritance hierarchies
16
class Vehicle {
public:
int weight;
char* name;
…
};
class Vehicle {
public:
int weight;
char* name;
…
};
class Car {
public:
int weight;
char* name;
char* manufacturer;
…
};
class Car : public Vehicle {
public:
inherits
Inheritance(3/7)
char* manufacturer;
…
};
An example of using inheritance
17
Inheritance(4/7)
 Inheritance and constructors / destructors
 Constructors / destructors of derived class object must
call constructors / destructors of the base class
 The constructor of a base class is called before the
constructor of a derived class is invoked
 The destructor of a base class is called after the
destructor of a derived class is invoked
18
Inheritance(5/7)
class Vehicle {
public:
Vehicle(int w, char* n) {
weight = w;
strcpy(name, n);
}
…
};
calls
class Car :Vehicle {
public:
Car(int w, char* n, char* m) :Vehicle(w, n) {
strcpy(manufacturer, m);
}
…
};
An example illustrating the constructor of a derived class
19
Inheritance(6/7)
 Multiple inheritance
 Allows a subclass to inherit from more than one
immediate superclass
 Supports combination of existing classes into new classes
 Makes the class inheritance hierarchy become DAG
 Ambiguity arises when inheriting multiple members with
the same name
20
Inheritance(7/7)
class Student {
protected:
int id;
};
class Staff {
protected:
int id;
};
class WorkStudy : public Student, public Staff {
public:
int getId(){
return id;
Error: Ambiguous!!
return Staff::id;
}
};
An example of multiple inheritance and ambiguity resolution
21
Dynamic Binding(1/2)
 Virtual functions
 Enable dynamic binding in C++
 Select which method to invoke dynamically (at run time)
 Two basic rules of dynamic binding
 A pointer (reference) to a class T may contain the address
of an object of class T or any of its subclasses
e.g.Vehicle* vp = &car;
vp is a pointer to Vehicle, but it contains the
address of an object of class Car
 When a pointer is used to call a virtual function, the class
of the object (not the pointer) determines which function to
call
22
Dynamic Binding(2/2)
class Vehicle {
public:
virtual float weight( );
};
class Car : public Vehicle {
public:
float weight( );
};
void main(void) {
Car c;
Vehicle* vp = &c;
float x = vp–>weight( );
}
Because vp points to an instance of Car,
Car::weight( ) is called by the second rule
of dynamic binding
An example of dynamic binding
23
Overloading(1/4)
 Function overloading
 In C++ it is possible to define several functions with the
same name, performing different actions
 C++ uses the following information (signature) to
distinguish among different functions
 Parameter types
 Number of parameters
24
Overloading(2/4)
void show(int val) {
cout << "Integer: " << val << endl;
}
void show(double val) {
cout << "Double: " << val << endl;
}
void show(char* val) {
cout << "String: " << val << endl;
}
An example of function overloading
25
Overloading(3/4)
 Operator overloading
 Allows redefinition of the C operators for any userdefined class
 Can be declared and used like any other functions
 Operators can be defined by either member functions or
nonmember functions
Overloadable operators
26
Overloading(4/4)
class Complex {
public:
Complex operator+(Complex c) {
Complex ret(r + c.r, i + c.i);
return ret;
}
…
};
void operator+=(Complex c1, complex c2) {
c1.r += c2.r;
c1.i += c2.i;
}
void main(void) {
Complex c1, c2;
Equivalent to c1 = c1.operator+(c2)
c1 = c1 + c2;
c1 += c2;
Equivalent to ::operator+=(c1, c2)
}
An example of operator overloading
27
Templates(1/3)
 Templates use accept types as parameters in generic
type declarations or classes
 Some people view template as a syntactic sugar
supporting generic programming rather than
polymorphism because
 Type parameters are statically (at compile time) resolved
 With macros, we can do our job without using templates
28
Templates(2/3)
 However, templates are widely used in objectoriented programming languages because
 Templates provide clustering of representation (structure)
and behavior (operations)
 Considering about code duplication, templates are better
than macros
 There are cases where it is difficult or impossible to use
macros
e.g. Recursive types
29
Templates(3/3)
template<class T, int size> class List {
T* list;
public:
List( ) {
list = new T[size];
}
…
};
template<class T> T max(T a, T b) {
return (a > b) ? a : b;
}
void main(void) {
List<int, 100> a;
int s = max(3, 4);
}
list = new int[100]
Calls max(int, int)
An example of template class and function
30
Contents






History
Central Concepts
Object Orientation in C++
Standard Template Library
Summary
Reference
31
What is STL?
 STL is a software library which is developed in early 90's at
HP Lab. and included in the C++ Standard Library in 1994
 STL is based on generic programming
 STL provides a ready-made set of common classes and
algorithms such as






Containers
Generic algorithms
Iterators
Functors
Adaptors
Container classes
Allocators
Iterators
Algorithms
32
Principles of STL(1/3)

STL was designed to make programmers make
their programs following these principles
1. Development of algorithms and data structures in a way
that allows the highest level of code reusability
List of integers
List of strings
…
<Using classes alone>
Template class
which needs a type T as a
parameter and creates a list of
type T
<Using template>
33
Principles of STL(2/3)

STL was designed to make programmers make
their programs following these principles
2. Provided that we have a good optimizing compiler, all the
generic algorithms in STL are almost as efficient as handcoded ones
Pair tmp = my_vector.get(i);
tmp.second = 5;
i->second = 5;
my_vector.put(i, tmp);
<Using class members – Slow>
<Using class-pointer operator – Fast>
34
Principles of STL(3/3)

STL was designed to make programmers make
their programs following these principles
3. Separate algorithms from data structures in order to
reduce the size of source code and avoid repetition of
work
Function which {
a list of {
adds
multiplies
int egers
floating numbers
} elements of
}
Template function which
needs a function F
and a type T as a parameter
and applies F to a list of type
T
2 * 2 = 4 functions are needed
<Functions incorporating two
algorithms and two types>
<A template function which
uses a function and a type>
35
STL At a Glance
Five major categories of STL components
36
STL Container Classes
STL Containers
Sequential Container Class
Associative Container Class
Basic Class
Adaptor Class
Map Class
Set Class
Vector Class
List Class
Dequeue Class
Stack Class
Queue Class
Priority Queue Class
Map Class
Multimap Class
Set Class
Multiset Class
Classification of STL container classes
37
Containers(1/2)
Class 1
Class 2
Container
(Template)
Conceptual representation of containers
38
Containers(2/2)
 Two categories of STL containers are
 Sequence containers
 Include vector, list, dequeue
 Organize a collection of objects into a strictly linear arrangement
 Arrays and strings can be used as a sequence container
 Sorted associative containers
 Include set, multiset, map, multimap
 Provide fast retrieval of objects based on keys
39
Sequence Containers(1/3)
 Vector
 Provides random access to a sequence of varying length
 Supports constant-time insertions and deletions at the end
 List
 Provides only linear time access to a sequence of varying length
 Supports constant-time insertions and deletions at any given position
 Dequeue
 Provides random access to a sequence of varying length
 Supports constant-time insertions and deletions at both the beginning
and the end
40
Sequence Containers(2/3)
begin( )
h
end( )
e
l
l
o
begin( )
end( )
h
e
l
l
o
begin( )
h
end( )
e
l
l
o
Vector, List and Dequeue
41
Sequence Containers(3/3)
…
int main(void) {
string s = "hello";
reverse(s.begin(), s.end());
cout << s << endl;
olleh
char ca[ ] = "STL";
reverse(&ca[0], &ca[strlen(ca)]);
cout << string(ca) << endl;
LTS
vector<int> v;
v.push_back(3);
v.push_back(4);
reverse(v.begin(), v.end());
cout << v.at(0) << "," << v.at(1) << endl;
return 0;
}
4,3
An example of using sequence containers
42
Sorted Associative Containers(1/4)
 Set
 Supports unique keys
 Provides for fast retrieval of the keys
 Multiset
 Supports duplicate keys
 Provides for fast retrieval of the keys
 Map
 Supports unique keys
 Provides for fast retrieval of values based on the keys
 Multimap
 Supports duplicate keys
 Provides for fast retrieval of values based on the keys
43
Sorted Associative Containers(2/4)
Set
Multiset
Map
Multimap
44
Sorted Associative Containers(3/4)
…
int main(void) {
set<int> s1;
s1.insert(3);
s1.insert(4);
multiset<int> s2;
s2.insert(3);
s2.insert(3);
s2.insert(4);
s2.insert(4);
return 0;
}
s1 is (3, 4)
s2 is (3, 3, 4, 4)
An example of using set and multiset
45
Sorted Associative Containers(4/4)
…
int main(void) {
map<string, int> m1;
m1["DB"] = 2006;
m1 is ("DB"2006, "OO"2007)
m1["OO"] = 2007;
cout << "OO:" << m1["OO"] << endl;
OO:2007
multimap<string, int> m2;
m2 is
m2.insert(pair<string, int>("DB", 2005));
("DB"2005,
m2.insert(pair<string, int>("DB", 2006));
"DB"2006)
cout << "DB:"
<< m2.find("DB")–>second << endl;
DB:2005
return 0;
}
An example of using map and multimap
46
Generic Algorithms(1/2)
Function 1
(multiplies
apples)
Function 2
(multiplies
light bulbs)
Generic Algorithm
(multiplies
given objects)
Conceptual representation of generic algorithm
47
Generic Algorithms(2/2)
 There are similar operations on the different data
objects of different classes
 STL provides the generic algorithms for containers
 STL generic algorithms fall into four categories




Nonmutating sequence algorithms
Mutating sequence algorithms
Sorting-related algorithms
Generalized numeric algorithms
48
Nonmutating Sequence Algorithms(1/3)
 find(first, last, value)
 Iterator first marks the position in a sequence where it
should start processing
 Iterator last marks the position where it can stop
processing
 Returns an iterator addressing the first location of an
element in the sequence whose value is value
49
Nonmutating Sequence Algorithms(2/3)
 count(first, last, value)
 Iterator first marks the position in a sequence where it
should start processing
 Iterator last marks the position where it can stop
processing
 Returns the number of elements in the sequence whose
value is value
50
Nonmutating Sequence Algorithms(3/3)
first
3
last
3
4
4
5
find(first, last, 4)
first
3
last
3
4
4
5
count(first, last, 4) = 2
An example of using find and count algorithm
51
Mutating Sequence Algorithms(1/3)
 copy(first1, last1, first2)
 Iterator first1 marks the position in a sequence where it
should start processing
 Iterator last1 marks the position where it can stop
processing
 first2 marks the beginning of copied sequence
52
Mutating Sequence Algorithms(2/3)
 unique(first, last)
 Iterator first marks the position in a sequence where it
should start processing
 Iterator last marks the position where it can stop
processing
 Eliminates all consecutive duplicate elements from the input
sequence
 Does not change the size of the sequence
53
Mutating Sequence Algorithms(3/3)
first1
3
last1
3
4
4
5
copy(first1, last1, first2)
3
3
4
first2
first
3
last
3
4
3
3
unique(first, last)
3
4
3
3
3
An example of using copy and unique algorithm
54
Sorting-related Algorithms(1/3)
 sort(first, last)
 Iterator first marks the position in a sequence where it
should start processing
 Iterator last marks the position where it can stop
processing
 Sorts the sequence in nondecreasing order
55
Sorting-related Algorithms(2/3)
 merge(first1, last1, first2, last2, result)
 first1 and last1 are iterators marking the beginning and
end of one input sequence whose elements are of some
type T
 first2 and last2 are iterators delimiting another input
sequence whose elements are also of type T
 The two input sequences are in ascending order according
to the < operator for type T
 result marks the beginning of the sequence where the
result should be stored
56
Sorting-related Algorithms(3/3)
first
7
last
5
6
3
4
sort(first, last)
3
4
first1
3
5
7
first2
last1
4
6
6
5
last2
7
merge(first1, last1, first2, last2, result)
3
4
5
6
7
result
An example of using sort and merge algorithm
57
Generalized Numeric Algorithms(1/2)
 accumulate(first, last, val)
 Iterator first marks the position in a sequence where it
should start processing
 Iterator last marks the position where it can stop
processing
 Adds val to the values in a given range of sequence
58
Generalized Numeric Algorithms(2/2)
first
3
last
3
4
4
5
accumulate(first, last, 0) = 19
An example of using accumulate algorithm
59
Iterator(1/3)
Iterator
Data
Structure
Using
Iterator
Conceptual representation of iterators
60
Iterators(2/3)
 STL generic algorithms are written in terms of
iterator parameters
 STL containers provide iterators that can be plugged
into the algorithms
 Generally iterators behave like pointers
61
Iterators(3/3)
#include <numeric> // for accumulate
using namespace std;
int main(void) {
int x[5] = {2, 3, 5, 7, 11};
int sum = accumulate(&x[0], &x[5], 0);
return 0;
}
template<typename I, typename T>
int
T accumulate(I
accumulate(int*
first,first,
I last,int*
T init)
last,{int init) {
while(first != last) {
init = init + *first;
++first;
}
return init;
28
}
(&x[0], &x[5], 0)
An example illustrating how iterators work
62
Functors(1/3)
Functor
Generic
Algorithm
Conceptual representation of functors
63
Functors(2/3)
 Many STL generic algorithms have more general
version of algorithms accepting functor (function
object) as additional parameter
 Functors extend the functionality of STL generic
algorithms
64
Functors(3/3)
…
int f(int x, int y) { return (x < y ? x : y); }
int main(void) {
int a[3] = {2, 3, 5};
int *p = &a[0];
int *q = &a[3];
int r1, r2, r3;
0 + 2 + 3 + 5 = 10
r1 = accumulate(p, q, 0);
r2 = accumulate(p, q, 1, multiplies<int>( ));
1 * 2 * 3 * 5 = 30
r3 = accumulate(p, q, 100, f);
f(f(f(100, 2), 3), 5) = 2
}
An example illustrating how functors work
65
Adaptors(1/3)
Iterator
Adaptor
Conceptual representation of adaptors
66
Adaptors(2/3)
 Components that modify the interface of other
components are called adaptors
 Adaptors modify iterators, containers and functions
 reverse_iterator makes iterator's direction of traversal
reversed
 stack / queue restricts a sequence container's behavior
to make it accessible only by LIFO / FIFO manner
 unary_negate and binary_negate reverse the sense of
predicate function objects which return a boolean value
67
Adaptors(3/3)
…
int main(void) {
int a[3] = {3, 4, 5};
reverse_iterator<int*> x(&a[3]), y(&a[0]);
int r = accumulate(++x, y, 0);
4+3=7
stack<int, deque<int> > s;
Create a stack using a dequeue
s.push(3);
and push 3
queue<float, list<int> > q;
Create a queue using a list
q.push(4);
and push 4
}
An example illustrating how adaptors work
68
Allocators
 Every STL container class uses an allocator class to
encapsulate information about the memory
allocation model the program is using
 The allocator class encapsulates information about





Pointers
Constant pointers
References
Constant references
Size of objects
69
Contents






History
Central Concepts
Object Orientation in C++
Standard Template Library
Summary
Reference
70
Summary
 C++ supports object-orientation features
 Data abstraction
 Inheritance
 Dynamic binding
 STL is part of C++ Standard Library and supports generic
programming by providing containers, iterators, generic
algorithms, etc.
 Problems of C++
 Since C++ is based on and largely compatible with C, it inherits the
drawbacks of C
 When different versions of STL are used in the same program,
compilation may end to fail or the executable file may become huge
(code bloat problem)
71
Contents






History
Central Concepts
Object Orientation in C++
Standard Template Library
Summary
Reference
72
Reference
 Setrag K., Razmik A. (1995). Object Orientation, John
Wiley & Sons, Inc., 267-319.
 Andrew K. (1988). What is C++, Anyway?, Journal of
Object-Oriented Programming, 1(1), 48-52.
 David M., Gillmer D., Atul S. (2001). STL Tutorial and
Reference Guide, 2nd Ed., Addison-Wesley, 19-44.
 Bjarne S. (1997). The C++ Programming Language,
Addison-Wesley, 242-259.
73
Descargar

Practical RDF Ch.10