C++ — 语言的发展

留下评论

运行时效率:
内联函数
程序的编译策略:
1. 类声明与实现的分离,凭配声明与实现的工具(link程序);
2. 类声明与依赖关系分析程序;
对象布局模型:
类型检查:
一个程序涉及语言要服务于两种目的:它为程序员提供了一种载体, 使他们能藐视需要执行的动作; 它还 提供了一组概念,程序员借助他们思考什么东西是能做的。[Stroustrup, 1986].  语言设计并不是从某个第一原理出发的涉及,而是一种需要经验、试验和有效工程折衷的艺术.
 
C++的保护概念:
1. 保护是通过编译时的机制提供的,目标是防止发生意外事件,而不是防止欺骗或者有意的侵犯;
2. 访问权是由类本身授予,而不是单方面的取用;
3. 保护的单位是类,而不是个别的对象;
4. 访问权控制室通过名字实行的,并不依赖于被命名事物的种类;
5. 受保护的是访问权,而不是可见性.

什么是程序设计的正交性?

临时变量析构的7个主要的可能点:
1. 在第一个使用之后;
2. 在语句结束处;
3. 在下一个分支点;
4. 在块的结束处;
5. 在函数的结束处;
6. 在最后的使用之后;
7. 在第一次使用和块结束之间(ARM规则).

编译技术中的控制流分析与局部流分析
存储分配的粒度控制场景:
1. 某个类频繁使用, 为了避免不必要的内存碎片, 可以为这样的类编写一个独立的类分配器.
2. 在资源非常紧张的场景里运行很长时间而且不能中断的程序. 传统上这样的系统要完全避免动态存储分配. 一个特定用途的分配程序可以用来管理
    这类的有限资源.
内存管理中遇到的需求描述: 1. 我们需要一种机制把对象安放到某个特定地址. 例如, 把一个表示进程的对象放到特定硬件所要求的特定地址去; 2.
    我们需要一种机制在某个特定分配区里分配对象. 例如在一个多处理器系统的共享储存中, 或者从由某个特定对象管理器控制的区域中分配对象.
解决方案: 允许对operator new()进行重载, 以便为new运算法提供一种允许有附加参数的语法形式. 例如, 一个能把对象分配到特定分配区的
    operator new()可能被定义为下面的这种样子:
void * operator new(size_t size, void *p)
{
     return p;
}

void *buf = (void *)0xF00F;
X *p2 = new (buf)X; // 放置语法形式.

void * operator new(size_t s, fast_arena &a)
{
     return a.alloc(s);
}

fast_arena arena;
X *p = new (arena)X;
class fast_arena
{
private:
     char *maxp;
     char *freep;
     char *expand(size_t s);

public:
     void * alloc(size_t s)
     {
           char *p = freep;
           return (((freep += s) < maxp) ? p : expand(s));
     }
     void free(void *) {}
     void clear();
};
注意在operator new()和operator delete()之间有一种明显的不对称性. 前者能够被重载而后者不能.
class X
{
    void * operator new(size_t);
    void * operator new(size_t, Arena &); // Ordinary allocation
    void operator delete(void *); // In Arena.
    // can’t define void operator delete(void *, Arena &);
};
原因是因为我们不能期望用户在删除指针所指向的内存空间时知道它是如何分配的. 那么我们应该这样让这些内存空间被自动管理呢?
我们可以让程序在执行的某个特殊点以整体的方式自动释放已分配的内存空间; 也可以为这块特殊的内存分配地定义一个特定的垃圾
收集系统. 我们一般采用前一种方式进行处理. Release2.0引进了显式调用析构函数的可能性, 以对付某些不大常见的情况, 在那里存储分配和
释放是相互完全分离的. 一个实际例子是某种容器, 它需要为自己所包含的对象完成所有的存储分配工作.

魔鬼隐藏在细节之中. –古语

C++区分了5种在函数调用中的参数匹配规则:
1. 匹配中部转换或者只使用不可避免的转换(例如, 从数组名到指针, 函数名到函数指针, 以及T到const T);
2. 使用了整数 提升的匹配(像ANSI C标准所定义的. 也就是说从char到int、short到int以及它们对应的unsigned
     类型)以及float到double;
3. 使用了标准转换的匹配(例如从int到double、derived*到base*、unsigned int到int);
4. 使用了用户定义转换的匹配(包括通过构造函数和转换操作);
5. 使用了在函数声明里的省略号…的匹配;
6. 对涉及多个参数的调用, 一个函数要想被选中, 那就要求它至少在某一个参数上比其他任何
    函数都匹配得更好, 而对每个参数都至少与其它函数匹配得同样好.

