丰帅的博客

 

这章讲的东西一般在工程里用得比较多，所以作为《大学教程》，这里对这方面的东西说得不细，只让人一个大概的认识。

 

这里可以总结一下 宏与const变量的各自特点。

 

#define 符号常量 替换文本

const 变量

 

const变量拥有特定的数据类型，调试器能通过名称访问该变量。作为参数时可以被编译器检查类型。缺点是需占据内存位置。

用宏定义常量符号并不占据内存，用替换文本替换常量符号之后，调试器只能访问替换文本。缺点是作参数时不能作类型检查。

 

 

条件编译

几个等价

#if define => #ifdef

#if ! define  => #ifndef

#elif  => #else if

 

若屏蔽不编译的代码，可以

#if 0

  不编译的代码

#endif

 

 

 

结构的一些基本概念：

 

结构不能比较，因为在内存中他们的成员不一定是连续放置。

结构需按顺序初始化。

结构作为参数时一般是按值传递，也可以作指针或引用传递。

 

位运算

&  按位与

|   按位或

^   按位异或

<<  左移位

>>  右移位

~   求反

 

按位与通常与一个屏蔽字（mark）一起使用，屏蔽字就是某一位为1的数（其他位为0）。一个整数与这个屏蔽字则除了为1的那位外，其他位都被“屏蔽”掉了。专门测试一个数的某一位是否为1。

 

利用这点可以写出一种显示整数的二进制数值的方法：

void displayBits(unsigned x)
{
    unsigned m,i=1<<15;

    for(m=1; m<=16; m++)
    {
        cout<<(x & i ? ‘1’:’0′);
        x<<=1;

        if(m%8==0)
            cout<<‘ ‘;
    }
    cout<<endl;
}

  

位段（位域）

   对于结构或类中的unsigned类型和int类型的成员，C语言允许指定存储他们的位数，指定了存储位数的这些结构的成员或就是位域（位段）。

 

 

struct BitCard

{

   unsigned face:4;     指定了4位，可表示范围0000~1111   2^4=16

   unsigned suit:2;     指定了2位，范围 00~11       2^2=4

   unsigned color:1     指定了1位，范围 0~1

}

这整个结构其实只是一个unsigned字节（在32位机上是4个字节）

 

有个问题，超过了指定位，怎么办？程序会有什么行为？验证之

 

struct exam

{

     unsigned a : 2;

     unsigned b : 6;

     unsigned c : 4;

 

int main()

{

     struct exam rt;

 

     memset(&rt,0,sizeof(rt));

     rt.a=31;

 

     cout<<“size=”<<sizeof(rt)<<‘n’;

     cout<<rt.a<<‘ ,'<<rt.b;

    

     return 0;

}

结果显示：

size=4

3 ,0

其实a存储了31（11111）的最后两位。并且，多出的位数并未占b变量，而是给截断了。各位域间显示出单独性。

 

位域不能去地址 &.

尽管使用位域能够节省内存，但是会使编译器产生执行速度变慢的机器代码。

 

字符处理函数

int isdigit(int c)  如果c是一个数字，返回true，否则返回false

int isalpha(int c) 如果c是一个字母，返回true，否则返回false

int isalnum(int c)  如果c是一个字母或数字，返回true，否则返回false

int isxdigit(int c) 如果c是一个十六进制字符，返回true，否则返回false

int islower(int c) 如果c是一个小写字母，返回true，否则返回false

int isupper(int c) 如果c是一个大写字母，返回true，否则返回false

int tolower(int c) 返回其小写字母

int toupper(int c) 返回其大写字母

int isspace(int c) 如果c是一个空白符，返回true，否则返回false。空白符包括：’n’, 空格，’t’ , ‘r’ ,进纸符（’f’）,垂直制表符(‘v’)

 

int iscntrl(int c) 如果c是一个控制符，返回true，否则返回false

int ispunct(int c) 如果c是一个除空格、数字和字母外的可打印字符，返回true，否则返回false

 

int isprint(int c) 如果c是一个可打印符（包括空格），返回true，否则返回false

 

int isgraph(int c) 如果c是除空格之外的可打印字符，返回true，否则返回false

 

    

 

字符串转换函数

 double atof(const char *nPtr)   把字符串nPtr转换为double类型

