Programming

Preface xxv



Chapter 0: Notes to the Reader 1

0.1 The structure of this book 2

0.2 A philosophy of teaching and learning 6

0.3 Programming and computer science 12

0.4 Creativity and problem solving 12

0.5 Request for feedback 12

0.6 References 13

0.7 Biographies 13



Chapter 1: Computers, People, and Programming 17

1.1 Introduction 18

1.2 Software 19

1.3 People 21

1.4 Computer science 24

1.5 Computers are everywhere 25

1.6 Ideals for programmers 34



Part I: The Basics 41



Chapter 2: Hello, World! 43

2.1 Programs 44

2.2 The classic first program 45

2.3 Compilation 47

2.4 Linking 51

2.5 Programming environments 52



Chapter 3: Objects, Types, and Values 59

3.1 Input 60

3.2 Variables 62

3.3 Input and type 64

3.4 Operations and operators 66

3.5 Assignment and initialization 69

3.6 Composite assignment operators 73

3.7 Names 74

3.8 Types and objects 77

3.9 Type safety 78



Chapter 4: Computation 89

4.1 Computation 90

4.2 Objectives and tools 92

4.3 Expressions 94

4.4 Statements 100

4.4.1 Selection 102

4.4.2 Iteration 109

4.5 Functions 113

4.6 vector 117

4.7 Language features 125



Chapter 5: Errors 133

5.1 Introduction 134

5.2 Sources of errors 136

5.3 Compile-time errors 136

5.4 Link-time errors 139

5.5 Run-time errors 140

5.6 Exceptions 146

5.7 Logic errors 154

5.8 Estimation 157

5.9 Debugging 158

5.10 Pre- and post-conditions 163

5.11 Testing 166



Chapter 6: Writing a Program 173

6.1 A problem 174

6.2 Thinking about the problem 175

6.3 Back to the calculator! 178

6.4 Grammars 188

6.5 Turning a grammar into code 195

6.6 Trying the first version 203

6.7 Trying the second version 208

6.8 Token streams 209

6.9 Program structure 215



Chapter 7: Completing a Program 221

7.1 Introduction 222

7.2 Input and output 222

7.3 Error handling 224

7.4 Negative numbers 229

7.5 Remainder: % 230

7.6 Cleaning up the code 232

7.7 Recovering from errors 239

7.8 Variables 242



Chapter 8: Technicalities: Functions, etc. 255

8.1 Technicalities 256

8.2 Declarations and definitions 257

8.3 Header files 264

8.4 Scope 266

8.5 Function call and return 272

8.6 Order of evaluation 291

8.7 Namespaces 294



Chapter 9: Technicalities: Classes, etc. 303

9.1 User-defined types 304

9.2 Classes and members 305

9.3 Interface and implementation 306

9.4 Evolving a class 308

9.5 Enumerations 318

9.6 Operator overloading 321

9.7 Class interfaces 323

9.8 The Date class 334

Part II Input and Output 343



Chapter 10: Input and Output Streams 345

10.1 Input and output 346

10.2 The I/O stream model 347

10.3 Files 349

10.4 Opening a file 350

10.5 Reading and writing a file 352

10.6 I/O error handling 354

10.7 Reading a single value 358

10.8 User-defined output operators 363

10.9 User-defined input operators 365

10.10 A standard input loop 365

10.11 Reading a structured file 367



Chapter 11: Customizing Input and Output 379

11.1 Regularity and irregularity 380

11.2 Output formatting 380

11.3 File opening and positioning 388

11.4 String streams 394

11.5 Line-oriented input 395

11.6 Character classification 396

11.7 Using nonstandard separators 398

11.8 And there is so much more 406



Chapter 12: A Display Model 411

12.1 Why graphics? 412

12.2 A display model 413

12.3 A first example 414

12.4 Using a GUI library 418

12.5 Coordinates 419

12.6 Shapes 420

12.7 Using Shape primitives 421

12.8 Getting this to run 435



Chapter 13: Graphics Classes 441

13.1 Overview of graphics classes 442

13.2 Point and Line 444

13.3 Lines 447

13.4 Color 450

13.5 Line_style 452

13.6 Open_polyline 455

13.7 Closed_polyline 456

13.8 Polygon 458

13.9 Rectangle 460

13.10 Managing unnamed objects 465

13.11 Text 467

13.12 Circle 470

13.13 Ellipse 472

13.14 Marked_polyline 474

13.15 Marks 476

13.16 Mark 478

13.17 Images 479



Chapter 14: Graphics Class Design 487

14.1 Design principles 488

14.2 Shape 493

14.3 Base and derived classes 504

14.4 Benefits of object-oriented programming 513



Chapter 15: Graphing Functions and Data 519

15.1 Introduction 520

15.2 Graphing simple functions 520

15.3 Function 524

15.4 Axis 529

15.5 Approximation 532

15.6 Graphing data 537



Chapter 16: Graphical User Interfaces 551

16.1 User interface alternatives 552

16.2 The "Next" button 553

16.3 A simple window 554

16.4 Button and other Widgets 561

16.5 An example 565

16.6 Control inversion 569

16.7 Adding a menu 570

16.8 Debugging GUI code 575



