Publish on 07th November 2019
Category: Birds
0

Using Sequential Containers

Lecture 8Hartmut [email protected]://www.cct.lsu.edu/˜hkaiser/spring_2015/csc1254.html

Programming Principle of the Day

Principle of leastastonishment (POLA/PLA)Theprinciple of least astonishment is usually referenced in regards to the user interface, but the same principle applies to written code.Codeshouldsurprisethe reader as little as possible.Thatmeans following standard conventions, code should do what the comments and name suggest, and potentially surprising side effects should be avoided asmuchas possible.http://en.wikipedia.org/wiki/Principle_of_least_astonishment

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

2

Abstract

We start looking beyond vector and string. We will focus on sequential containers and demonstrate a couple of problems we can solve when applying them.The standard library’s architecture will start to get visible. That will help us to start understanding how to use all of the different containers in the standard library.

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

3

Separating Students into Categories

Sort out failed studentsWho failed?Remove from our dataCreate a new vector ofstudent_datacontaining only students who succeeded:// predicate to determine whether a student failedboolfail_grade(student_infoconst& s){returngrade(s) < 60;}Pushstudent data onto one of two containers based on this predicate

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

4

Separating Students into Categories

What’s wrong here? (Hint: what’s the memory consumption?)// separate passing and failing student records: first tryvector<student_info>extract_fails(vector<student_info>& students){vector<student_info> pass, fail;for(vector<student_info>::size_type i = 0;i != students.size(); ++i){if(fail_grade(students[i]))fail.push_back(students[i]);elsepass.push_back(students[i]);}students = pass;returnfail;}

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

5

Separating Students into Categories

Requires twice as much memoryEach record is held twiceBetter to copy failed students, removing the data from original vectorHow to remove elements from a vector?Slow, too slow for larger amounts of data.Why?What happens if all students have failed?This can be solved by either using a different data structure or by modifying the algorithm

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

6

ErasingElementsinPlace

Slow, but direct solution (Why is it slow?)// second try: correct but potentially slowvector<student_info>extract_fails(vector<student_info>& students){vector<student_info> fail;vector<student_info>::size_typei= 0;// invariant: elements [0,i) of students represent passing gradeswhile(i!=students.size()) {if(fail_grade(students[i])) {fail.push_back(students[i]};students.erase(students.begin() +i);}else++i;}returnfail;}

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

7

Erasing Elements in Place

The erase() function takes a special type ‘pointing’ (referring) to the element to erase:students.erase(students.begin() +i);

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

8

Elements we’ve already seen

FAIL

Elements we haven’t processed

Elementi

students.size() == n

Elements we’ve already seen

Elements we haven’t processed

students.size() == n - 1

(These elements are copied)

Erasing Elements in Place

Caution: why will this fail?// this code will fail because of misguided optimizationautosize =students.size();while(i!= size) {if(fail_grade(students[i])) {fail.push_back(students[i]);students.erase(students.begin() +i);}else++i;}

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

9

SequentialVersus Random Access

Both versions share a non-obvious propertyThe elements are accessed sequentially onlyWe used integer ‘i’ as an index, which hides thatNeed to analyze every operation on ‘i’ to verifyWe might access student data in arbitrary orderEvery container type has its performance characteristics for certain operationsBy knowing what access pattern we use we can utilize the ‘best’ container type

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

10

Sequential Versus Random Access

Let’s restrict our access to being sequentialThe standard library exposes special types we can use to express this intent:IteratorsBy choosing the right type of iterator we ‘tell’ the library what access pattern we need to supportAllows for optimal selection of the underlying algorithm implementation

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

11

Iterators