 int atoi(const char* nPtr)       把字符串nPtr转换为int类型

long atol(const char *nPtr)       把字符串nPtr转换为long

 

double strtod(const char* nPtr,char **endPtr)

把字符串nPtr转换为double类型，endPtr接收nPtr中非数字的部分

 

long strtol(const char *nPtr,char** endPtr, int base)

把字符串nPtr转换为long类型，endPtr接收nPtr中遇到的第一个非数字到结尾的部分，base是待转换字符串中数值的进制类型，0表示可以是（8、10、16）。也可是2～36中任何值。

 

unsigned long strtoul(const char* nPtr,char **endPtr, int base)

把字符串nPtr转换为unsigned long类型，endPtr接收nPtr中遇到的第一个非数字到结尾的部分，base是待转换字符串中数值的进制类型，0表示可以是（8、10、16）。也可是2～36中任何值。

 

 

字符串处理中的查找函数

char *strchr(const char *s,int c)

查找c在s中首次出现的位置，成功将返回该位置的指针，否则返回NULL

 

size_t strcspn(const char *s1,const char *s2)

计算并返回s1中不包含s2中任何字符的起始段的长度。即在s1中查找是否有s2的字符，若碰到有该字符则返回从开始（数数1开始）到该字符之前的字符串长度。

 

size_t strspn(const char *s1,const char *s2)

计算并返回s1中只包含s2中字符的起始段长度。即当在s1中没遇到在s2中的字符时，返回从开始到该字符之前的字符串的长度。

char *strpbrk(const char *s1,const char *s2)

定位字符串s1首次出现在字符串s2中字符的位置。若找到了字符串s2中的字符，返回一个指向字符串s1中该字符的指针，否则返回NULL

 

char *strrchr(const char *s,int c)

返回c在s中最后一次出现的位置指针，否则返回NULL

 

char *strstr(const char *s1, const char *s2)

返回s2在s1中首次出现（整个字符串匹配）的位置指针，否则返回NULL。

 

 

字符串处理库中的内存函数

void *memcpy(void *s1,const void *s2, size_t n)

把s2所指的对象中的n个字符复制到s1所指的对象中。返回s1结果指针。

 

void *memmove(void *s1,const void *s2,size_t n)

同memcpy,并且多考虑了重叠情况（Overlapping Buffers）

 

int memcmp(const void *s1,const void *s2,size_t n)

比较s1和s2指向对象的前n个字符。如果s1所指向对象的字符等于、小于或大于s2所指向对象中的字符，返回值分别等于0、<0 、>0

 

void *memchr(const char *s,int c,size_t n)

定位s的前n个字符首次出现c的位置。找到就返回指向它的指针，否则返回0

 

void *memset(void *s, int c,size_t n)

把c复制到s所指的对象的前n个字符中。返回指向结果指针。

   

这里memcpy和memmove的区分有点特别。从源码看，显然，memmove比memcpy多了处理重叠的情况。但当我从标准库直接调用memcpy的时候，发现它也如同memmove一样处理了重叠的情况。

 

#include <stdio.h>

#include <string.h>

 

int main()

{

     char x[]=”Home Sweet Home”;

 

     if(x<&x[5])

     memmove(&x[5],x,10);//此处换成memcpy结果一样

 

     printf(“%s”,x);

     return 0;

}

结果：

Home Home Sweet

无论是用vc 还是 gcc 结果都是这样。

 

但是，如看memcpy的源码，结果应该是Home Home Home 才对。于是直接把源码copy过来用。

 

#include <stdio.h>

#include <string.h>

 

void * __cdecl Memcpy (

        void * dst,

        const void * src,

        size_t count

        )

{

        void * ret = dst;

 

#if defined (_M_MRX000) || defined (_M_ALPHA) || defined (_M_PPC)

        {

        extern void RtlMoveMemory( void *, const void *, size_t count );

 

        RtlMoveMemory( dst, src, count );

        }

#else  /* defined (_M_MRX000) || defined (_M_ALPHA) || defined (_M_PPC) */

        /*

         * copy from lower addresses to higher addresses

         */

        while (count–) {

                *(char *)dst = *(char *)src;

                dst = (char *)dst + 1;

                src = (char *)src + 1;

        }

#endif  /* defined (_M_MRX000) || defined (_M_ALPHA) || defined (_M_PPC) */

 

        return(ret);

}

 

int main()

{

     char x[]=”Home Sweet Home”;

 

     if(x<&x[5])

     Memcpy(&x[5],x,10);

     printf(“%s”,x);

     return 0;

}

结果：Home Home Home

 

看来，标准库里直接把memcpy作为memmove了。也难怪，其实两个功能几乎一样，后者还考虑了内存重叠情况，使用可能更方便。

 

其他函数

char *strerror(int errornum)

建立与errornum匹配的字符串（与系统有关），返回指向该字符串的指针。

char *_strerror(char *errMsag)

在输出错误信息前先打印出errMsag信息，也可以为NULL

void perror(const char *msg)

把相关错误信息写到stderr上，在此之前先打印msg信息，如果为NULL则直接打印错误信息。最后自动换行

 

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

 

int main()

{

     FILE *fp;

    

     if((fp=fopen(“tstc”,”r”)) == NULL)

       {

          perror(“open file failed”);

          printf(strerror(errno));

          printf(“n”);

          printf(_strerror(“open failed”));

       }

          

     return 0;

}

结果：

open file failed: No such file or directory

No such file or directory

open failed: No such file or directory

 

程序操作出现错误时通常会写errno，errno与错误信息表sys_errlist联系，而sys_errlist是以errno为序的一个错误信息列表。

组合的算法    出处：http://community.csdn.net/Expert/topic/3143/3143703.xml?temp=.5916101 

