Data Structures: Follows on from CS211 C++, memory, etc. CS311 will also use C++ cout, objects, new, delete, etc. We'll mostly avoid private data members Syllabus and Calendar First: A review of C++ pointers We'll use them more than CS211 did Remembering CS253 could be helpful too They'll be used in CS430 and CS435 Memory areas: Heap vs. Stack allocation Picture on board Address range: Three variables from each Code segment also, to be complete We will be building data structures on the heap Why not the stack? Lifetime will not correlate with function calls Size will vary throughout the structure's lifetime A data structure contains a bunch of "normal" variables Structuring data, philisophical note: A lot of organizational schemes have a real-world analogy Trees, etc Retrieval time is usually important Just like in normal life Kitchens, projects, dentists, etc. What do we really want out of a data structure? Quick retrieval Quick addition of new data Quick deletion of data that actually frees up space Quick search Efficient use of memory Parallel access from multiple threads Parallel modification from multiple threads Simple enumeration of items (in sorted order) Doesn't lose data Accesses normally result in a CPU cache hit Low use of CPU resources (battery life) We'll cover traditional staples of data organization More important is to learn to think through data organization There are good libraries for the structures we'll learn Sometimes a custom solution is better It might not be exactly any of what we've discussed in this class If I don't think of a better demo: Put a bunch of integers in a chain and print them out or something