C++编程语言虽然功能强大，应用方式灵活，但是在实际编程中同样会出现各种各样的错误。在这里我们将会为大家详细介绍一下有关C++指针漂移的解决方法，希望本文介绍的内容可以帮助大家解决问题。
最近我们在工作中碰到一个奇怪的问题，最后确定是多继承引起的C++指针漂移，跟C++对象模型有关。示意如下：
class A {...}; class B{...}; class AB : public B, public A {...} ... AB *pab = new AB(); A* pa = (A*)pab; B* pb = (B*)pab; 这时候你发现pa和pb的值是不一样的！它们中有一个跟pab是相等的，而另外一个产生了偏移。如果把AB的声明中A和B的顺序调换一下，则产生偏移的指针也会变为另外一个。
为了确定这是编译器做了转换的缘故，利用void指针愚弄编译器：
void *pv = (void*)pab; pa = (A*)pv; 这时候pa的值倒是跟pab相等了，然而指向了错误的地方。从pab到pa的转换，依赖于路径的选择，让人不是很放心。还不知道把指针放入容器中再取出来，会不会出错。当然，上面使用了强制类型转换，在良好的程序中应该避免。如果只有隐式转换，可以得到正确的结果：
std::vector<A*> v; //implicit type conversion v.insert(v.begin(), pab); void *pv = v[0]; pa = (A*)pv; 以下程序使用Cygwin/g++b编译通过：
#include <stdio.h> #include <vector> class A { public: int a; }; class B { public: int b; }; class AB : public B, public A { public: int ab; }; int main(int argc, char **argv) { AB *pab = new AB(); pab->ab = 1; pab->b = 2; pab->a = 3; A* pa = (A*)pab; B* pb = (B*)pab; printf( "AB: %p\n" \ " A: %p\n" \ " B: %p\n", pab, pa, pb); std::vector<A*> v; //implicit type conversion v.insert(v.begin(), pab); void *pv = v[0]; pa = (A*)pv; printf("pv is %p\npa is %p\npab %s pv\n", pv, pa, (pab == pv) ? "==" : "!="); printf("A.a is %d\n", pa->a); //forced type conversion pv = (void*)pab; pa = (A*)pv; printf("Now A.a is %d\n", pa->a); } 运行结果：
AB: 0x6b01f0 A: 0x6b01f4 B: 0x6b01f0 pv is 0x6b01f4 pa C++编程语言中的模板应用是一个比较复杂的应用技术，我们今天就先从C++ kmp算法模板的基本应用开始学习，从而加深我们对这方面知识的认识程度，方便将来的应用，提高编程效率。
在使用的时候加上这两行代码就行了
#include < vector> using namespace std;
C++ kmp算法模板参数说明
const T *source 待匹配的字符串
TL sourceLen 待匹配字符串的长度
const T *pattern 模式串
TL 模式串长度
C++ kmp算法模板代码示例：
template < class T,class TL> inline int kmpmatch(const T *source,TL sourceLen,const T *pattern,TL patternLen)
{ vector< int> next;
for ( int i = 0; i < patternLen ; i ++ ) next.push_back(0); next[0] = -1; for( int i = 1 ; i < patternLen ; i ++ )
{ int j = next[i - 1];
while ( (pattern != pattern[i + 1])&& (j >= 0))
{ j = next[j]; }
if ( pattern == pattern[j + 1])
{ next = j + 1; }
else { next = -1; } }
int i = 0; int j = 0;
while (( i < sourceLen ) && ( j < patternLen ))
{ if ( source == pattern[j] )
{ i ++; j ++; } else if ( j == 0 )
{ i ++; } else { j = next[j - 1 ] + 1; } }
if ( j >= patternLen )
{ if ( !next.empty() )
next.clear();
return i - patternLen ;
}
else
{ if ( !next.empty() ) next.clear();
return -1; } }
is 0x6b01f4 pab != pv A.a is 3 Now A.a is 2
KMP起源于字符串的匹配，顾名思义匹配字符就是看2串字符是能匹配上，比如说字符串S=”abcd”字符串T=”abc”，就可以匹配上，返回的是第一个匹配的位置，也就是1。
1、最基本的匹配。从原字符串开始搜索，若出现不能匹配，则从原搜索位置+1继续。这样时间复杂度是很高的。
虽然前4位一样但是第5位不一样，需要从原来的位置+1,再进行匹配。
以此类推，直到匹配为止。
/*检测从主串T的
pos位置开始，是否有和子串S匹配,如果有返回匹配开始位置，如果没有，返回-
1T:主串S:子串tlength:主串长度slength:子串长度
pos:主串开始位置
*/int Index (char T[],char S[],
int tlength,
int slength,
int pos){
int j=
0,i=
pos;
while(i<tlength&&j<slength) {
if(T
==S[j]) { i++; j++; } else { i=i-j+1; j=0; } } return j==slength?i-slength:-1;}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
2、KMP匹配算法。KMP算法就是改进了不匹配时候返回去从哪个位置开始再进行比较。比如当第一个主串的c与子串中的a不匹配时，下一次的 主串的b和子串的a(第一个)的比较可以通过分析子串的特点直接跳过这次比较。KMP算法就是为了告诉我们，我们应该每当一趟匹配过程中出现比较不等时，我们不需要回溯i指针。而是利用已经得到的“部分匹配”的结果将模式子串想右“滑动”尽可能远的距离，然后继续比较。首先先要统计一下要匹配的字符串中的重复情况，也就是求一个next[]数组。
求出next[]数组后，再进行匹配的时候就会加快速度。举一个求next[]数组的例子：
下面是一个KMP的实现例子。
#include <vector>#include <string>#include <iostream>using namespace std;
const vector<int> * kmp_next(
string &m){
static vector<int> next(m.size()); next[
0]=
0;
int temp;
for(
int i=
1; i<next.size(); i++) { temp=next[i-
1];
while(m
!=m[temp]&&temp>0) { temp=next[temp-1]; } if(m==m[temp]) next=temp+1; else next=0; } return &next;}bool kmp_search(string text,string m,int &pos){ const vector<int> * next=kmp_next(m); int tp=0; int mp=0; for(tp=0; tp<text.size(); tp++) { while(text[tp]!=m[mp]&&mp) mp=(*next)[mp-1]; if(text[tp]==m[mp]) mp++; if(mp==m.size()) { pos=tp-mp+1; return true; } } if(tp==text.size()) return false;}int main(){ int pos=0; kmp_search("abcacbc","ca",pos); cout<<"position = "<<pos+1<<endl; return 0;}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
3、KMP改进算法。KMP算法还是存在着一定的不足，比如S=”AAAABCDE”时候，T=”AAAAAX”这个时候可以求出next[]数组值为：012345，开始时i=5、j=5发现B与A不一致，j=next[5]=4。以此类推发现有多余的判断。由于T串的第2、3、4、5位置的字符和第一个位置的字符是一样的，那么可以用首位的next[1]代替相应的next[j]的值。于是对next[j]改进。
nextval数组的求解方法是：nextval[1]=0。从第二位开始，若要求nextval，将next的值对应的位的值与i的值进行比较（例如，第i为的值为’b’，next=3,则将i的值’b’与第三位的值进行比较），若相等，nextval=nextval【next】（例，nextval=nextval[3]）；若不相等，则nextval=next（例，nextval=next=3）。
1.第一位的nextval值必定为0，第二位如果与第一位相同则为0，如果不同则为1。
2.第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则，第三位的nextval值为0。
3.第四位的next值为2，那么将第四位和第二位进行比较，不同，则第四位的nextval值为其next值，为2。
4.第五位的next值为2，那么将第五位和第二位进行比较，相同，第二位的next值为1，则继续将第二位与第一位进行比较，不同，则第五位的nextval值为第二位的next值，为1。
5.第六位的next值为3，那么将第六位和第三位进行比较，不同，则第六位的nextval值为其next值，为3。
6.第七位的next值为1，那么将第七位和第一位进行比较，相同，则第七位的nextval值为0。
7.第八位的next值为2，那么将第八位和第二位进行比较，不同，则第八位的nextval值为其next值，为2。
|( 京ICP备09078825号 )
发表于 2017-6-19 23:21:01
收藏