                       原作者：cxjddd (空浮无根)

内容简介：

　　本文讲述求一种求排列组合中的“组合”的算法。本算法通过组织选入组合
的元素和未选入组合的元素之间次序，以方便求得下一个组合——更大的或更小
的。算法采用了与 STL 中的（next、prev）permutation 类似的表达方法，将
所有组合纳入一个“由小到大”的线性序列里。

关键字：

组合　人字形　算法　STL　排列

正文：

　　受 STL 的排列算法（next_permutation 和 prev_permutation）的影响，
想写一个组合的算法，其结果就是一个类似于“人”字的算法。形如“人”字，
所有的元素被处理成左边升序，右边降序。

　　先说一下组合之间的次序，以 {1, 2, 3, 4} 选二为例，最“小”的组合是：
{1, 2}，然后是 {1, 3}，{1, 4}，{2, 3}，{2, 4}，最“大”的组合则是 {3,
4}。如果是从小到大的列出组合，则只要从剩余的元素里选出下一个更大的元素，
然后就可以很快地求出下一个更大的组合。比如对组合 {1, 2}，可从剩下的 3、
4 里选取 3 来代替 2，求得下一个组合为 {1, 3}。而对组合 {2, 4}，可从剩
下的 1、3 里选取 3 来代替 4 求得前一个组合 {2, 3}。

　　数据表示：用左闭右开区间表示，待选元素的集合由输入区间 [first,
last) 表示，入选组合的元素在区间 [first, middle)，剩下的元素在区间
[middle, last)。

　△△△◎◎◎●
　↑　　↑　　↑
first middle last

图中“△”为组合中的元素，“◎”为剩下的元素，下同。

　　区间 [first, middle) 一定是升序的；而 [middle, last) 则由升序和降
序两部分组成，如果没有左边的升序，则全部是降序，相反，没有右边的降序，
则全部是升序。而且，[first, middle) 与 [middle, last) 的升序部分是连续
的。左升右降，所以如“人”字形。以下称 [first, middle) 为前部；称
[middle, last) 为后部；且称后部中的升序部分为升部，其降序部分为降部。

　　　　　　◎　　　　　◎　　　　△　　　　　　　◎　　　　　△　　　
　　　　　◎◆　　　　◎◆　　　　■◎　　　　　△◆　　　　△■　　　
　　　　◎◆◆　　　△◆◆　　　　■◆◎　　　△■◆　　　△■■　　　
　　　△◆◆◆　　　■◆◆◎　　　■◆◆◎　　■■◆◎　　■■■◎　　
　　△■◆◆◆　　△■◆◆◆　　△■◆◆◆　△■■◆◆　　■■■◆◎　
　△■■◆◆◆　△■■◆◆◆　△■■◆◆◆　■■■◆◆◎　■■■◆◆◎
　■■■◆◆◆　■■■◆◆◆　■■■◆◆◆　■■■◆◆◆　■■■◆◆◆
　■■■◆◆◆　■■■◆◆◆　■■■◆◆◆　■■■◆◆◆　■■■◆◆◆
　　　　↑↑↑　　　　↑↑↓　　　　↓↓↓　　　　↑↓↓　　　　↓↓↓
　　　ａ　　ｅ　　　ｂ　ｅ　　　　ｂｅ　　　　　ｂｅ　　　　　ｂｅ　　

图中“↑”表示元素属于升部，“↓”则属于降部。

　　令前部的最后一个元素是 b，则所有升部的元素都是不小于 *b 的，而所有
属于降部的元素都是小于 *b 的。

　　按照这个特点，可以写出规范化的函数 adjust_combination()：先将前部
和后部的元素分别排序，然后以后面的元素以 *b 为“轴”对折，即可。代码大
致如下：

