Standard Template Library (STL)
Introduction
container: to manage collection of objects of certain type. e.g dequeue, lists, vector, map
algorithm: provides ways to perform init, sort, search, transform container's content
iterators: to step through containers
Containers
Containers provide some common api: empty(), size(), clear()-remove all elems and make size=0, v1.swap(v2): v1 becomes empty, v2 gets v1 elems, copy constructor vector<int> v2(v1).
One way to categorize containers:
Array based: vector, dequeue. invalidates native, iterator and iterator pointer
e.g.
vector<int> v={1,2,3};
int *p=&v[1]; //p points to 2
v.insert(v.begin(), 0); //p may print 2 or any other random number, undefined behaviour.
Everytime you move/insert something to vector, previous pointer might get invalid. Stop using pointer after insertion to array based container.
Node based: list, associative containers, unordered containers.
previously assigned pointer remains even after insert/add as long as member it points is not deleted.
a) Vector: dynamically allocated contiguous array in memory. int *ptr=&v[0]; p[2]=10;
vector<int> v; v.push_back(10);
v[2] //no bounds check. v.ar(2) throw range_error exception of out of range.
+ O(1) add/remove at end, O(n) add/remove in middle/start, O(n) search
b) Dequeue: can grow both at end and start
dequeue<int> deq={1,2,3};
deq.push_front(0); deq.push_back(4);
deq[1]
+ fast add/remove at begin/end, O(n) add/remove in middle, O(n) search
c) List: doubly LL.
+ fast add/remove at any place, O(n) search
list<int> l={5,2,9};
l.push_back(6); l.push_front(4); //list={4,5,2,9,6}
list<int>::iterator it=find(l.begin(), l.end(), 2); //find an item of 2, it points to 2.
l.insert(it, 8); //list={4,5,8,2,9,6}
it++; //it points to 9
l.erase(it); //list={4,5,8,2,6}
+ O(1) add/remove at any place, O(n) search, no random access operator[].
list1.splice(it, list2, it_a, it_b); //O(1) big advantage.
d) Forward list: only traverse from start to end. singly LL.
e) Array:
array<<int, 3> a={1,2,3}; //size can not be changed.
array<<int, 4> b={1,2,3, 4}; //size can not be changed.
a.begin(), a.end(), a.size(), a.swap()
function can take fixed size array (??).
sequence container doe snot have find().
II. Associative Containers(binary tree): set/multiset, map/multimap
always sorted (default criteria <), No push_back, push_front().
a) Set/Multiset: no duplicates.
set<int> s; s.insert(3); s.insert(1); s.insert(7); //O(log n)
set<int>::iterator it;
it=s.find(7); //find item 7, O(log n)
pair<set<int>::iterator, bool> ret;
ret=set.insert(3); //insert fails,
if(ret.second==false) it=ret.first; //it points to element 3.
s.insert(it, 9); //1,3,7,9, it points to 3.
//Why 9 got inserted at end? Position is not decided by iterator, remember always sorted??
s.erase(it); //1,7,9
s.erase(7); //1,9
Multiset allows duplicates, value of elements can not be modified.
multiset<int> ms;
*it=10; //wrong, it is read only.
+ fast search O(log n), slow traverse wrt vector, dequeue, no random access, no [] operator.
What if you wish to sort based on key? Solution map/multimap.
b) Map/Multimap:
each element is pair of key/val. keys can not be changed.
Map does not allow duplicate.
map<char, int> m;
m.insert( pair<char,int>('a', 10));
m.insert(make_pair('b', 20);
map<char,int>::iterator it=m.begin();
m.insert(it, pair<char, int> ('c', 30));
it=m.find('c'); //O(log n)
for(it=m.begin();it<m.end();it++) cout<<(*it).first<<"=>"<<(*it).second>>endl; //print map
Multimap
allows duplicate keys, keys unmodifiable. (*it).first='k'; //wrong
Why, because type of (*it) is pair<const char, int>. const char can not be changed.
III. Unordered Containers(hash table): unordered set/multiset, unordered map/multimap.
If fast and effective hash function can fast member in O(1). can be fastest container.
unordered set/multiset: element value can not be changed.
unordered map/multimap: key can not be changed.
a) Unordered set/multiset:
unordered_set<string> s={"red", "green", "blue"}
unordered_set<string>::const_iterator it=s.find("green"); //O(1);
if(it!=s.end()) cout<<*it<<endl;
s.insert("yellow");
vector<string> v={"pink", "purp"};
s.insert(v.begin(), v.end()); //add all items of vector into set
//Hash specific
s.load_factor(): ratio of total elements/total buckets
string k="red"; cout<<"red is in bucket #"<<s.bucket(k)<<endl;
cout<<"total bucket"<<s.bucket_count()<<endl;
b) unordered multiset allows duplicate elements
c) unordered map: unordered set of pairs
d) unordered multimap: unordered map that allows duplicate keys
Hash table gives amortized constant time search, but performance can degrade due to hash collision (when items are inserted into single/less buckets).
Associative Array: using map/unordered map.
Const search unordered_map while map has O(log n).
Unordered map can degrade to linear search while map guarantees O(log n) search.
Can not use multimap/unordered multimap as they dont have unique key and [] operator.
unordered_map<char, string> day={ {'S', "Sunday", {'M', "Monday"} };
vector<int> v={1,2,3};
v[5]=5; //compiler error
day['W']="Wednesday"; //same as below
day.insert(make_pair('F', "Friday"));
day.insert(make_pair('M', "Monday")); //fail to change, its unordered_map.
day['M']="MONDAY"; //works fine
insert() can not modify existing functions, however [] can be used to modify existing member.
[] provides write access to container.
Notes:
//way to print element of map.
void fun(const unordered_map<char, string>& m){
//m['S']="Sunday"
//cout << m['S']<<endl
auto it=m.find('S');
if(it!=m.end()){cout<<*it<<endl;}
}
Container Adapter
Implemented using fundamental container classes, provides interface for specific operation.
stack: LIFO. push(), pop(), top().
queue: FIFO. push(), pop(), front(), back().
priority queue: first element has highest priority. push(), pop(), top().
C++ Header: vector, dequeue, list, set, map, unordered_set, unordered_map, iterator, algorithm, numeric, functional
Iterator
Iterator Types: iterator, const_iterator.
Every container has iterator and const_iterator.
list<int<::iterator itr;
list<int>::const_iterator const_itr;
e.g. for(citr=l.begin(); citr!=l.end(); citr++){ cout<<*citr<<endl; } // *ctr=3: error
foreach(l.cbegin();l.cend(); func) //Only C++11
Iterator Function: advance, distance
advance(itr,5); //take itr 5 forward. For random access itrator: itr+=5; convenient for other iterators.
distance(itr1, it2); //calculate distance between itr1 and itr2
Random access iterator: For vector, dequeue, arrays
vector<int> itr;
itr=itr+5; itr=itr-5; //advance/recede by 5
if(itr2>itr1) //ok
++itr; --itr; //pre-increment faster than post form, because does not need to return old value
Bidirectional Iterator: For list, set/multiset, map/multimap.
Can not compare, can not add/dec numbers
list<int> itr; ++itr; --itr;
Forward Iterator: forward_list<int> itr; ++itr;
- Input Iterator: Read and process values while iterating forward. Can reference its value but can not write to it. int x=*itr;
- Output Iterator: Output values while iterating forward. Can write values into it. *itr=100;
Input and Output iterators can only move forward.
Unordered Containers provide at least forward iterators and have option to provide bidirectional iterator.
Iterator Adapter:
Predefined iterator doing more that just iterating.
insert iterator: insert_iterator, back_insert_iterator, front_insert_iterator.
vector<int> v1={10,11,12}; vector<int> v2={5,6,14,15};
vector<int>iterator it=find(v2.begin(), v2.end(), 16);
insert_iterator<vector<int>> i_itr(v2, it);
copy(v1.begin(), v2.end(); i_itr); //v2={5,6,10,11,14,15};
stream iterator:
vector<string> v;
copy(istream_iterator<string>(cin), istream_iterator<string>(), back_insert(v)); //copiy everything fron standard input and insert to vector v.
copy(v.begin(), v.end(), ostream_iterator<string>(cout, " "); //copy everything in v is printed to standard out, each element space separated.
//combine above as:
copy(istream_iterator<string>(cin), istream_iterator<string>(cout, " "));
reverse iterator: Provided for every container
vector<int> v={1,2,3,4};
reverse_iterator<vector<int>::iterator> rit;
for(rit=v.begin(); rit!=v.end(); rit++) cout<<*rit;endl; //outputs: 4 3 21
move (C++11) iterator
Algorithm: Algo always process ranges in half open way [begin, end)
vector<int> v={2,4,5,6,1,3,7};
vector<int>::iterator it=min_element(v.begin, v.end()); //it points at 1
sort(v.begin(), it); //v={1,2,3,4,5,6,7}
reverse(it, v.end(); //v={7,3,`,6,5,4,2}
Safety Issue:
vector<int> v(5);
copy(it, v.end(), //src
v.begin()); //dst
//copy has src range, dst range, v needs to have at least src number of (5) element space
Not safe: as undefined when dst does not have min (5 here) elements spce.
Solution:
vector<int> v;
copy(it, v.end(), back_inserter(vec3)); //safe but not efficient as inserts instead of overwrite
v.insert(v.end(), it, v.end()); //efficient and safe
bool isOdd(int i){ return i%2;}; //Algo works well with user functions
vector<int> v={2,4,5,7};
vector<int>::iterator it=find_if(v.begin(), v.end(), isOdd); //itr points to 5
int arr[4]={2,4,5,7};
sort(arr, arr+4); //Algo works well with C++ arrays.
here, pointer can be thought as iterator.
Functors (Function Objects)
class A{ public: void operator()(string s){cout <<"functor X caled with << s<<endl; }; //A is class, but behaves like function. remember, its not overloading, as void is given as return type
Call: A a; a("Hello");
a is instance of class A, but can be called as if its a function.
+smart function which can remember state, can have its own type.
Algorithm
Non-modifying:
Modifying
Vector Container
like arrays, but handles storage requirements when it grows [dynamic arrays?]
vector<int> v; vector<int>::iterator i=v.begin();
v.size(); v.push_back(value); v[i]:value at index i
while(i<v.end()){ value of v at index i: *i; i++;}
resize(): v.resize(20); If require less elements, extra deleted, else added size and copies old elements. newly added elements are 0.
push_back() after resize() will add elements after resized size, not into it.
size() unsigned.
Note: Avoid: v.size()>=0 : Because all containers can not report size in O(1). Use: v.empty() to check empty vector.
clear(): make vector to contain zero elements. [does not make elements 0].
Initialize vector:
vector<int> v1;
vector<int> v2=v1;
vector<int> v3(v1);
vector<int> data(100); //data has 100 elements initialized to 0.
vector<string> name(20, "unknown"); //
vector< vector<int> > matrix_2d(N, vector<int>(M, -1)); //create NxM matrix, initialised to -1.
Insert/Erase at position: use iterators:
Introduction
container: to manage collection of objects of certain type. e.g dequeue, lists, vector, map
algorithm: provides ways to perform init, sort, search, transform container's content
iterators: to step through containers
Containers
Containers provide some common api: empty(), size(), clear()-remove all elems and make size=0, v1.swap(v2): v1 becomes empty, v2 gets v1 elems, copy constructor vector<int> v2(v1).
One way to categorize containers:
Array based: vector, dequeue. invalidates native, iterator and iterator pointer
e.g.
vector<int> v={1,2,3};
int *p=&v[1]; //p points to 2
v.insert(v.begin(), 0); //p may print 2 or any other random number, undefined behaviour.
Everytime you move/insert something to vector, previous pointer might get invalid. Stop using pointer after insertion to array based container.
Node based: list, associative containers, unordered containers.
previously assigned pointer remains even after insert/add as long as member it points is not deleted.
Another way to categorize containers:
I. Sequence Container (arr/linked list): vector, dequeue, list, forward list, arraya) Vector: dynamically allocated contiguous array in memory. int *ptr=&v[0]; p[2]=10;
vector<int> v; v.push_back(10);
v[2] //no bounds check. v.ar(2) throw range_error exception of out of range.
+ O(1) add/remove at end, O(n) add/remove in middle/start, O(n) search
b) Dequeue: can grow both at end and start
dequeue<int> deq={1,2,3};
deq.push_front(0); deq.push_back(4);
deq[1]
+ fast add/remove at begin/end, O(n) add/remove in middle, O(n) search
c) List: doubly LL.
+ fast add/remove at any place, O(n) search
list<int> l={5,2,9};
l.push_back(6); l.push_front(4); //list={4,5,2,9,6}
list<int>::iterator it=find(l.begin(), l.end(), 2); //find an item of 2, it points to 2.
l.insert(it, 8); //list={4,5,8,2,9,6}
it++; //it points to 9
l.erase(it); //list={4,5,8,2,6}
+ O(1) add/remove at any place, O(n) search, no random access operator[].
list1.splice(it, list2, it_a, it_b); //O(1) big advantage.
d) Forward list: only traverse from start to end. singly LL.
e) Array:
array<<int, 3> a={1,2,3}; //size can not be changed.
array<<int, 4> b={1,2,3, 4}; //size can not be changed.
a.begin(), a.end(), a.size(), a.swap()
function can take fixed size array (??).
sequence container doe snot have find().
II. Associative Containers(binary tree): set/multiset, map/multimap
always sorted (default criteria <), No push_back, push_front().
a) Set/Multiset: no duplicates.
set<int> s; s.insert(3); s.insert(1); s.insert(7); //O(log n)
set<int>::iterator it;
it=s.find(7); //find item 7, O(log n)
pair<set<int>::iterator, bool> ret;
ret=set.insert(3); //insert fails,
if(ret.second==false) it=ret.first; //it points to element 3.
s.insert(it, 9); //1,3,7,9, it points to 3.
//Why 9 got inserted at end? Position is not decided by iterator, remember always sorted??
s.erase(it); //1,7,9
s.erase(7); //1,9
Multiset allows duplicates, value of elements can not be modified.
multiset<int> ms;
*it=10; //wrong, it is read only.
+ fast search O(log n), slow traverse wrt vector, dequeue, no random access, no [] operator.
What if you wish to sort based on key? Solution map/multimap.
b) Map/Multimap:
each element is pair of key/val. keys can not be changed.
Map does not allow duplicate.
map<char, int> m;
m.insert( pair<char,int>('a', 10));
m.insert(make_pair('b', 20);
map<char,int>::iterator it=m.begin();
m.insert(it, pair<char, int> ('c', 30));
it=m.find('c'); //O(log n)
for(it=m.begin();it<m.end();it++) cout<<(*it).first<<"=>"<<(*it).second>>endl; //print map
Multimap
allows duplicate keys, keys unmodifiable. (*it).first='k'; //wrong
Why, because type of (*it) is pair<const char, int>. const char can not be changed.
III. Unordered Containers(hash table): unordered set/multiset, unordered map/multimap.
If fast and effective hash function can fast member in O(1). can be fastest container.
unordered set/multiset: element value can not be changed.
unordered map/multimap: key can not be changed.
a) Unordered set/multiset:
unordered_set<string> s={"red", "green", "blue"}
unordered_set<string>::const_iterator it=s.find("green"); //O(1);
if(it!=s.end()) cout<<*it<<endl;
s.insert("yellow");
vector<string> v={"pink", "purp"};
s.insert(v.begin(), v.end()); //add all items of vector into set
//Hash specific
s.load_factor(): ratio of total elements/total buckets
string k="red"; cout<<"red is in bucket #"<<s.bucket(k)<<endl;
cout<<"total bucket"<<s.bucket_count()<<endl;
b) unordered multiset allows duplicate elements
c) unordered map: unordered set of pairs
d) unordered multimap: unordered map that allows duplicate keys
Hash table gives amortized constant time search, but performance can degrade due to hash collision (when items are inserted into single/less buckets).
Associative Array: using map/unordered map.
Const search unordered_map while map has O(log n).
Unordered map can degrade to linear search while map guarantees O(log n) search.
Can not use multimap/unordered multimap as they dont have unique key and [] operator.
unordered_map<char, string> day={ {'S', "Sunday", {'M', "Monday"} };
vector<int> v={1,2,3};
v[5]=5; //compiler error
day['W']="Wednesday"; //same as below
day.insert(make_pair('F', "Friday"));
day.insert(make_pair('M', "Monday")); //fail to change, its unordered_map.
day['M']="MONDAY"; //works fine
insert() can not modify existing functions, however [] can be used to modify existing member.
[] provides write access to container.
Notes:
//way to print element of map.
void fun(const unordered_map<char, string>& m){
//m['S']="Sunday"
//cout << m['S']<<endl
auto it=m.find('S');
if(it!=m.end()){cout<<*it<<endl;}
}
Container Adapter
Implemented using fundamental container classes, provides interface for specific operation.
stack: LIFO. push(), pop(), top().
queue: FIFO. push(), pop(), front(), back().
priority queue: first element has highest priority. push(), pop(), top().
C++ Header: vector, dequeue, list, set, map, unordered_set, unordered_map, iterator, algorithm, numeric, functional
Iterator
Iterator Types: iterator, const_iterator.
Every container has iterator and const_iterator.
list<int<::iterator itr;
list<int>::const_iterator const_itr;
e.g. for(citr=l.begin(); citr!=l.end(); citr++){ cout<<*citr<<endl; } // *ctr=3: error
foreach(l.cbegin();l.cend(); func) //Only C++11
Iterator Function: advance, distance
advance(itr,5); //take itr 5 forward. For random access itrator: itr+=5; convenient for other iterators.
distance(itr1, it2); //calculate distance between itr1 and itr2
Random access iterator: For vector, dequeue, arrays
vector<int> itr;
itr=itr+5; itr=itr-5; //advance/recede by 5
if(itr2>itr1) //ok
++itr; --itr; //pre-increment faster than post form, because does not need to return old value
Bidirectional Iterator: For list, set/multiset, map/multimap.
Can not compare, can not add/dec numbers
list<int> itr; ++itr; --itr;
Forward Iterator: forward_list<int> itr; ++itr;
- Input Iterator: Read and process values while iterating forward. Can reference its value but can not write to it. int x=*itr;
- Output Iterator: Output values while iterating forward. Can write values into it. *itr=100;
Input and Output iterators can only move forward.
Unordered Containers provide at least forward iterators and have option to provide bidirectional iterator.
Iterator Adapter:
Predefined iterator doing more that just iterating.
insert iterator: insert_iterator, back_insert_iterator, front_insert_iterator.
vector<int> v1={10,11,12}; vector<int> v2={5,6,14,15};
vector<int>iterator it=find(v2.begin(), v2.end(), 16);
insert_iterator<vector<int>> i_itr(v2, it);
copy(v1.begin(), v2.end(); i_itr); //v2={5,6,10,11,14,15};
stream iterator:
vector<string> v;
copy(istream_iterator<string>(cin), istream_iterator<string>(), back_insert(v)); //copiy everything fron standard input and insert to vector v.
copy(v.begin(), v.end(), ostream_iterator<string>(cout, " "); //copy everything in v is printed to standard out, each element space separated.
//combine above as:
copy(istream_iterator<string>(cin), istream_iterator<string>(cout, " "));
reverse iterator: Provided for every container
vector<int> v={1,2,3,4};
reverse_iterator<vector<int>::iterator> rit;
for(rit=v.begin(); rit!=v.end(); rit++) cout<<*rit;endl; //outputs: 4 3 21
move (C++11) iterator
Algorithm: Algo always process ranges in half open way [begin, end)
vector<int> v={2,4,5,6,1,3,7};
vector<int>::iterator it=min_element(v.begin, v.end()); //it points at 1
sort(v.begin(), it); //v={1,2,3,4,5,6,7}
reverse(it, v.end(); //v={7,3,`,6,5,4,2}
Safety Issue:
vector<int> v(5);
copy(it, v.end(), //src
v.begin()); //dst
//copy has src range, dst range, v needs to have at least src number of (5) element space
Not safe: as undefined when dst does not have min (5 here) elements spce.
Solution:
vector<int> v;
copy(it, v.end(), back_inserter(vec3)); //safe but not efficient as inserts instead of overwrite
v.insert(v.end(), it, v.end()); //efficient and safe
bool isOdd(int i){ return i%2;}; //Algo works well with user functions
vector<int> v={2,4,5,7};
vector<int>::iterator it=find_if(v.begin(), v.end(), isOdd); //itr points to 5
int arr[4]={2,4,5,7};
sort(arr, arr+4); //Algo works well with C++ arrays.
here, pointer can be thought as iterator.
Functors (Function Objects)
class A{ public: void operator()(string s){cout <<"functor X caled with << s<<endl; }; //A is class, but behaves like function. remember, its not overloading, as void is given as return type
Call: A a; a("Hello");
a is instance of class A, but can be called as if its a function.
+smart function which can remember state, can have its own type.
Algorithm
Non-modifying:
Modifying
Vector Container
like arrays, but handles storage requirements when it grows [dynamic arrays?]
vector<int> v; vector<int>::iterator i=v.begin();
v.size(); v.push_back(value); v[i]:value at index i
while(i<v.end()){ value of v at index i: *i; i++;}
resize(): v.resize(20); If require less elements, extra deleted, else added size and copies old elements. newly added elements are 0.
push_back() after resize() will add elements after resized size, not into it.
size() unsigned.
Note: Avoid: v.size()>=0 : Because all containers can not report size in O(1). Use: v.empty() to check empty vector.
clear(): make vector to contain zero elements. [does not make elements 0].
Initialize vector:
vector<int> v1;
vector<int> v2=v1;
vector<int> v3(v1);
vector<int> data(100); //data has 100 elements initialized to 0.
vector<string> name(20, "unknown"); //
vector< vector<int> > matrix_2d(N, vector<int>(M, -1)); //create NxM matrix, initialised to -1.
Insert/Erase at position: use iterators:
No comments:
Post a Comment