C/C++ Pointers - Fresh Sources

C/C++ Pointers - Fresh Sources

CNS 3370 Sequences vector,deque,list,(string),forward_list Container Adapters queue, stack, priority_queue Associative

Containers set, unordered_set map, unordered_map plus multi_ versions of each of the above bool empty(); // use instead of size_t size(); void resize(size_t, T = T()); T& front(); T& back();

// Not void push_back(const T&); // Not void pop_back(); // Not size() == 0 forward_list forward_list forward_list

// deque and list/forward_list only: void push_front(const T&); void pop_front(); //deque, vector and string only: T& at(size_type n); // range-checked T& operator[] shrink_to_fit(); Generalization of a pointer Overload at least operator!=,

operator==, operator*, operator++, operator-> Some overload operator--, pointer arithmetic operator[], template Iterator

find(Iterator start, Iterator past, const T& v) { while (start != past) { if (*start == v) break; ++start; } return start; } All algorithms are implemented in terms of iterators

Input Output Forward Bi-directional Random Access Modeled after file input Read-only access to elements

Single-pass, forward traversal find expects an Input Iterator it only needs to read through the data once template

InputIterator find(InputIterator start, InputIterator past, const T& v) { while (start != past) { if (*start == v) break; ++start; } return start; }

Modeled after file output Write-only access to elements Single-pass, forward traversal Example: ostream_iterator: copy(a, a+n, ostream_iterator(cout, ));

Both read and write access can be used as Input or Output Iterators Multiple-pass, unique forward traversal

expects a Forward Iterator list::iterator p = unique(lst.first(), lst.end()); It needs 2 simultaneous, read/write iterators Can do everything a Forward Iterator

can Also support backwards traversal operator--() operator--(int) requires a Bi-directional Iterator reverse