  // 规范化
  adjust_combination (first, middle, last)
  {
    sort_combination (first, middle);
    sort_combination (middle, last);

    j = lower_bound (middle, last, *b);
    /* 此时 [middle, j) 为降部的元素，而 [j, last) 为升部的元素
     */

    reverse (j, last);  // 把 [j, last) 反转
    reverse (middle, last); // 再把 [middle, last) 反转
    /* 升部还是升序，调到左边；
     * 降部已经是降序，调到右边了。
     */
  }

　　这个算法中有两个 STL 的函数（算法），在实现中是大量使用了的。这样
的函数大概有如下几个：

iter_swap (i, j)：交换两个迭代器指向的空间 *i 和 *j；

reverse (f, l)：反转，把 [f, l) 里的元素前后对调；

inplace_merge (f, m, l)：合并，把两个有序区间 [f, m) 和 [m, l) 合并成
有序区间 [f, l)；

lower_bound (f, l, v)：在有序区间 [f, l) 里找出第一个不小于 v 的位置；

upper_bound (f, l, v)：在有序区间 [f, l) 里找出第一个大于 v 的位置。

　　除了上面这些 STL 的函数，还有一个 sort_combination() 用来排序的，
其实现以 inplace_merge() 为辅助，使用归并排序。

　　依照后部中元素与 *b 的大小关系，可以这样区分后部中的升部与降部：令
[middle, last) 中最大的元素为 e，e 后第一个小于的元素为 f（若无，则令
f = last）。则若 *e >= *b，一定有 [middle, f) 是升部，[f, last) 为降部；
相反若 *e < *b，一定有 e == middle 且 [middle, last) 为降部。

　　下面以“无重复元素，组合从小到大”的条件来分析。

　　先考察一下这样的程序，{1, 2, 3, 4, 5, 6} 选三：

  for (a = 1; a <= 6-2; a++)
    for (b = a + 1; b <= 6-1; b++)
      for (c = c + 1; c <= 6; c++)
        out (a, b, c);

　　这个程序就是“从小到大”的，其中的 c 对应前部的最后一个元素，总体
{a, b, c} 对应前部。如果 c 的值不是最大的，则找出 c 的下一个更大的值代
替 c。如果 c 已经是最大的值，则让 b 的值变大；如果 b 也到了最大的值，
就让 a 的值变大。如果 a 不能再大，则结束。当然，a 实际最大值也就是 4，
b 是 5。如果是 a 或 b 的值变了，那么其后的元素的值也要一起改变，就如组
合 {1, 4} 变成 {2, 3}。

　　从上面可以看出，最重要的事情是，从当前组合里选出要被替换的元素，从
剩下的元素里选出用来替换的元素，然后就交换、调整一下。简单地说，就是要
从前部里找出最大的可以变大的元素，并变大。这个算法里安排这样的人字形结
构，就是为了便于找出两个关键的元素。

　　如果存在升部（*b < *e，或是 *b < *middle），则表示后面有比 *b 更大
的元素，所以选取升部的第一个元素 *middle 与 *b 交换。加上调整的话，可
以用“冒泡”法把 *b 往后移。

  // 存在升部，替换掉 *b
  if (*b < *e)
    {
      j = b;
      i = j++;
      while ((j != last) && (*i < *j))
        iter_swap (i++, j++);
    }

　　如果只有降部，那么有两种情况：一是 *first > *e，组合已经是最大的了；
另外就不是最大的组合了，可以求下一个更大的。前面一种情况很简单，调整到
最小的组合即可。后一种情况，则要求出前部中要替换掉的元素和降部中要选出
的元素。