多重继承的实现方式: 关键设计类的内存布局中虚函数表的存储模型.

Advertisements

C++学习笔记 — 多态

留下评论

     设计容器类时,由于元素的类型要在运行时才能被确定,所以当我们要创建、复制和存储它们时,这会给编译时检查带来麻烦。
     解决方案:使用句柄类(Handle),把一个单一类型的对象与一个与之有某种特定继承关系的任意类型的对象捆绑起来。所以,句柄可以让我们忽略正在处理的对象的
的准确类型,同时还能避免指针带来的关于内存管理的麻烦。
     问题:Handle类的实现方式?
     最简单的Handle类的实现方式:运用智能指针的概念,也就是对父类指针进行包装,通过包装类来管理父类指针所指向内存块的分配与回收。
     class Vehicle
     {
      public:
           virtual double weight() const=0;
           virtual void start()=0;
           virtual Vehicle* copy() const = 0;     
           viutual ~Vehicle() {}
     };
     class VehicleSurrogate
     {
      public:
           VehicleSurrogate();
           VehicleSurrogate(const Vehicle&);
           ~VehicleSurrogate();
           VehicleSurrogate(const VehicleSurrogate&);
           VehicleSurrogate& operator=(const VehicleSurrogate&);
           double weight() const;
           void start();
      private:
           Vehicle *vp;
     };
     使用范例:VehicleSurrogate parking_lot[10];
                  Automobile x;
                  parking_lot[num_vehicles++] = x;
     实现方式之二:使用引用计数,要领是主意"写时拷贝"操作。也就是当需要修改被公共引用的对象是需要首先断开对象的当前连接,然后在新的引用值上作修改操   
     作。关于这种思想的具体实现中可以改进的地方可以参考"Effecitive C++",基本是把引用计数再抽象出来提高重用度。
 
问题:1. 要求一边读入表达式一边计算表达式的值?
        2. 实现图像的横向连接、纵向连接、加裱和去裱等操作(用字符串模拟图像位值)?
 
数组下标与指针访问的区别:
1. 效率问题;
2. 下标值本身就具有意义而与它是否用于下标无关; 要使用指针访问容器的元素没有必要知道容器的标识, 指针本身就包含了必要的信息;
template<class T> class Array
{
public:
     Array() : data(0), sz(0) {}
     Array(unsigned size)
          : sz(size), data(new T[size]) {}
     ~Array() { delete[] data; }
     const T& operator[](unsigned n) const;
     {
           if (n >= sz || data == 0)
           {
                 throw "Array subscript out of range";
           }
           return data[n];
     }
     T& operator[](unsigned n)
     {
           if (n >= sz || data == 0)
           {
                throw "Array subscript out of range";
           }
           return data[n];
     }
     operator const T*() const
     {
           return data;
     }
     operator T*()
     {
           return data;
     }
private:
     T *data;
      unsigned sz;
      Array(const Array &a);
      Array& operator=(const Arrray &a);
};
对内建数组使用指针比使用下标要方便得多; 但是改变这样的类的实现或者增加它的操作都会突然使指向它的元素指针阵失效, 例如实现resize()功能。
解决的方法就是牺牲掉其他一些特性来进行折中。
// 再次使用引用计数
template<class T> class Array_Data
{
private:
     friend class Array<T>;
     friend class Pointer<T>;
     Array_Data(unsigned size = 0)
          : data(new T[size]), sz(size), use(1) {}
     const T& operator[](unsigned n) const;
     T& operator[](unsigned n);
     
     // 不允许复制操作
     Array_Data(const Array_Data &a);
     Array_Data* operator=(const Array_Data &a);
     T *data;
     unsigned sz;
     int use;
};
为容器定义迭代器可以有效避免用户通过指针访问容器时的空引用问题, 而可以让用户使用指针遍历容器。
怎样设计容器的迭代器?怎样提高自己抽象的能力?
 

字符串查找算法

留下评论

Boyer-Moore Algorithm

//计算Bad-Character
//很简单,就是找到每个字符出现的最右位置
void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}

// 计算以pattern中每一位字符结尾的与pattern的后缀相等的字串长度
void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
// pattern: abc11abc11abc22abc11abc
// 注意分析当i移至红色的'c'字符上时,
// 我们不能简单地认为suff[i] = suff[i + m - 1 - f],
// 这个时候我们要重新计算以其结尾的最长后缀。
 if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= 0; --i)
