16. vector Sequence Container
Khai b叩o
std::vector <type> v;
type l ki畛u d畛 li畛u c畛a ph畉n t畛 d畛 li畛u (int, float, v.v..)
Iterator
std::vector<type>::iterator iterVar;
tr動畛ng h畛p th担ng th動畛ng
std::vector<type>::const_iterator iterVar;
const_iterator kh担ng th畛 s畛a 畛i c叩c ph畉n t畛
std::vector<type>::reverse_iterator iterVar;
Visits elements in reverse order (end to beginning)
Use rbegin to get starting point
Use rend to get ending point
19. vector Sequence Container
C叩c hm thnh vi棚n c畛a vector
v.clear()
X坦a ton b畛 container
v.front(), v.back()
Tr畉 v畛 ph畉n t畛 畉u ti棚n v cu畛i c湛ng
v.[elementNumber] = value;
G叩n gi叩 tr畛 value cho m畛t ph畉n t畛
v.at[elementNumber] = value;
Nh動 tr棚n, nh動ng k竪m theo ki畛m tra ch畛 s畛 h畛p l畛
c坦 th畛 n辿m ngo畉i l畛 out_of_bounds
20. vector Sequence Container
ostream_iterator
std::ostream_iterator< type >
Name( outputStream, separator );
type: outputs values of a certain type
outputStream: iterator output location
separator: character separating outputs
Example
std::ostream_iterator< int > output( cout, " " );
std::copy( iterator1, iterator2, output );
Copies elements from iterator1 up to (not
including) iterator2 to output, an
ostream_iterator
20
21. 1 // Fig. 21.14: fig21_14.cpp
2 // Demonstrating standard library vector class template.
3 #include <iostream>
4
5 using std::cout;
6 using std::cin;
7 using std::endl;
8
9 #include <vector> // vector class-template definition
10
11 // prototype for function template printVector
12 template < class T >
13 void printVector( const std::vector< T > &integers2 );
14
15 int main()
16 {
17 const int SIZE = 6;
18 int array[ SIZE ] = { 1, 2, 3, 4, 5, 6 };
19
20 std::vector< int > integers;
21
22 cout << "The initial size of integers is: "
23 << integers.size()
24 << "nThe initial capacity of integers is: "
25 << integers.capacity();
26
21
T畉o m畛t vector ch畛a
c叩c gi叩 tr畛 int
G畛i c叩c hm thnh vi棚n.
22. 27 // function push_back is in every sequence collection
28 integers.push_back( 2 );
29 integers.push_back( 3 );
30 integers.push_back( 4 );
31
32 cout << "nThe size of integers is: " << integers.size()
33 << "nThe capacity of integers is: "
34 << integers.capacity();
35
36 cout << "nnOutput array using pointer notation: ";
37
38 for ( int *ptr = array; ptr != array + SIZE; ++ptr )
39 cout << *ptr << ' ';
40
41 cout << "nOutput vector using iterator notation: ";
42 printVector( integers );
43
44 cout << "nReversed contents of vector integers: ";
45
22
s畛 d畛ng push_back 畛
th棚m ph畉n t畛 vo cu畛i
vector
23. 46 std::vector< int >::reverse_iterator reverseIterator;
47
48 for ( reverseIterator = integers.rbegin();
49 reverseIterator!= integers.rend();
50 ++reverseIterator )
51 cout << *reverseIterator << ' ';
52
53 cout << endl;
54
55 return 0;
56
57 } // end main
58
59 // function template for outputting vector elements
60 template < class T >
61 void printVector( const std::vector< T > &integers2 )
62 {
63 std::vector< T >::const_iterator constIterator;
64
65 for ( constIterator = integers2.begin();
66 constIterator != integers2.end();
67 constIterator++ )
68 cout << *constIterator << ' ';
69
70 } // end function printVector
23
fig21_14.cpp
(3 of 3)
Duy畛t ng動畛c vector b畉ng
m畛t reverse_iterator.
Template function 畛
duy畛t vector theo
chi畛u ti畉n.
24. The initial size of v is: 0
The initial capacity of v is: 0
The size of v is: 3
The capacity of v is: 4
Contents of array a using pointer notation: 1 2 3 4 5 6
Contents of vector v using iterator notation: 2 3 4
Reversed contents of vector v: 4 3 2
24
fig21_14.cpp
output (1 of 1)
25. Container Adapter
Container adapter
stack, queue v priority_queue
Kh担ng ph畉i first class container, cho n棚n
Kh担ng h畛 tr畛 iterator
Kh担ng cung c畉p c畉u tr炭c d畛 li畛u
L畉p tr狸nh vi棚n c坦 th畛 ch畛n c叩ch ci 畉t (s畛 d畛ng c畉u
tr炭c d畛 li畛u no)
畛u cung c畉p c叩c hm thnh vi棚n push v pop b棚n
c畉nh c叩c hm thnh vi棚n kh叩c.
26. stack Adapter
stack
Header <stack>
ch竪n v x坦a t畉i m畛t 畉u
C畉u tr炭c Last-in, first-out (LIFO)
C坦 th畛 ch畛n ci 畉t b畉ng vector, list, ho畉c deque (m畉c
畛nh)
Khai b叩o
stack<type, vector<type> > myStack;
stack<type, list<type> > myOtherStack;
stack<type> anotherStack; // default deque
ch畛n ci 畉t l vector, list hay deque kh担ng lm thay 畛i
hnh vi, ch畛 畉nh h動畛ng t畛i hi畛u qu畉 (ci b畉ng deque v
vector l nhanh nh畉t)
27. 1 // Fig. 21.23: fig21_23.cpp
2 // Standard library adapter stack test program.
3 #include <iostream>
4
5 using std::cout;
6 using std::endl;
7
8 #include <stack> // stack adapter definition
9 #include <vector> // vector class-template definition
10 #include <list> // list class-template definition
11
12 // popElements function-template prototype
13 template< class T >
14 void popElements( T &stackRef );
15
16 int main()
17 {
18 // stack with default underlying deque
19 std::stack< int > intDequeStack;
20
21 // stack with underlying vector
22 std::stack< int, std::vector< int > > intVectorStack;
23
24 // stack with underlying list
25 std::stack< int, std::list< int > > intListStack;
26
27
fig21_23.cpp
(1 of 3)
T畉o stack b畉ng nhi畛u
ki畛u ci 畉t.
28. 27 // push the values 0-9 onto each stack
28 for ( int i = 0; i < 10; ++i ) {
29 intDequeStack.push( i );
30 intVectorStack.push( i );
31 intListStack.push( i );
32
33 } // end for
34
35 // display and remove elements from each stack
36 cout << "Popping from intDequeStack: ";
37 popElements( intDequeStack );
38 cout << "nPopping from intVectorStack: ";
39 popElements( intVectorStack );
40 cout << "nPopping from intListStack: ";
41 popElements( intListStack );
42
43 cout << endl;
44
45 return 0;
46
47 } // end main
48
28
fig21_23.cpp
(2 of 3)
s畛 d畛ng hm thnh vi棚n push.
29. 49 // pop elements from stack object to which stackRef refers
50 template< class T >
51 void popElements( T &stackRef )
52 {
53 while ( !stackRef.empty() ) {
54 cout << stackRef.top() << ' '; // view top element
55 stackRef.pop(); // remove top element
56
57 } // end while
58
59 } // end function popElements
29
fig21_23.cpp
(3 of 3)
fig21_23.cpp
output (1 of 1)
Popping from intDequeStack: 9 8 7 6 5 4 3 2 1 0
Popping from intVectorStack: 9 8 7 6 5 4 3 2 1 0
Popping from intListStack: 9 8 7 6 5 4 3 2 1 0
37. 1 // Fig. 21.31: fig21_31.cpp
2 // Standard library search and sort algorithms.
3 #include <iostream>
4
5 using std::cout;
6 using std::endl;
7
8 #include <algorithm> // algorithm definitions
9 #include <vector> // vector class-template definition
10
11 bool greater10( int value ); // prototype
12
13 int main()
14 {
15 const int SIZE = 10;
16 int a[ SIZE ] = { 10, 2, 17, 5, 16, 8, 13, 11, 20, 7 };
17
18 std::vector< int > v( a, a + SIZE );
19 std::ostream_iterator< int > output( cout, " " );
20
21 cout << "Vector v contains: ";
22 std::copy( v.begin(), v.end(), output );
23
24 // locate first occurrence of 16 in v
25 std::vector< int >::iterator location;
26 location = std::find( v.begin(), v.end(), 16 );
37
fig21_31.cpp
(1 of 4)
38. 27
28 if ( location != v.end() )
29 cout << "nnFound 16 at location "
30 << ( location - v.begin() );
31 else
32 cout << "nn16 not found";
33
34 // locate first occurrence of 100 in v
35 location = std::find( v.begin(), v.end(), 100 );
36
37 if ( location != v.end() )
38 cout << "nFound 100 at location "
39 << ( location - v.begin() );
40 else
41 cout << "n100 not found";
42
43 // locate first occurrence of value greater than 10 in v
44 location = std::find_if( v.begin(), v.end(), greater10 );
45
46 if ( location != v.end() )
47 cout << "nnThe first value greater than 10 is "
48 << *location << "nfound at location "
49 << ( location - v.begin() );
50 else
51 cout << "nnNo values greater than 10 were found";
52
38
fig21_31.cpp
(2 of 4)
39. 53 // sort elements of v
54 std::sort( v.begin(), v.end() );
55
56 cout << "nnVector v after sort: ";
57 std::copy( v.begin(), v.end(), output );
58
59 // use binary_search to locate 13 in v
60 if ( std::binary_search( v.begin(), v.end(), 13 ) )
61 cout << "nn13 was found in v";
62 else
63 cout << "nn13 was not found in v";
64
65 // use binary_search to locate 100 in v
66 if ( std::binary_search( v.begin(), v.end(), 100 ) )
67 cout << "n100 was found in v";
68 else
69 cout << "n100 was not found in v";
70
71 cout << endl;
72
73 return 0;
74
75 } // end main
76
39
fig21_31.cpp
(3 of 4)
40. 77 // determine whether argument is greater than 10
78 bool greater10( int value )
79 {
80 return value > 10;
81
82 } // end function greater10
40
fig21_31.cpp
(4 of 4)
fig21_31.cpp
output (1 of 1)
Vector v contains: 10 2 17 5 16 8 13 11 20 7
Found 16 at location 4
100 not found
The first value greater than 10 is 17
found at location 2
Vector v after sort: 2 5 7 8 10 11 13 16 17 20
13 was found in v
100 was not found in v
41. Function Object functor
(<functional>)
C叩c畛it動畛ngc坦th畛g畛inh動hmb畉ngto叩nt畛()
STL function objects Type
divides< T > arithmetic
equal_to< T > relational
greater< T > relational
greater_equal< T > relational
less< T > relational
less_equal< T > relational
logical_and< T > logical
logical_not< T > logical
logical_or< T > logical
minus< T > arithmetic
modulus< T > arithmetic
negate< T > arithmetic
not_equal_to< T > relational
plus< T > arithmetic
multiplies< T > arithmetic
42. 1 // Fig. 21.42: fig21_42.cpp
2 // Demonstrating function objects.
3 #include <iostream>
4
5 using std::cout;
6 using std::endl;
7
8 #include <vector> // vector class-template definition
9 #include <algorithm> // copy algorithm
10 #include <numeric> // accumulate algorithm
11 #include <functional> // binary_function definition
12
13 // binary function adds square of its second argument and
14 // running total in its first argument, then returns sum
15 int sumSquares( int total, int value )
16 {
17 return total + value * value;
18
19 } // end function sumSquares
20
42
fig21_42.cpp
(1 of 4)
T畉o m畛t hm 畛 d湛ng
v畛i accumulate.
43. 21 // binary function class template defines overloaded operator()
22 // that adds suare of its second argument and running total in
23 // its first argument, then returns sum
24 template< class T >
25 class SumSquaresClass : public std::binary_function< T, T, T > {
26
27 public:
28
29 // add square of value to total and return result
30 const T operator()( const T &total, const T &value )
31 {
32 return total + value * value;
33
34 } // end function operator()
35
36 }; // end class SumSquaresClass
37
43
fig21_42.cpp
(2 of 4)T畉o m畛t function object
(n坦 c嘆n c坦 th畛 坦ng g坦i
d畛 li畛u).
Overload operator().
44. 38 int main()
39 {
40 const int SIZE = 10;
41 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
42
43 std::vector< int > integers( array, array + SIZE );
44
45 std::ostream_iterator< int > output( cout, " " );
46
47 int result = 0;
48
49 cout << "vector v contains:n";
50 std::copy( integers.begin(), integers.end(), output );
51
52 // calculate sum of squares of elements of vector integers
53 // using binary function sumSquares
54 result = std::accumulate( integers.begin(), integers.end(),
55 0, sumSquares );
56
57 cout << "nnSum of squares of elements in integers using "
58 << "binarynfunction sumSquares: " << result;
59
44
fig21_42.cpp
(3 of 4)
畉u ti棚n, accumulate
truy畛n 0 v ph畉n t畛
th畛 nh畉t l畉n l動畛t lm
c叩c tham s畛. Sau 坦, n坦
d湛ng k畉tqu畉 tr畉 v畛 lm
tham s畛 th畛 nh畉t, v l畉p
qua c叩c ph畉n t畛 c嘆n l畉i.
45. 60 // calculate sum of squares of elements of vector integers
61 // using binary-function object
62 result = std::accumulate( integers.begin(), integers.end(),
63 0, SumSquaresClass< int >() );
64
65 cout << "nnSum of squares of elements in integers using "
66 << "binarynfunction object of type "
67 << "SumSquaresClass< int >: " << result << endl;
68
69 return 0;
70
71 } // end main
45
fig21_42.cpp
(4 of 4)
fig21_42.cpp
output (1 of 1)
vector v contains:
1 2 3 4 5 6 7 8 9 10
Sum of squares of elements in integers using binary
function sumSquares: 385
Sum of squares of elements in integers using binary
function object of type SumSquaresClass< int >: 385
d湛ng accumulate v畛i
m畛t function object.
![C叩c ph辿p to叩n 畛i v畛i Iterator
Input iterator
++ , =*p , -> , == , !=
Output iterator
++ , *p= , p = p1
Forward iterator
K畉t h畛p c叩c to叩n t畛 c畛a input v output iterator
Bidirectional iterator
c叩c to叩n t畛 cho forward, v --
Random iterator
c叩c to叩n t畛 cho bidirectional, v
+ , +=, -, -=, >, >=, <, <=,[]](https://image.slidesharecdn.com/7-stlc-140717044336-phpapp02/85/7-stl-c-12-320.jpg)
![vector Sequence Container
vector
<vector>
c畉u tr炭c d畛 li畛u v畛i c叩c v湛ng nh畛 li棚n ti畉p
truy nh畉p c叩c ph畉n t畛 b畉ng to叩n t畛 [ ]
s畛 d畛ng khi d畛 li畛u c畉n 動畛c s畉p x畉p v truy nh畉p
d畛 dng
C董ch畉 ho畉t 畛ng khi h畉t b畛 nh畛
c畉p ph叩t m畛t v湛ng nh畛 li棚n l畛c l畛n h董n
t畛 sao ch辿p ra v湛ng nh畛 m畛i
tr畉 l畉i v湛ng nh畛 c滴
s畛 d畛ng randomaccess iterator](https://image.slidesharecdn.com/7-stlc-140717044336-phpapp02/85/7-stl-c-15-320.jpg)
![vector Sequence Container
C叩c hm thnh vi棚n c畛a vector
v.clear()
X坦a ton b畛 container
v.front(), v.back()
Tr畉 v畛 ph畉n t畛 畉u ti棚n v cu畛i c湛ng
v.[elementNumber] = value;
G叩n gi叩 tr畛 value cho m畛t ph畉n t畛
v.at[elementNumber] = value;
Nh動 tr棚n, nh動ng k竪m theo ki畛m tra ch畛 s畛 h畛p l畛
c坦 th畛 n辿m ngo畉i l畛 out_of_bounds](https://image.slidesharecdn.com/7-stlc-140717044336-phpapp02/85/7-stl-c-19-320.jpg)
![1 // Fig. 21.14: fig21_14.cpp
2 // Demonstrating standard library vector class template.
3 #include <iostream>
4
5 using std::cout;
6 using std::cin;
7 using std::endl;
8
9 #include <vector> // vector class-template definition
10
11 // prototype for function template printVector
12 template < class T >
13 void printVector( const std::vector< T > &integers2 );
14
15 int main()
16 {
17 const int SIZE = 6;
18 int array[ SIZE ] = { 1, 2, 3, 4, 5, 6 };
19
20 std::vector< int > integers;
21
22 cout << "The initial size of integers is: "
23 << integers.size()
24 << "nThe initial capacity of integers is: "
25 << integers.capacity();
26
21
T畉o m畛t vector ch畛a
c叩c gi叩 tr畛 int
G畛i c叩c hm thnh vi棚n.](https://image.slidesharecdn.com/7-stlc-140717044336-phpapp02/85/7-stl-c-21-320.jpg)
![1 // Fig. 21.31: fig21_31.cpp
2 // Standard library search and sort algorithms.
3 #include <iostream>
4
5 using std::cout;
6 using std::endl;
7
8 #include <algorithm> // algorithm definitions
9 #include <vector> // vector class-template definition
10
11 bool greater10( int value ); // prototype
12
13 int main()
14 {
15 const int SIZE = 10;
16 int a[ SIZE ] = { 10, 2, 17, 5, 16, 8, 13, 11, 20, 7 };
17
18 std::vector< int > v( a, a + SIZE );
19 std::ostream_iterator< int > output( cout, " " );
20
21 cout << "Vector v contains: ";
22 std::copy( v.begin(), v.end(), output );
23
24 // locate first occurrence of 16 in v
25 std::vector< int >::iterator location;
26 location = std::find( v.begin(), v.end(), 16 );
37
fig21_31.cpp
(1 of 4)](https://image.slidesharecdn.com/7-stlc-140717044336-phpapp02/85/7-stl-c-37-320.jpg)
![38 int main()
39 {
40 const int SIZE = 10;
41 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
42
43 std::vector< int > integers( array, array + SIZE );
44
45 std::ostream_iterator< int > output( cout, " " );
46
47 int result = 0;
48
49 cout << "vector v contains:n";
50 std::copy( integers.begin(), integers.end(), output );
51
52 // calculate sum of squares of elements of vector integers
53 // using binary function sumSquares
54 result = std::accumulate( integers.begin(), integers.end(),
55 0, sumSquares );
56
57 cout << "nnSum of squares of elements in integers using "
58 << "binarynfunction sumSquares: " << result;
59
44
fig21_42.cpp
(3 of 4)
畉u ti棚n, accumulate
truy畛n 0 v ph畉n t畛
th畛 nh畉t l畉n l動畛t lm
c叩c tham s畛. Sau 坦, n坦
d湛ng k畉tqu畉 tr畉 v畛 lm
tham s畛 th畛 nh畉t, v l畉p
qua c叩c ph畉n t畛 c嘆n l畉i.](https://image.slidesharecdn.com/7-stlc-140717044336-phpapp02/85/7-stl-c-44-320.jpg)