list::iterator p = lst.end(); while (p != lst.begin()) { --p; // advances backwards // process *p } list::reverse_iterator p = lst.rbegin(); while (p != lst.rend()) { // process *p, then:

++p; // advances backwards } Modeled after pointers support Pointer Arithmetic in constant time operator+, +=, -, -=, [], <, <=, >, >=

expects a Random Access Iterator sort Functional inheritance via duck typing (not via classes) Doesnt

provide a Random Access Iterator Generic sort will fail on a list Answer: Provides its own sort member function Also merge, remove, and

unique vector v1; // fill v1, then: vector v2; copy(v1.begin(), v1.end(), v2.begin()); Iterators work in overwrite mode by

default Need an insert mode for cases like above that calls the appropriate insert operation provided by the container Replace output calls (operator*, operator=, etc.) with appropriate insert function

back_insert_iterator calls push_back front_insert_iterator calls push_front insert_iterator calls insert

vector v1; // fill v1, then: vector v2; copy(v1.begin(), v1.end(), back_inserter(v2)); (But there is still a better way) back_inserter creates a back_insert_iterator

front_inserter creates a front_insert_iterator inserter creates an insert_iterator ostream_iterator an Output Iterator copy(v1.begin(), v1.end(), ostream_iterator(cout, ));

istream_iterator an Input Iterator copy(istream_iterator(cin), istream_iterator(), back_inserter(v1)); insert, assign, erase, and constructors

Usually more efficient than the generic algorithm counterparts Prefer over using copy See range-based.cpp For erasing selected elements of a sequence applies to vector, deque, string for lists, use remove/remove_if

The idiom: The remove algorithm reorders the sequence, moving the deleted elements to the end returning an iterator to the first deleted element c.erase(remove(beg, end, x), end); c.erase(remove_if(beg, end, pred), end); Higher-level Containers that use Sequences

High-level abstract data types queue, stack, priority_queue They adapt sequences for specific uses i.e., they use a sequence for implementation stack & queue use deque by default priority_queue uses a vector can change the underlying sequence:

stack> myStack; No iterators are provided they offer a more restricted interface queue: pushes at end, pops from front front, back, push, pop

stack: pushes and pops at front top, push, pop priority_queue: (See pq.cpp, pq2.cpp) retrieves elements in priority order you provide a strict weak ordering priority_queue

and ordered associative containers (set, map, multi_set, multi_map) require strict weak ordering comparators behave like less< >( ) ( (which calls operator<( )) never use <= or anything like it!!! Definition: f(x,y) is a SWO if: f(x,x) = false (irreflexive) f(x,y) = !f(y,x) (anti-symmetric) f(x,y) && f(y,z) => f(x,z)

(transitive) Two flavors Ordered tree-based storage O(log n) retrieval set, multi_set, map, multi_map Unordered hashed-based storage O(1) retrieval unordered_set, unordered_map

#include #include #include using namespace std; int main() { // Populate a set: set s; s.insert("Alabama"); s.insert("Georgia"); s.insert("Tennessee"); s.insert("Tennessee");

// Print it out: auto p = s.begin(); while (p != s.end()) cout << *p++ << endl; cout << endl; // Do some searches: string key = "Alabama"; p = s.find(key); cout << (p != s.end() ? "found " : "didn't find ") << key << endl; key = "Michigan"; p = s.find(key); cout << (p != s.end() ? "found " : "didn't find ") << key << endl; } // Output: Alabama Georgia Tennessee found Alabama didn't find Michigan

#include #include

#include using namespace std; int main() { // Insert some elements (two ways): map> m; m.insert(make_pair(string("Alabama"), string("Montgomery"))); m["Georgia"] = "Atlanta"; m["Tennessee"] = "Knoxville";

m["Tennessee"] = "Nashville"; // overwrites // Print auto p = while (p auto cout the map: m.begin(); != m.end()) { elem = *p++;

<< '{' << elem.first << ', << elem.second << "}\n"; } cout << endl; } // Retrieve via a key: cout << '"' << m["Georgia"] << '"' << endl; cout << m.size() << endl; cout << '"' << m["Texas"] << '"' << endl; cout << m.size() << endl; // Output: {Tennessee,Nashville} {Georgia,Atlanta} {Alabama,Montgomery} "Atlanta" 3 "" 4 Shows

the conciseness of maps design Count the number of each word in a text file wordcount.cpp output in wordcount-gettysburg.out Necessary to maintain proper order in

the underlying tree data structure They test for equivalence, not equality, to maintain uniqueness x and y are equivalent iff !cmp(x,y) && ! cmp(y,x) i.e., neither precedes the other Example: swo.cpp ignores non-alpha characters in strings

Recently Viewed Presentations

  • EECS 473 Advanced Embedded Systems Lecture 14 Wireless

    EECS 473 Advanced Embedded Systems Lecture 14 Wireless

    This not only makes the math easier, it means that because the addition of Gaussians is a Gaussian, all noise sources can be modeled as a single source. Also note, this includes our inability to distinguish different voltages. Effectively quantization...
  • Title Goes Here Presenter Name Here Title Goes

    Title Goes Here Presenter Name Here Title Goes

    • Bullet Point #1 Goes Here. Supporting copy can go here. • Bullet Point #2 Goes Here - Sub-bullet point should be formatted like this. - Sub-bullet point should be formatted like this. - Sub-bullet point should be formatted like...
  • Unit 1: World at risk case studies - Rawlins A-level Geography

    Unit 1: World at risk case studies - Rawlins A-level Geography

    What is a disaster Hotspot? Hotspots are multiple hazard zones (2+) Identification of disaster hotspots has major implications for development and investment planning, and for disaster preparedness and loss prevention. However, many of these countries have more pressing needs to...
  • The Man Who Named the Clouds - PC&#92;|MAC

    The Man Who Named the Clouds - PC\|MAC

    How about taking them to whole new level! ... Then, using your context clues…write a synonym for each vocab word. Vocabulary. destruction. expected. We'll compare your work at the end of the lesson! Now…let's take a look at your new...
  • 20th and 21st Century Classroom Management Pioneers

    20th and 21st Century Classroom Management Pioneers

    Redl & Wattenberg believed that discipline was closely linked to group behavior, as students behaved differently when they were in a group than when they were alone. They suggested that student behavior was strongly influenced by the dynamics of a...
  • Air Pollution - WordPress.com

    Air Pollution - WordPress.com

    unburnt hydrocarbons. carbon dioxide. nitrogen. water. Out of the exhaust. ALL Explain the products formed by the complete and incomplete combustion of hydrocarbons. MOST Explain how sulfur dioxide and nitrogen oxides are produced in some combustion reactions and cause acid...
  • 14 October 2009 Chapter 7 Sensory Physiology Aspects

    14 October 2009 Chapter 7 Sensory Physiology Aspects

    (location enhanced by lateral inhibition) How long? (duration, onset/offset.. Adaptation) How strong? (intensity) Figure 7.01 1st order sensory neuron 1st order sensory neuron Example: a rod or cone of the retina Figure 7.16 Adequate Stimulus & Labeled Line Each type...
  • SESSION 9 PLANNING AND IMPLEMENTING A CENSUS GEOSPATIAL

    SESSION 9 PLANNING AND IMPLEMENTING A CENSUS GEOSPATIAL

    SESSION 9. PLANNING AND IMPLEMENTING A CENSUS GEOSPATIAL PROGRAMME. FOR RWANDA 2022 HPC. as presented . By Jimmy MUKASA. Director of ICT Unit @ NISR . During UN Regional Workshop on the 2020 World Programme on Population and Housing Censuses:...