// 如果下面的判断成立的话,表明这个子串是pattern的一个前缀
if (suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
// 这一行是计算当某位失去匹配时,应该根据其最佳后缀
// 所移动的距离。
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}


void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];

/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}
引用地址:http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140

终于搞定了!

接下来是根据那篇原始论文看懂它的数学论证过程。

Problem — Tactic to be winner

留下评论

Problem description: 有n(>1)堆棋子,两个人交替从里面取任意数量(>0)的棋子,拿走最后一颗棋子者为输者。制定一种策略让先拿棋子的人肯定赢。
 

C++ — Exception hints

留下评论

1. When we throw an exception with the style "throw obj;" the compiler will invoke the type’s coping constructor.
    : How does the compiler determine the type of obj?
    : obj’s static type.
    for example,
    class Wdiget { … }
    class SpecialWidget : public Widget { … }
   
    void passAndThrowWidget()
    {
        SpecialWidget localSpecialWidget;
        …
        Widget& w = localSpecialWdiget;
        throw w;// equals to throw Widget::Widget(w);
    } 
 
2. The difference between syntax "throw;" and "throw obj;":
    for example,
    catch(Widget& w)
   {
         …
         throw;// 1
   }
   VS.
   catch(Widget& w)
   {
        …
        throw w; // 2
   }
   place [1] just throw the w itself while place [2] will call Widget::Widget(w), so it can only return
   instance of type Widget.
 
3. Only two kinds of implicit type convesion fit for exception catching.
    3.1 inheritance-based;
    3.2 typed pointers to untyped pointer;
    wrong expectation example:
    void f(int value)
    {
        try
        {
             …
             throw value;
        }
        catch(double d) // this line will never be executed.
        {
             …
        }
    }

C++ — 自动隐式类型转换

留下评论

1. How to self-define conversion function?
    grammar: operator Type();
    for example, if we want to implement the String class by ourselves:
    class String
    {
     public:
         //… other definitions
 
         // This method will convert the String object to C-style char array.
         operator char*() const;
    };
 
2. But the implicit conversion sometimes will course problem or make the program run with undefined result.
    for example,
    bool operator==(const Array<int>& a1, const Array<int>& a2);
    Array<int> a(10);
    Array<int> b(10);
    …
    for(int i = 0; i < 10; ++i)
    {
        // Sometimes we are too careless to omit the subscripting syntax.
        if(a == b[i])
        {
             // do something else…
        }
    }
    If we defines a constructor Array(int size); for the Array template, the compiler won’t report the error about the
    red line.
 
3. How to avoid harmful implicit type conversion by the compiler?
   3.1 Use explicit keyword for the constructor (such as explicit Array(int size); for the above example);
   3.2 template<class T>
        class Array
        {
         public:
             class ArraySize
             {
                 public:
                     ArraySize(int numElements) : theSize(numElements){}
                     int size() const { return theSize; }
                 private:
                     int theSize;
             };
             Array(it lowBound, int highBound);
             Array(ArraySize size);
            // … other definitions.
        };

Numeric solution — find special numbers

留下评论

Problem: 在1-1,000,000之间有多少个数字其位上各位之和为20. 例如992, 9+9+2=20.
 
void GetNumbers(int sum, int r, int bits[], int c)
{
 if(r > 0)
 {
  for(int i = 0; i <= 9; ++i)
  {
    if((sum + bits[r – 1] – i + 1) / r <= 9 && (sum + bits[r – 1] – i) >= 0)
   //if((sum + 1 – i) / r <= 9 && (sum – i) >= 0)
   {
    sum = sum + bits[r – 1] – i;
    bits[r – 1] = i;
    if(sum == 0)
    {
     if(bits[i])
     {
      for(int i = 0; i < c; ++i)
      {
       cout << bits[i];
      }
      cout << endl;
     }
    }
    else
    {
     GetNumbers(sum, r – 1, bits, c);
    }
   }
   else
   {
    sum = sum + bits[r – 1];
    bits[r – 1] = 0;
   }
  }
 }
}
void GetNumbers(int n, int sum)
{
 int* bits = new int[n];
 for(int i = 1; i <= n; i++)
 {
  for(int j = 0; j < n; j++)
  {
   bits[j] = 0;
  }
  GetNumbers(sum, i, bits, i);
 }
}
 

Older Entries