Our code uses the index forAccess of an elementfgrade(students[i])Moveto the nextelement (increment ‘i’)while(i!=students.size()) {// work gets done here; but doesn't change the value ofii++;}We useindex for sequential access only!But there is no way of telling the library about this

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

12

Iterators

Iterators are special typesIdentifya container and an element in thecontainerLetus examine the value stored in that elementProvideoperations for moving between elements in the containerRestrictthe available operations in ways that correspond to what the containercan handleefficiently

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

13

Iterators

Code using iterators is often analogous to index based code:// code based on indiciesfor(vector<student_info>::size_typei = 0;i!= students.size(); ++i){cout<< students[i].name <<endl;}// code based on iteratorsfor(vector<student_info>::const_iteratoriter=students.begin();iter!=students.end(); ++iter){cout<< (*iter).name <<endl;}

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

14

Iterator Types

Every standard container, such as vector, defines two associated iterator types:container_type::iteratorcontainer_type::const_iteratorWherecontainer_typeis the container (vector<student_info>)Useiteratorto modify the element,const_iteratorotherwise (read only access)Note, that we don‘t actually see the actual type, we just know what we can do with it.Abstraction is selectiveignorance!

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

15

Iterators, C++11

Code using iterators is often analogous to index based code:// code based on indiciesfor(autoi = 0; i != students.size(); ++i){cout<< students[i].name <<endl;}// code based on iterators using C++11 (VS2010, g++4.2)for(autoiter=students.begin();iter!=students.end(); ++iter){cout<< (*iter).name <<endl;}

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

16

Iterator Types

Everycontainer_type::iteratoris convertible to the correspondingcontainer_type::const_iteratorstudents.begin() returns an iterator, but we assign it to aconst_iteratorOpposite is not true! Why?

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

17

Iterator Operations

Containers not only expose their (specific) iterator types, but also actual iterators:students.begin(),students.end()begin(): ‘points’ to the first elementend(): ‘points’ to the element after the last oneIterators can becompared:iter!=students.end()Tests, whether both iterators refer to the same elementIterators can beincremented:++iterMake the iterator ‘point’ (refer) to the next element

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

18

Iterator Operations

Iterators can bedereferenced:*iterEvaluates to the element the iterator refers toIn order to access a member of the element the iterator refers to, we write:(*iter).name(why not:*iter.name?)Syntactic sugar, 100% equivalent:iter->name

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

19

Iterator Operations

Some iterators can get a number addedstudents.erase(students.begin() +i);Overloaded operator+, makes the iterator refer to the ‘i’ –s element after beginEquivalent to invoking ++ ‘i’ timesDefined only for iterators fromrandom accesscontainersvector, string are random access (indexing is possible)Will result in compilation error for sequential containers

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

20

ErasingElementsinPlace

Slow, but direct solution// second try: correct but potentially slowvector<student_info>extract_fails(vector<student_info>& students){vector<student_info> fail;autoi= 0;// invariant: elements [0,i) of students represent passing gradeswhile(i!=students.size()) {if(fail_grade(students[i])) {fail.push_back(students[i]};students.erase(students.begin() +i);}else++i;}returnfail;}

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

21

Erasing Elements in Place

Still slow, but without indexing:// version 3: iterators but no indexingvector<student_info>extract_fails(vector<student_info>& students){vector<student_info> fail;autoiter=students.begin();while(iter!=students.end()) {if(fail_grade(*iter)) {fail.push_back(*iter);iter=students.erase(iter);// watch out! Why?}else++iter;}returnfail;}

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

22

Iterator Invalidation

What happens to an iterator if the element it refers to is deleted?It is invalidatedCertain containers invalidate all iterators after the deleted element as well (vectors)For that reason erase() returns the next iterator:iter=students.erase(iter);

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

23

Same problem as Before

Why does this code fail:// this code will fail because of misguided optimizationautoiter=students.begin();autoend_iter=students.end();while(iter!=end_iter) {// ...}End iterator is invalidated as well when element is erased!

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

24

What’s the problem with vector

For small inputs, vector works just fine, larger inputs cause performance degradationVector is optimized for fast access to arbitrary elements and for fast addition to the endInserting or removing from the middle is slow.All elements after the inserted/removed element need to be moved in order to preserve fast random accessOur algorithm has quadratic performance characteristicsLet’s utilize a different data structure:Next lecture:The list type

19/2/2015, Lecture 8

CSC 1254, Spring 2015, Using Sequential Containers

25

0

Embed

Upload

Getting Started - cct.lsu.edu