复习C++基础知识-----“我的第一本C++”读书笔记3
算法(algorithm)+容器(container)+迭代器(iterator) = STL
容器(container)
主要含有deque(双端队列)、queue(队列)、stack(堆栈容器)、vector(动态数组容器)、map multimap unordered_map unorderd_multimap(映射容器 由{键, 值}对组成)、set multiset unordered_set
unordered_multiset(集合容器)、algorithm(通用算法, 包括比较、交换、查找、排序等)、functional(模板类)、string(字符串类)、regex(正则表达式)、memory(定义了跟内存操作相关的组件, 例如智能指针等)
vector相对于数组来说,他可以合理利用空间,让程序有更大的可扩展性
函数模板
1)当编译器发现一个函数模板的调用后,将根据实参的实际数据类型来确认是否匹配函数模板中对应的形参,然后生成一个重载函数。根据参数类型的不同,一个函数模板可以随时变成各种不同的重载
函数,从而实集类型的处理。
2)比如max函数---------------------能够比较int、float、string
temple<typename 标识符>
返回值类型 函数名(形参表)
{
//函数体
}
类模板
1)类模板的声明
temple<typename 标识符>
class 类名
{
//类的定义
}
2)定义一个用于比较两个数的类模板compare
#include "stdafx.h"
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
template <typename T>
T compare( const T a, const T b)
{
return ( a > b ? a : b );
}
template <>
string compare( const string a, const string b)
{
return ( a.size() > b.size() ? a : b );
}
int main()
{
const int ii = 10;
const int ij = 20;
cout << "return the max value is : " << compare<int>( ii, ij ) << endl;
const float fi = 0.7f;
const float fj = 1.2f;
cout << "return the max value is : " << compare<float>( fi, fj ) << endl;
const string strN = "aaaaaaaaaaa";
const string strM = "zengraoli";
cout << "return the max value is : " << compare<string>( strN, strM ) << endl;
return 0;
}
模板的实例化
1)隐式实例化
常用方式,实例化为
compare<int> intcompare(2, 3)
2)显示实例化
在声明时,直接在template关键字后接函数的声明,且函数标识符后接模板参数
比如:
template int compare<int> intcompare( int, int );
用模板使用通用算法-------------------------------------------------------------------------
actioncontainer 有一个撤销和恢复的通用功能
#include "stdafx.h"
#include "iostream"
using namespace std;
template<typename T>
class CActionContainer
{
public:
CActionContainer()
: m_nRedoPos( 0 ), m_nUndoPos( 0 )
{
}
void add( T value );
T redo();
T undo();
private:
int m_nRedoPos;
int m_nUndoPos;
// Container size
const static int ActionContainerSize = 5;
// record array
T m_RedoAction[ ActionContainerSize ];
T m_UndoAction[ ActionContainerSize ];
};
template<typename T>
void CActionContainer<T>::add( T value )
{
// if the container is full, adjust the pos of the container to add
if ( m_nUndoPos > ActionContainerSize )
{
m_nUndoPos = m_nUndoPos - 1;
for ( int i = 0; i < ActionContainerSize; i++ )
{
m_UndoAction[i] = m_UndoAction[ i + 1];
}
}
m_UndoAction[ m_nUndoPos++ ] = value;
}
// undo operator
template <typename T>
T CActionContainer<T>::undo()
{
// copy the revocation action to restore of the array
m_RedoAction[ m_nRedoPos++ ] = m_UndoAction[ --m_nUndoPos ];
return m_UndoAction[ m_nUndoPos ];
}
// redo operaor
template <typename T>
T CActionContainer<T>::redo()
{
// copy recovery action to the revocation of the array
m_UndoAction[ m_nUndoPos++ ] = m_RedoAction[ --m_nRedoPos ];
return m_RedoAction[ m_nRedoPos ];
}
int _tmain(int argc, _TCHAR* argv[])
{
CActionContainer<int> intaction;
intaction.add( 1 );
intaction.add( 2 );
intaction.add( 3 );
intaction.add( 4 );
intaction.add( 5 );
int iUndo = intaction.undo();
cout << "pass undo current value is : " << iUndo << endl;
iUndo = intaction.undo();
cout << "second pass undo current value is : " << iUndo << endl;
int iRedo = intaction.redo();
cout << "pass redo current value is : " << iRedo << endl;
iRedo = intaction.redo();
cout << "second pass redo current value is : " << iRedo << endl;
return 0;
}
泛型编程
1)
通过使用模板,可以使程序具有更好的代码重用性。泛型编程就是一种大量使用模板来实现更好的代码重用性的编程方式
2)
泛型编程的代表作品STL是一种高效、泛型、可交互操作的软件组件。其中算法是泛型的,不与任何特定的数据结构或对象类型联系在一起。
STL容器
1)
顺序容器
deque(双端队列)、list(线性表)、vector(动态数组容器)
基于这三种基本的顺序容器又可以构造出一些专门的容器,用于比较特殊的数据结构,包括heap(堆)、stack(栈)、queue(队列)、priority queue(优先队列)
2)
关联容器
所容纳的对象时有{键、值}对组成
3)
操作容器中的数据元素
接受用户输入并将数据保存到容器中
在开始位置插入一个数据
删除容器中的前三个数据
清空容器中的所有数据
#include "stdafx.h"
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
void vecDisplay( const float fValue )
{
cout << "current value is : " << fValue << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<float> vecScore;
float fi = 0.0f;
for ( int i = 0; i < 5; i++ )
{
cin >> fi;
vecScore.push_back(fi);
}
cout << "input the value : " << endl;
for_each( vecScore.begin(), vecScore.end(), vecDisplay );
const float fj = 0.02f;
vecScore.insert( vecScore.begin(), fj );
cout << "\n";
cout << "in the begin insert a number 0.02 : " << endl;
for_each( vecScore.begin(), vecScore.end(), vecDisplay );
vecScore.erase( vecScore.begin() );
vecScore.erase( vecScore.begin() );
vecScore.erase( vecScore.begin() );
cout << "\n";
cout << "delete vec in the before three number : " << endl;
for_each( vecScore.begin(), vecScore.end(), vecDisplay );
vecScore.clear();
cout << "\n";
cout << "clear vec : " << endl;
for_each( vecScore.begin(), vecScore.end(), vecDisplay );
return 0;
}
STL迭代器
1)
容器和算法结合起来的黏合剂
和指针的区别,迭代器不一定具有地址值
2)
按照使用的目的不同,各个容器都提供了多种类型的迭代器。比如只读迭代器,前移迭代器等。跟指针类似迭代器前面加上*运算符能够获取这个迭代器所指向的数据;可以使用++或者--来将迭代器向
前或者向后移动一个位置,让它指向容器中的其他位置的数据元素。如果迭代器到达容器中的最后一个元素的后面,则迭代器编程past_the_end值,使用past_the_end值的迭代器来访问数据元素是非法
的,就好像使用NULL值的指针一样。
3)遍历容器
#include "stdafx.h"
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
vector<int> vecScore;
vecScore.push_back( 50 );
vecScore.push_back( 60 );
vecScore.push_back( 70 );
vecScore.push_back( 80 );
vecScore.push_back( 90 );
vector<int>::iterator it;
for ( it = vecScore.begin(); it != vecScore.end(); it++ )
{
cout << "print current value : " << ( *it ) << endl;
}
return 0;
}
4)一般使用
a、对于对象,一般存放该对象的指针
b、小心清理容器中保存的对象指针,如果容器中保存的是对象,那么在容器析构的时候容器会自动清理这些对象。但是,如果存放对象指针,那么在容器析构的时候,首先要释放这些指针所指向的对象。
#include "stdafx.h"
#include "vector"
#include "string"
#include "algorithm"
#include "iostream"
using namespace std;
class CStudent
{
public:
CStudent( int iHeight ) : m_nHeight( iHeight )
{
}
int GetHeight() const
{
return m_nHeight;
}
private:
int m_nHeight;
};
void vecDisplay( CStudent* pSt )
{
cout << "current value is : " << pSt->GetHeight() << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<CStudent *> vecStudent;
CStudent* CTest_A = new CStudent( 165 );
CStudent* CTest_B = new CStudent( 175 );
CStudent* CTest_C = new CStudent( 185 );
vecStudent.push_back( CTest_A );
vecStudent.push_back( CTest_B );
vecStudent.push_back( CTest_C );
cout << "Init vector : " << endl;
for_each( vecStudent.begin(), vecStudent.end(), vecDisplay );
vector<CStudent *>::iterator it;
for ( it = vecStudent.begin(); it != vecStudent.end(); it++ )
{
if ( NULL != ( *it ))
{
delete ( *it );
}
( *it ) = NULL;
}
cout << "clear this point vector" << endl;
vecStudent.clear();
return 0;
}
c、如果需要将某个对象保存到容器中,实际上STL会重新生成一个此对象的拷贝,然后将这个拷贝保存在容器中,源对象不再使用。所以,当要保存的对象中含有指针类型成员变量时,要为容器中的对
象实现拷贝构造函数和赋值操作符。
--------------------------------------------------------------
#include "stdafx.h"
#include "vector"
#include "string"
#include "algorithm"
#include "iostream"
using namespace std;
class CStudent
{
public:
CStudent( const char* strName, const int iHeight)
{
m_nHeight = iHeight;
m_strName = new char[ strlen( strName + 1 ) ];
strcpy( m_strName, strName );
}
CStudent( const CStudent& st )
{
m_nHeight = st.m_nHeight;
m_strName = new char[ strlen( st.m_strName ) ];
strcpy( m_strName, st.m_strName );
}
CStudent& operator= ( const CStudent& st )
{
// to prevent self assignment
if ( this == &st )
{
return *this;
}
m_nHeight = st.m_nHeight;
m_strName = new char[ strlen( st.m_strName ) ];
strcpy( m_strName, st.m_strName );
return *this;
}
~CStudent()
{
if ( NULL != m_strName )
{
delete[] m_strName;
m_strName = NULL;
}
}
char* GetName() const
{
return m_strName;
}
int GetHeight() const
{
return m_nHeight;
}
private:
int m_nHeight;
char* m_strName;
};
void vecDisplay( const CStudent st )
{
cout << "the student name is : " << st.GetName()<< endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
// Init
vector<CStudent> vecStudent;
CStudent Test_A( "zengraoli1", 155 );
CStudent Test_B( "zengraoli2", 165 );
CStudent Test_C( "zengraoli3", 175 );
Test_A = Test_B; // Test_A已经构造过了,所以这时进入的事重载的=操作符
CStudent Test_D = Test_C; // Test_D没构造过,所以这时进入拷贝构造函数
vecStudent.push_back(Test_A);
vecStudent.push_back(Test_B);
vecStudent.push_back(Test_C);
cout << "output vector element : " << endl;
for_each( vecStudent.begin(), vecStudent.end(), vecDisplay );
return 0;
}
d、删除一个容器中大于某个数
删除的时候要注意:
如在for循环中加上it++,那么删除的时候会后移一个。可以不再for中写it++,而在else部分写
删除一个数的时候,不能仅仅是vecStudent.erase( it );必须要it = vecStudent.erase( it );记录,这是因为STL里的所有容器类中的erase实现都会返回一个迭代器,这个迭代器指向"当前删除
元素的后续元素,或者是end()"
--------------------------------------------------------------
#include "stdafx.h"
#include "vector"
#include "string"
#include "algorithm"
#include "iostream"
using namespace std;
class CStudent
{
public:
CStudent( int iHeight ) : m_nHeight( iHeight )
{
}
int GetHeight() const
{
return m_nHeight;
}
private:
int m_nHeight;
};
void vecDisplay( CStudent* pSt )
{
cout << "current value is : " << pSt->GetHeight() << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<CStudent *> vecStudent;
CStudent* CTest_A = new CStudent( 165 );
CStudent* CTest_B = new CStudent( 175 );
CStudent* CTest_C = new CStudent( 185 );
vecStudent.push_back( CTest_A );
vecStudent.push_back( CTest_B );
vecStudent.push_back( CTest_C );
cout << "Init vector : " << endl;
for_each( vecStudent.begin(), vecStudent.end(), vecDisplay );
vector<CStudent *>::iterator it;
for ( it = vecStudent.begin(); it != vecStudent.end(); )
{
if ( ( *it )->GetHeight() < 180 )
{
delete ( *it );
( *it ) = NULL;
it = vecStudent.erase( it );
}
else
{
it++;
}
}
cout << "\n";
cout << "delete smaller then 180 : " << endl;
for_each( vecStudent.begin(), vecStudent.end(), vecDisplay );
return 0;
}