Multi-Paradigm Programming in C++: Sequential Containers
A detailed overview of structuring and implementing containers in C++, emphasizing the importance of container-level interfaces and iterators. Explore the fundamental concepts and principles governing containers, including ownership of elements, range definitions, and interface implementations for seamless data manipulation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
E81 CSE 428S: Multi-Paradigm Programming in C++ Sequential Containers Department of Computer Science & Engineering Washington University, St. Louis MO Adam Mitz mitzah@wustl.edu 1
Structure and Container-Level Interfaces A container is parameterized with its elements type Defines ordered and non-overlapping ranges of elements A given location cannot be within more than one container Adding or copying elements into a container is by value A container owns the elements within it: the container s destructor destroys the elements that it contains A container provides several kinds of interfaces To get iterators over elements, e.g., begin() and end() Functions to add values, e.g., push_back() , emplace_back() Container-specific callables e.g. operator[] if random access Obeys principle of least surprise e.g., no operator[]for list
Containers Provide Their Own Iterators Containers declare associated iterator types // try to use const_iterators whenever you can vector<int>::iterator i; // iterator over non-const vector<int>::const_iterator ci; // iterator over const Also give iterator accessor/factory methods for beginning of and just past the end of range // v is previously declared as vector<int> v; auto ci2 = v.cbegin(); // use a const_iterator while (ci2 != v.cend()) { // compare to const_iterator cout << *ci2 << endl; // does not modify v ++ci2; }
More About Container Iterators Their iterators generalize different uses of pointers Most importantly, they define left-inclusive intervals over the ranges of elements in a container [begin, end) Interface between algorithms and data structures Algorithm manipulates iterators, not containers An iterator s value can represent 3 kinds of states: dereferenceable(points to a valid location in a range) past the end(points just past last valid location in a range) singular(points to nothing) What's an example of a pointer in each of these states? Can construct, compare, copy, and assign iterators so that fundamental types and library types can inter- operate
Properties of Iterator Intervals valid intervals can be traversed safely with an iterator An empty range [p, p) is valid If [first, last) is valid and non-empty, then [first+1, last) is also valid Proof: iterative induction on the interval If both [first, mid) and [mid, last) are valid, then [first, last) is valid Proof: divide and conquer induction on the interval Corollary: if [first, last) is valid and position mid is safelyreachable from first, and last is safely reachable from mid, then both [first, mid) and [mid, last) are also valid
Some Standard Sequential Containers The std::deque class template Double ended queue that can grow efficiently at either end E.g., using its push/emplace_front/back member functions Provides fast random access indexing (in constant time) The std::vector class template Behaves like an array but can grow efficiently at the back E.g., using its push_back or emplace_back member functions Provides fast random access indexing (in constant time) The std::list class template Doubly-linked list, can grow/shrink efficiently at any position E.g., using its insert/emplace/erase member functions Provides iteration in either direction, but not indexing The std::forward_list class template Singly-linked list, can grow/shrink efficiently at any position E.g., using its insert/emplace/erase member functions Provides forward iteration, not indexing or backward iteration CSE 428S Multi-Paradigm Programming in C++ 6
Insertion vs. Emplacement Insertion may have extra overhead for copying vector<string> courses; courses.push_back("cse428"); // 2 constructor calls Emplacement may be more efficient, if types constructors match arguments vector<string> courses; courses.emplace_back("cse428"); // 1 constructor call // due to forwarding
Container Type Requirements/Operations Sequential containers impose only a few requirements on the types they contain (often to maintain efficiency) E.g., types in a container must support default initialization or construction to make (re-)sizing a container possible and efficient The operations provided by a container and its iterators are specific to the container s complexity/efficiency requirements E.g., random access iterators for std::vector and std::deque support +=, ++, and -- operators with constant time complexity E.g., bidirectional iterators for std::list support ++ and -- operators with constant time complexity, but +=isn t supported E.g., forward iterators for std::forward_list support ++ with constant time complexity, but don t support either -- or += C++ library containers iterator ranges are left-inclusive An iterator range is from first up to but not including last Also shown as [first, last) to indicate closed-open semantics Allows easy representation of empty ranges (first == last) and past-the-end iterators for things like strings, iostreams, etc. CSE 428S Multi-Paradigm Programming in C++ 8
Studio 17 Looks at iteration through an array using pointers and formulas for the size of the array (in bytes), the size of an element in the array (in bytes), and from those the number of elements in an array Considers how iteration can be defined generically using a limited set of required operators Explores which containers support operator[] Studios 12 through 19 are due 11:59pm November 25th (night before Exam 1) Submit as soon as each is done so you get feedback and can resubmit any that may be marked incomplete CSE 428S Multi-Paradigm Programming in C++ 9