  // 只有降部，且已经是最大的组合
  if (*e < *first)
    {
      reverse (first, middle);
      reverse (first, last);
    }

　　（后一种情况）前部中要替换掉的元素 *i 可以由 *middle 求出，也就是
前部里小于 *middle 的最大的元素。求出了要被替换的元素 *i，然后就可以求
出用来替换的元素 *j 了：也就是降区里大于 *i 的最小的元素。除了交换 *i
和 *j，还要把 i 到 j 之间的元素调整好。这里先后两次很有意思，前面一次
是小于里的最大的，后面一次是大于里的最小的。

    // 只的降部时，求下一个更大的组合
    // 要被替换的元素：
    i = b;
    while (!(*–i < *middle))
      ;
    // 用来替换的元素：
    j = last;
    while (!(*i < *–j))
      ;

    // 交换
    iter_swap (i, j);

    // 调整 i 至 j 的元素
    reverse (++i, middle);  // 最大的元素在前
    reverse (i, j);         // 现在最小的元素在前了

　　前面所说的，就是当“没有重复元素，且从小到大”时的算法。可以区分成
三种情况：一是存在升部；二是恰好最大；三是从降部里选出元素。这样一个处
理无重复元素的 next_combination 就出来了，也可以命名成
next_combination_unique()。

　　如果有重复元素，那么就要多上“等于”比较，上面三种情况就要做些改变。
这里还是只用“小于”比较，等于和大于就都要从小于里变化出来。第一种情况
可改成 *b 小于 *middle。第二种情况要改一下判断的条件，改成 !(*first <
*e)。剩下的情况，则要分两种：一是 *b < *e，表示存在升部且有比 *b 大的
元素，从升部里找出比 *b 大的元素，替换 *b；另外则与无重复元素时的第三
种类似，从前部里找出最大的比 *e 小的元素 *i，从降部里找出最小的比 *i
大的元素 *j，交换 i 和 j 并调整。

　　（汗！写到前面，发现一个思路上的 bug，还好不会出问题。）

　　总结“有重复元素，从小到大”的代码大致如下：

  /* 此代码未验证，以源代码为准 */
  if (*b < *middle)
    {
      j = b;
      i = j++;
      while ((j != last) && (*i < *j))
        iter_swap (i++, j++);
 
      return true;
    }
 
  if (!(*first < *e))
    {
      reverse (first, middle);
      reverse (first, last);
      return false;
    }

  if (*b < *e)
    {
      bb = b;
      while ((++b != e) && !(*b < *bb))
        ;
      reverse (bb, f);
      reverse (b, f);
      return true;
    }
  else
    {
      i = b;
      while (!(*–i < *e))
        ;
      j = last;
      while (!(*i < *–j))
        ;
      iter_swap (i, j);
      reverse (++i, middle);
      reverse (i, j);
      return true;
    }

下面讨论从大到小的算法，同样，先假设没有相同的元素。从大到小的算法，
简单地说是，找出最大的可以变小的元素，并变小。

　　如果不存在升部（*middle < *b 或说 *e < *b），则 *middle（*e） 就是
要新选入的元素，而要选出的元素就是第一个比 *e 大的元素。这种情况是最简
单的了。

  if (*middle < *b)
    {
      i = upper_bound (first, middle, *middle);
      iter_swap (i, middle);
    }

　　如果存在升部（*b < *middle），也分两种情况；一是 f == last，表示只
有升部而没有降部，到达最小的组合；另一种，*f 就是要新选入的元素，找出
第一个比 *f 大的元素，即为要选出的元素（当然，要选入选出的元素可能更
多）。

  /* 只有升部，已经是最小的组合 */
  if (f == last)
    {
      reverse (first, last);
      reverse (first, middle);
    }

　　第二种情况，找出第一个比 *f 大的元素 *i，则 *i 就是要换出的元素，
而 (i, middle) 则要换成所有最大的元素（*b 应该是全部元素中最大的元素，
然后其前依次是次小的元素）。

  /* 有升部也有降部，做较大调整 */
  i = upper_bound (first, middle, *f);
  iter_swap (i, f);
  reverse (++i, f);
  reverse (i, middle);

　　如果有重复元素，从大到小这种算法主要的改动是要判断换出的位置是否为
b，进行不同的处理。主要是因为相同元素的存在，使交换元素后的调整变得更
复杂一些，因而做相应变化。

  if (*middle < *b)
    {
      i = upper_bound (first, middle, *middle);
      if (i != b)
        iter_swap (i, middle);
      else
        {
   s = middle;
   while ((++s != last) && !(*s < *middle))
     ;
   reverse (b, s);
 }
      return true;
    }

