CS32: Final Study Guide
CS32: Final Study Guide
Popular in Course
verified elite notetaker
Popular in ComputerScienence
Ted Robel Sr.
verified elite notetaker
This 9 page Bundle was uploaded by logeybearrr on Saturday June 7, 2014. The Bundle belongs to a course at University of California Santa Barbara taught by a professor in Fall. Since its upload, it has received 240 views.
Reviews for CS32: Final Study Guide
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 06/07/14
From Source File to Executable File Compilation linking loading and execution High level symbolic languages were invented to make it simpler and more convenient for the programmer to write a program The main purposes of the compiler are translating each instruction of the source language into a set of machine instructions o Replacing each symbolic reference by an address reference Linking actually consists of relocation and linking of object modules Objects defined outside of functions have storage class static global objects they exist for the duration of the execution of the ro ram O An object module contains all source code statements translated to machine instructions Header Machine Code Initialized Data Symbol Table Relocation Information Section The header section contains the sizes of all the other sections involved o Including size of uninitialized data section not created until load time The transformation of symbolic references into address references in terms of offset distance in bytes from the beginning of the object module Linking External address references in each object module must be resolved The load module represents the abstract notion of the program address space all address references are in the form of the offset from the beginning of the load module relative or logical addresses o The loaderOS must map the logical addresses to physical addresses in the main memory and copy the binary information to these memori locations 0 0 Programs in general need the ability to request and obtain more memory dynamically managed by the program memory manager 0 Local variables are stored on the stack Variables and Objects Pointers and Addresses A variable corresponds to a segment in memory The binary code stored in that se ment is the value of the variable o The memory of a structure is contiguous It is much more efficient to waste some memory with padding and align the components with a machine word 4 bytes boundaries in the h sical memory endian b te order is on the right network byte order 0 In the little endian byte order the less significant byte is on the left while the more significant byte is on the right 0 Beware uninitialized and dangling pointers Dynamic Allocation and Deallocation of Memory 0 Modern OS have a process memory manager software that is responsible for providing additional allocation of memory to its process and for deallocation when the memory is no longer needed 0 The OS memory manager allocates large chunks of memory to individual process memory managers and keeps track of them 0 Each process memory manager allocates smaller chunks of the memory to its process and keeps track of allocated and free segments o When its process requests deallocation it puts that segment on the list of free segments o If running out of memory it requests another big chunk from the OS memory manager 0 It is more efficient not to have the process manager return freed memory segments to the OS memory manager The freed segments are kept by the process memory manager for serving future requests and possible unifying adjacent segments into bigger ones 171 Templates for Algorithm Abstraction The template prefix templateltclass Tgt tells the compiler that the definition or function declaration that follows is a template and T is a type parameter class means type A separate definition will be produced for each different type for which iou use the template but not for ani tipes iou do not use Do not use template function declarations and be sure the function template definition appears in the same file it is used before the function template is used Could be used through a incude directive if compiler allows It is possible to have function templates that have more than one type parameter templateltclass T1 class T2gt Function declaration for a function template o templateltclass Tgt o void showstuffTamp stuff2 Tamp stuff3 Function definition for a function template o templateltclass Tgt o void showstuffTamp stuff2 Tamp stuff3 implementation Templates allow for algorithm abstraction expressing algorithms in a very general way so that we can ignore incidental detail and concentrate on the substantive part of the algorithm 172 Templates for Data Abstraction A class template is preceded by the same template prefix templateltclass Tgt Once the class template is defined you can declare objects of this class The declaration must specify what type is to be filled in for T o Pairltintgt score or Pairltchargt seats The oblects are then used iust like ani other obiects o templateltclass Tgt o void PairltTgtseteementint position T value imp The name of a class template may be used as a type for a function parameter int addupconst Pairltintgtamp thepair or templateltclass Tgt T addupconst PairltTgtamp thepair OOOO 0 Introduction Data structures held in the STL are called container classes because they are used to hold collections of data The classes in the STL are template classes and make extensive use of iterators objects that facilitate cycling through the data in a container The STL differs from other C libraries in that the classes and algorithms are generic 181 Iterators Iterators are a generalization of pointers but not pointers usinclq std vectorltintgt iterator An iterator variables is located points to one data entry in the container Can use or to traverse or for logic and to dereference the iterator and access the data located at the iterator using std vector permits access and load of vector container vectorltintgt container creates container of type int vector vectorltintgt iterator p creates iterator of type int vector using std vectorltintgt iterator iterator p p2 and p2 will both access the third element of the container but leaves p where it was These provide random access you can access any particular element in one step Forward Iterators works on the iterator Bidirectional Iterators and work on the iterator Random Access Iterators and random access work on the iterator With a constant iterator the dereferencing operator produces a read only version of the element With a mutable iterator the dereferencing operator can be used to assign a value to change the corresponding element in the container If a container only has constant iterators you cannot obtain a mutable iterator however if a container has mutable iterators you can have a constant iterator A reverseiterator can be used to cycle through all elements of a container provided the container has bidirectional iterators o Also has a constant version constreverseiterator Input and output iterators can be used with input and output streams 182 Containers Each container class data structure is a template class with a parameter for the particular type of data to be stored A sequential container arranges its data items into a list so that there is a first element next element and so forth up to a last element list vector deque o The STL container for lists is a doubly linked list o With a queue you can add data at one end of the data sequence and remove data from the other end o With a deque you can add data at either end and remove data from either end When adding or removing an element to or from a container there is no guarantee that the iterators will be located at the same element o stackltint dequeltintgt gt o Items are retrieved by their key The set template class stores elements without repetition and each element is its own key o setltT orderinggt s A map is essentially a function given as a set of ordered pairs o mapltKeyType Tgt m or mapltKeyType T Orderinggt m o mapltstring intgt numbermap assign a number to a string A map can be thought of as an associative array A map object stores its elements in sorted order by its key values The operator can be used to add a new item to the map or to replace an existing entry The map template class uses the pair template class to store the association between the key and a data item Multiset allows repetition of elements Multimap allows multiple values multiple values to be associate with each key value 183 Generic Algorithms Function templates in the STL are sometimes called generic algorithms In the STL the interface tells the programmer what the function does how functions are used and how rapidly efficient the task will be done The big O estimate is a worst case estimate of a program39s efficiency o Look only at the term with the highest exponent and do not pay attention to constant multiples o Linear running time On o Quadratic running time On 2 o Oogn is extremely fast The generic find function is a nonmodifying sequence algorithm o It can be used with any of the STL sequential container classes o However it takes iterators as arguments so the container must have iterators The movement from some iterator first often containerbegin up to but not including some location ast often containerend is so common it has come to have a special name rangefirst last Modifying Generic Functions copy remove reverse randomshuffe Generic set operation functions work with containers that store their elements in sorted order set map multiset multimap o includes setunion setintersection setdifference Generic Sorting Algorithms merge merges the two ranges into a sorted range Introduction 0 A library is a set of functions and the code does not need to be rewritten for every program that uses it o A single library tends to contain functions concerning a single topic 81 Using a Library 0 First one or more header files must be included in the program code o include ltmathhgt Second the library must be linked into the executable o gcc o sq sqc m link library file named m 811 Header Files 0 A header files does not contain the code for any of the functions in the library 0 It contains function prototypes constants define typedef and struct definitions to createedit data types 0 If a header file is placed in a different location use the Ipath command line argument o gcc o sq sqc Iusrincludemathlib m 812 Library Files 0 A library file contains the actual code for the functions in the library o Begin with the letters ib and have filename suffix a o The command line argument Lusrx11R6ib tells the compiler to add the path usrx11R6ib to the set of directories in which to find library files 0 The code is precompiled and ready to be linked 82 Purpose of Libraries 0 Avoiding repetition o Avoiding recoding difficult code 0 Allowing for cross patform code 83 The C Standard Library 0 The C standard library is a collection of libraries It includes functions covering a wide variety of topics and is organized into multiple files different parts of it are referred to in isolation Not necessary to link c because many compilers link by default 84 The Curses Library 0 gcc o hello heoc ncurses Curses functions cannot be used prior to calling initscr and a program should always call endwin to close out use of library 841 IO Control 0 8411 Buffering o The process of temporarily storing bytes on a stream and grouping them up before transferring them to the destination o Character input is unbuffered by default however scanf is line buffer because it waits for enter keystroke 8412 Echoing o Echoing refers to the process of copying bytes from the input stream to the output stream 0 8413 Blocking o Blocking refers to the process of how the program will wait for bytes to appear on the input stream On program will not continue until input is received Off the function call will check to see if data is present o Blocking can occur for a preselected amount of time 842 Dynamic Graphics 0 The curses library can be used to create dynamic or moving graphics 0 8421 Motion o To create a moving graphic erase the screen at the graphic s previous location and redraw it at an adjacent location o Draw the graphic flush the buffer pause the program erase the graphic and move to new location 0 8422 User Input During Motion o Blocking must be turned off o Polling The process of using a nonblocking function call to check for user input and acting upon the input if given but otherwise continuing program execution o Most programs that use dynamic graphics have echoing switched off 0 8423 Varying Rate Graphics o Graphics move at the rate defined by the amount of time spent paused in each iteration o Use modulus arithmetic on the loop counter to control when the motion of each graphic occurs 85 The X Library 0 Allows the same application to work with different graphics displays having varying capabilities As graphics hardware capabilities have expanded a hierarchy of graphics libraries has evolved o The X library provides for the creation and manipulation of windows 0 The lack of standardization on Unix systems is a result of modular development allowing users maximum flexibility 851 Windows 0 The basic construct in X library programming is a window a virtual monitor or display created for a program 854 User Input 0 Using the X library user input is provided to a program through an event 855 Fonts 0 With the X library a program can draw text at any location in a window There is not character grid instead the units of location are pixels 86 Making a Library 0 First source code for the desired functions must be compiled and stored in object code files o gcc c argestc o gcc c twoc Second the object files are packaged together to create a library file On a Unix system the program ar is used to package object code files into a library file o ar r ibcustoma argesto twoo Third an include file is normally written defining the prototypes of the functions in the library file o customibh 87 Library Pitfalls Programs can become bloated and difficult to maintain simply because they have been linked to too many libraries
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'