DOC PREVIEW
Duke CPS 108 - Java Collections to STL

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Software Design1.1Java Collections to STL What’s the difference between ArrayList and vector How to access each element? Safety and the kitchen sink• What happens with t[21] on a 21-element vector?• Part of STL means crufty code (whose viewpoint?) Differences in wordlines.cpp and wordlines.java Map compared to map, what other kinds of maps? Sets and vectors, which is easier to use? Anything not clear in either program? Are these programsobject-oriented?Software Design1.2Standard Libraries In C++ there is the Standard Library, formerly known as theStandard Template Library or STL Emphasizes generic programming (using templates) Write a sorting routine, the implementation depends on• Elements being comparable• Elements being assignable We should be able to write a routine not specific to int, string orany other type, but to a generic type that supports beingcomparable/assignable In C++ a templated function/class is a code-factory, generatescode specific to a type at compile time Arguably hard to use and unsafeSoftware Design1.3STL concepts Container: stores objects, supports iteration over the objects Containers may be accessible in different orders Containers may support adding/removing elements e.g., vector, map, set, deque, list, multiset, multimap Iterator: interface between container and algorithm Point to objects and move through a range of objects Many kinds: input, forward, random access, bidirectional Syntax is pointer like, analogous to (low-level) arrays Algorithms find, count, copy, sort, shuffle, reverse, …Software Design1.4Iterator specifics An iterator is dereferenceable, like a pointer *it is the object an iterator points to An iterator accesses half-open ranges, [first..last), it can have a value oflast, but then not dereferenceable Analogous to built-in arrays as we’ll see, one past end is ok An iterator can be incremented to move through its range Past-the-end iterators not incrementablevector<int> v; for(int k=0; k < 23; k++) v.push_back(k);vector<int>::iterator it = v.begin();while (it != v.end()) { cout << *v << endl; v++;}Software Design1.5From Java to STL iterators In Java Iterator is an interface Collection(s) are required to have iterators, these are used in someoperations like max, min, construct vector, … Related to STL as algorithm glue, but very different In STL an iterator is a concept, there are refinements Input, output, forward, bidirectional, random access• A forward iterator is an input iterator and an output iterator• The iterator may be immutable (or const)---read only Refinements not implemented by inheritance, but by design, contract,and subsequently implementation• What happens if you try to implement an STL iterator?Software Design1.6Iterator as Pattern (GOF) Provides access to elements of aggregate objectsequentially without exposing aggregate’s representation Support multiple traversals Supply uniform interface for different aggregates: this ispolymorphic iteration (see C++ and Java) Solution: tightly coupled classes for storing and iterating Aggregate sometimes creates iterator (Factory pattern) Iterator knows about aggregate, maintains state Forces and consequences Who controls iteration (internal iterator, apply in MultiSet)? Who defines traversal method? Robust in face of insertions and deletions?Software Design1.7STL overview STL implements generic programming in C++ Container classes, e.g., vector, stack, deque, set, map Algorithms, e.g., search, sort, find, unique, match, … Iterators: pointers to beginning and one past the end Function objects: less, greater, comparators Algorithms and containers decoupled, connected by iterators Why is decoupling good? Extensible: create new algorithms, new containers, new iterators,etc. Syntax of iterators reflects array/pointer origins, an array can beused as an iteratorSoftware Design1.8STL examples: wordlines.cpp How does an iterator work? Start at beginning, iterate until end: use [first..last) interval Pointer syntax to access element and make progressvector<int> v; // push elementsvector<int>::iterator first = v.begin();vector<int>::iterator last = v.end();while (first < last) { cout << *first << endl; first++;} Will the while loop work with an array/pointer? In practice, iterators aren’t always explicitly defined, but passed asarguments to other STL


View Full Document

Duke CPS 108 - Java Collections to STL

Download Java Collections to STL
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Java Collections to STL and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Java Collections to STL 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?