  if (f == last)
    {
      reverse (first, last);
      reverse (first, middle);
      return false;
    }

  i = upper_bound (first, middle, *f);
  if (i == b)
    {
      s = f;
      while ((++s != last) && !(*s < *f))
        ;
      reverse (b, f);
      reverse (b, s);
    }
  else
    {
      iter_swap (i, f);
      reverse (++i, f);
      reverse (i, middle);
    }
  return true;

　　至此，组合算法 combination 已经说完了，但是写得比较含糊。在下篇里
将细说一些东西，但完整的程序实现这里已经有了。

template
void
sort_combination (BiIterator first, BiIterator last)
{
  if (first == last) // $(AC;SPT*KX
(B    return;

  BiIterator i = first;
  ++i;
  if (i == last)     // $(AR;8vT*KX
(B    return;
 
  int half = distance (first, last) / 2;  // half of the length
  BiIterator middle = first;
  advance (middle, half);  // middle += half

  sort_combination (first, middle);     // sort first part
  sort_combination (middle, last);      // sort second part

  inplace_merge (first, middle, last);  // merge two parts
}

template
void
adjust_combination (BiIterator first, BiIterator middle, BiIterator last)
{
  // the front part or the back part have no elements
  if ((first == middle) || (middle == last))
    return;

  sort_combination (first, middle);
  sort_combination (middle, last);

  BiIterator b = middle;
  –b;
  BiIterator j = lower_bound (middle, last, *b);
  reverse (j, last);
  reverse (middle, last);
}

template
void
init_combination (BiIterator first, BiIterator middle, BiIterator last,
    bool min)
{
  sort_combination (first, last);

  if (min == false)
    {
      // the max combination
      reverse (first, last);
      reverse (first, middle);
    }
}

template
bool
next_combination (BiIterator first, BiIterator middle, BiIterator last)
{
  if ((first == middle) || (middle == last))
    return false;

  // last element of [first, middle)
  BiIterator b = middle;
  –b;

  if (*b < *middle)
    {
      BiIterator j = b;
      while ((++b != last) && (*j < *b))
 {
   iter_swap (j, b);
   j = b;
 }
      return true;
    }

  BiIterator e = last;
  –e;
  while (e != middle)
    {
      BiIterator k = e;
      –k;
      if (!(*k < *e))
 e = k;
      else
 break;
    }
 
  BiIterator f = e;
  ++f;
  while ((f != last) && !(*f < *e))
    ++f;

  if (!(*first < *e))
    {
      reverse (first, middle);
      reverse (first, last);
      return false;
    }

  if (*b < *e)
    {
      BiIterator bb = b;
      while ((++bb != e) && !(*b < *bb))
 ;
      reverse (bb, f);
      reverse (b, f);
    }
  else
    {
      BiIterator i = b;
      while (!(*–i < *e))
 ;
     
      BiIterator j = last;
      while (!(*i < *–j))
 ;

      iter_swap (i, j);
      reverse (++i, middle);
      reverse (i, j);
    }
  return true;
}

template
bool
prev_combination (BiIterator first, BiIterator middle, BiIterator last)
{
  if ((first == middle) || (middle == last))
    return false;
 
  BiIterator b = middle;
  –b;
 
  if (*middle < *b)
    {
      BiIterator i = upper_bound (first, middle, *middle);
      if (i != b)
 iter_swap (i, middle);
      else
 {
   BiIterator s = middle;
   while ((++s != last) && !(*s < *middle))
     ;
   reverse (b, s);
 }

      return true;
    }
 
  BiIterator e = last;
  –e;
  while (e != middle)
    {
      BiIterator k = e;
      –k;
      if (!(*k < *e))
 e = k;
      else
 break;
    }
 
  BiIterator f = e;
  ++f;
  while ((f != last) && !(*f < *e))
    ++f;

  if (/*!(*e < *b) && */(f == last))
    {
      reverse (first, last);
      reverse (first, middle);
      return false;
    }

  BiIterator i = upper_bound (first, middle, *f);
  if (i == b)
    {
      BiIterator s = f;
      while ((++s != last) && !(*s < *f))
 ;

      reverse (b, f);
      reverse (b, s);
    }
  else
    {
      iter_swap (i, f);
      reverse (++i, f);
      reverse (i, middle);
    }
  return true;
}