Part III: Data and Algorithms 581



Chapter 17: Vector and Free Store 583

17.1 Introduction 584

17.2 vector basics 586

17.3 Memory, addresses, and pointers 588

17.4 Free store and pointers 591

17.5 Destructors 601

17.6 Access to elements 605

17.7 Pointers to class objects 606

17.8 Messing with types: void* and casts 608

17.9 Pointers and references 610

17.10 The this pointer 618



Chapter 18: Vectors and Arrays 627

18.1 Introduction 628

18.2 Initialization 629

18.3 Copying 631

18.4 Essential operations 640

18.5 Access to vector elements 646

18.5.1 Overloading on const 647

18.6 Arrays 648

18.7 Examples: palindrome 659



Chapter 19: Vector, Templates, and Exceptions 667

19.1 The problems 668

19.2 Changing size 671

19.3 Templates 678

19.4 Range checking and exceptions 693

19.5 Resources and exceptions 697



Chapter 20: Containers and Iterators 711

20.1 Storing and processing data 712

20.2 STL ideals 717

20.3 Sequences and iterators 720

20.4 Linked lists 724

20.5 Generalizing vector yet again 729

20.6 An example: a simple text editor 734

20.7 vector, list, and string 741

20.8 Adapting our vector to the STL 745

20.9 Adapting built-in arrays to the STL 747

20.10 Container overview 749



Chapter 21: Algorithms and Maps 757

21.1 Standard library algorithms 758

21.2 The simplest algorithm: find() 759

21.3 The general search: find_if() 763

21.4 Function objects 765

21.5 Numerical algorithms 770

21.6 Associative containers 776

21.7 Copying 789

21.8 Sorting and searching 794

21.9 Container algorithms 797



Part IV: Broadening the View 803



Chapter 22: Ideals and History 805

22.1 History, ideals, and professionalism 806

22.2 Programming language history overview 818



Chapter 23: Text Manipulation 849

23.1 Text 850

23.2 Strings 850

23.3 I/O streams 855

23.4 Maps 855

23.5 A problem 864

23.6 The idea of regular expressions 866

23.7 Searching with regular expressions 869

23.8 Regular expression syntax 872

23.9 Matching with regular expressions 880

23.10 References 885



Chapter 24: Numerics 889

24.1 Introduction 890

24.2 Size, precision, and overflow 890

24.3 Arrays 895

24.4 C-style multidimensional arrays 896

24.5 The Matrix library 897

24.6 An example: solving linear equations 908

24.7 Random numbers 914

24.8 The standard mathematical functions 917

24.9 Complex numbers 919

24.10 References 920



Chapter 25: Embedded Systems Programming 925

25.1 Embedded systems 926

25.2 Basic concepts 929

25.3 Memory management 935

25.4 Addresses, pointers, and arrays 943

25.5 Bits, bytes, and words 954

25.6 Coding standards 974



Chapter 26: Testing 989

26.1 What we want 990

26.2 Proofs 992

26.3 Testing 992

26.4 Design for testing 1011

26.5 Debugging 1012

26.6 Performance 1012

26.7 References 1016



Chapter 27: The C Programming Language 1021

27.1 C and C++: siblings 1022

27.2 Functions 1028

27.3 Minor language differences 1036

27.4 Free store 1043

27.5 C-style strings 1045

27.6 Input/output: stdio 1050

27.7 Constants and macros 1054

27.8 Macros 1055

27.9 An example: intrusive containers 1059



Part V: Appendices 1071



Appendix A: Language Summary 1073

A.1 General 1074

A.2 Literals 1077

A.3 Identifiers 1081

A.4 Scope, storage class, and lifetime 1082

A.5 Expressions 1086

A.6 Statements 1096

A.7 Declarations 1098

A.8 Built-in types 1099

A.9 Functions 1103

A.10 User-defined types 1106

A.11 Enumerations 1107

A.12 Classes 1108

A.13 Templates 1121

A.14 Exceptions 1125

A.15 Namespaces 1127

A.16 Aliases 1128

A.17 Preprocessor directives 1128



Appendix B: Standard Library Summary 1131

B.1 Overview 1132

B.2 Error handling 1137

B.3 Iterators 1139

B.4 Containers 1144

B.5 Algorithms 1152

B.6 STL utilities 1162

B.7 I/O streams 1168

B.8 String manipulation 1175

B.9 Numerics 1180

B.10 Time 1185

B.11 C standard library functions 1185

B.12 Other libraries 1195



Appendix C: Getting Started with Visual Studio 1197

C.1 Getting a program to run 1198

C.2 Installing Visual Studio 1198

C.3 Creating and running a program 1199

C.4 Later 1201



Appendix D: Installing FLTK 1203

D.1 Introduction 1204

D.2 Downloading FLTK 1204

D.3 Installing FLTK 1205

D.4 Using FLTK in Visual Studio 1205

D.5 Testing if it all worked 1206



Appendix E: GUI Implementation 1207

E.1 Callback implementation 1208

E.2 Widget implementation 1209

E.3 Window implementation 1210

E.4 Vector_ref 1212

E.5 An example: manipulating Widgets 1213



Glossary 1217

Bibliography 1223

Index 1227