Java开发XML解析器Document、SAXParser、XMLStreamReader详解

1.Document

接口对象是官方出的,W3C标准,作为HTML、XML实体类加载到内存中,形成文档对象,然后使用循环进行数据解析。

2.SAXParser

SAXParser是一个用于处理XML的事件驱动的“推”模型。它不是W3C标准,但它是一个得到了广泛认可的API,大多数SAXParser解析器在实现的时候都遵循标准。

SAXParser解析器不象DOM那样建立一个整个文档的树型表示,而是使用数据流的方式读取,然后根据读取文档的元素类型进行事件反馈。这些事件将会推给事件处理器,而事件处理器则提供对文档内容的访问数据包装等。

事件处理器有三种基本类型:

用于访问XML DTD内容的DTDHandler;
用于低级访问解析错误的ErrorHandler;
用于访问文档内容的最普遍类型ContentHandler。
3.XMLStreamReader(StAX)

XMLStreamReader也属于数据留解析的一种,读入文件,按线性的方式从文件头一直读到文件尾;和SAXParser一样,使用事件驱动的模型来反馈事件。不同的是,XMLStreamReader不使用SAXParser的推模型,而是使用 “拉”模型进行事件处理。而且XMLStreamReader解析器不使用回调机制,而是根据应用程序的要求返回事件。XMLStreamReader还提供了用户友好的API用于读入和写出。

尽管SAXParser向ContentHandler返回不同类型的事件,但XMLStreamReader却将它的事件返回给应用程序,甚至可以以对象的形式提供事件。

当应用程序要求一个事件时,XMLStreamReader解析器根据需要从XML文档读取并将该事件返回给该应用程序。 XMLStreamReader提供了用于创建XMLStreamReader读写器的工具,所以应用程序可以使用StAX接口而无需参考特定实现的细节。

与Document和SAXParser不同,XMLStreamReader指定了两个解析模型:指针模型,如SAXParser,它简单地返回事件;迭代程序模型,它以对象形式返回事件(这里需要吐槽一下,我个人是比较喜欢SAXParser的handler事件处理的模式,代码方面比较值观),其实XMLStreamReader也可以跟SAXParser一样,但是需要额外的对象创建开销。

FileChannel文件通道

FileChannel

FileChannel 可以通过 RandomAccessFile、FileInputStream、FileOutStream也可以通过FileChannel.open 获取。

其中方法write 和 read 都是通过 ByteBuffer 对象进行操作(读写)。

 

如果使用FileChannel.open打开文件通道时可以提供 OpenOption 来定义行为,如果需要写的话可以使用 write 和 append 模式,在不确定文件是否存在是加入 Create,这样如果不存在会自动创建。

write 和 append 有什么区别?

这两种模式声明的不是 FileChannel 的模式,而是声明那个文件的打开模式,作为 FileChannel 只顾自己position 增加,在 write 模式下文件的 postion 跟 Channel 的 position 是一致的,但是在 append 模式下文件 position 跟 Channel 的完全脱节,两者都是自顾自增加。

说到这里你可能已经想到,如果要实现每次输入内容覆盖之前的话,必须选择 Write 模式,并且每次 channel.write 前都需要将channel的 position 置为零。

文件锁 Lock

FileChannel.lock tryLock 从文档上看一个是同步阻塞、另一个是非阻塞。

tryLock 在同一个JVM中不同线程获取时,先到先得,后到的返回null,但我在windows上测试为抛出异常:OverlappingFileLockException ,据说 Linux 上抛出【java.io.IOException:Permission denied】。

tryLock 和 lock 都提供一个API含有三个参数

lock(long position,
long size,
boolean shared)

看样子貌似可以锁住部分似的,可能跟操作系统有关,反正windows上并不行,抛出异常:java.io.IOException: 另一个程序已锁定文件的一部分,进程无法访问。

共享锁,独占锁概念上跟并发的 WriteReadLock 一样可多读但只一写,写是独占的。

怎么设置?看上面API第三个参数。

lock(long position,
long size,
boolean shared) // 是否共享锁

如何判断获取到的是什么锁?

FileLock.isShared()
实现靠谱的文件锁

主要就是一个循环判断加try.catch

while (true) {
try {
lock = fc.lock();
break;
} catch (OverlappingFileLockException e) {
Thread.sleep(1 * 1000);
}
}

这可以让需要获取锁的代码块阻塞在那里,当然咯,如果想 wait 也是可以的,只是要在 release 的地方加上 notifyAll 了。

内存映射文件

这个可谓 “大杀器”,特别是大文件读写时,效率比普通IO要快N倍。据一位网友测试86M的文件进行读操作,内存映射方式只要78ms,而普通IO需要468ms,差了6倍。可见威力无穷。
为什么这么快?

普通IO是操作系统先读入到内核缓冲器,再转到用户进程私有的内存区,当然JVM进程还作了内核态和用户态的切换;而内存映射方式,是将文件直接映射到内存中的一块区域,当调用读时会抛出缺页异常,OS会读取该页数据,依次往复,因此这里少了依次内核缓冲区到私有内存之间的拷贝,所以快了不少。
内存映射模式:

read_only只读设置 ;

read_write读写都可,并且任何写操作立即反应在文件上,其他共享该文件的内存映射也能立即看到 。

private私有模式,不写时跟read_only 一样,但是写时会克隆一个独立内存区域,不会影响文件。

代码片段:

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.Path;
import java.nio.file.Paths;

/**
 * Created by alan on 2018/12/15.
 */
public class FileChannelDemo extends OutPut {

    public static void main(String[] args) {
        String path = "d:/1.txt";
        w(path);
        try {
            Path paths = Paths.get(path);
//            FileChannel channel = FileChannel.open(paths);//HEX{01 02 03 04}
            FileInputStream in = new FileInputStream(path);
            FileChannel channel = in.getChannel();
            MappedByteBuffer buffer = channel.map(FileChannel.MapMode.READ_ONLY, 0, channel.size());

            String str = "";
            for (int i = 0; i < channel.size(); i++) {
                str += buffer.get() + " ";
            }
            out(str);

            buffer.flip();
            channel.close();
            in.close();


        } catch (IOException e) {
            e.printStackTrace();
        }

    }

    public static void w(String path) {
        try {

            FileOutputStream out = new FileOutputStream(path);
            FileChannel channel = out.getChannel();
            ByteBuffer buffer = ByteBuffer.allocate(20);

            buffer.put((byte) 0x1B);
            buffer.put((byte) 0x2B);
            buffer.put((byte) 0x3B);
            buffer.put((byte) 0x4B);
            buffer.put((byte) 0x5B);
            buffer.put((byte) 0xFB);
            buffer.put((byte) 0xEB);

            buffer.flip();

            channel.write(buffer,0);
            channel.close();

            out.flush();
            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

ConcurrentLinkedDeque类详解

一、Queue接口定义

boolean add(E e);//入列 会抛出异常

boolean offer(E e);//入列

E remove();//出列 会抛出异常

E poll();//出列

E element();//读取 会抛出异常

E peek();//读取

Queue是一种具有FIFO特点的数据结构,元素只能在队首进行“入列”操作,在队尾进行“出列”操作。Queue的接口非常简单,一共只有三种类型的操作:入列、出列、读取。

每种操作类型,都给出了两种方法,区别就是其中一种操作在队列的状态不满足某些要求时,会抛出异常;另一种,则直接返回特殊值(如null)。

再来看下JDK中QueueDeque这两种数据结构的接口定义,看看Deque和Queue相比有哪些增强:

二、Deque接口定义

Deque(double-ended queue)是一种双端队列,也就是说可以在任意一端进行“入列”,也可以在任意一端进行“出列”。

Queue接口的所有方法Deque都具备,只不过队首/队尾都可以进行“出列”和“入列”操作:

void addFirst(E e);//队首入列 会抛出异常

void addLast(E e);//队尾入列 会抛出异常

boolean offerFirst(E e);//队首入列

boolean offerLast(E e);//队尾入列

E removeFirst();//队首出列 会抛出异常

E removeLast();//队尾出列 会抛出异常

E pollFirst();//队首出列

E pollLast();//队尾出列

E getFirst();//队首读取 会抛出异常

E getLast();//队尾读取 会抛出异常

E peekFirst();//队首读取

E peekLast();//队尾读取

除此之外,Deque还可以当作“栈”来使用,我们知道“栈”是一种具有“LIFO”特点的数据结构,Deque提供了pushpoppeek这三个栈方法,一般实现这三个方法时,可以利用已有方法,即有如下映射关系:

Comparison of Stack and Deque methods
Stack Method Equivalent Deque Method
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()

官网连接:https://docs.oracle.com/javase/8/docs/api/

三、ConcurrentLinkedDeque简介

ConcurrentLinkedDeque是JDK1.7时,J.U.C包引入的一个集合工具类。在JDK1.7之前,除了Stack类外,并没有其它适合并发环境的“栈”数据结构。ConcurrentLinkedDeque作为双端队列,可以当作“栈”来使用,并且高效地支持并发环境。

ConcurrentLinkedDequeConcurrentLinkedQueue一样,采用了无锁算法,底层基于自旋+CAS的方式实现。

Class ConcurrentLinkedDeque<E>

 

Class ConcurrentLinkedQueue<E>

四、ConcurrentLinkedDeque原理

1.队列结构:

我们先来看下ConcurrentLinkedDeque的内部结构:

public class ConcurrentLinkedDeque<E> extends AbstractCollection<E>
    implements Deque<E>, java.io.Serializable {

    /**
     * 头指针
     */
    private transient volatile Node<E> head;

    /**
     * 尾指针
     */
    private transient volatile Node<E> tail;

    private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
    
    // Unsafe mechanics
    private static final sun.misc.Unsafe UNSAFE;
    private static final long headOffset;
    private static final long tailOffset;

    static {
        PREV_TERMINATOR = new Node<Object>();
        PREV_TERMINATOR.next = PREV_TERMINATOR;
        NEXT_TERMINATOR = new Node<Object>();
        NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> k = ConcurrentLinkedDeque.class;
            headOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("head"));
            tailOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("tail"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
    
    /**
     * 双链表结点定义
     */
    static final class Node<E> {
        volatile Node<E> prev;  // 前驱指针
        volatile E item;        // 结点值
        volatile Node<E> next;  // 后驱指针

        Node() {
        }

        Node(E item) {
            UNSAFE.putObject(this, itemOffset, item);
        }

        boolean casItem(E cmp, E val) {
            return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
        }

        void lazySetNext(Node<E> val) {
            UNSAFE.putOrderedObject(this, nextOffset, val);
        }

        boolean casNext(Node<E> cmp, Node<E> val) {
            return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
        }

        void lazySetPrev(Node<E> val) {
            UNSAFE.putOrderedObject(this, prevOffset, val);
        }

        boolean casPrev(Node<E> cmp, Node<E> val) {
            return UNSAFE.compareAndSwapObject(this, prevOffset, cmp, val);
        }

        // Unsafe mechanics

        private static final sun.misc.Unsafe UNSAFE;
        private static final long prevOffset;
        private static final long itemOffset;
        private static final long nextOffset;

        static {
            try {
                UNSAFE = sun.misc.Unsafe.getUnsafe();
                Class<?> k = Node.class;
                prevOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("prev"));
                itemOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("item"));
                nextOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("next"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }
    }
    
    // ...
}

可以看到,ConcurrentLinkedDeque的内部和ConcurrentLinkedQueue类似,不过是一个双链表结构,每入队一个元素就是插入一个Node类型的结点。字段head指向队列头,tail指向队列尾,通过Unsafe来CAS操作字段值以及Node对象的字段值。

QQ截图20181130105240

需要特别注意的是ConcurrentLinkedDeque包含两个特殊字段:PREV_TERMINATOR、NEXT_TERMINATOR。
这两个字段初始时都指向一个值为null的空结点,这两个字段在结点删除时使用,后面会详细介绍:

QQ截图20181130105328

2.构造器定义

ConcurrentLinkedDeque包含两种构造器:

/**
 * 空构造器.
 */
public ConcurrentLinkedDeque() {
    head = tail = new Node<E>(null);

}
/**
 * 从已有集合,构造队列
 */
public ConcurrentLinkedDeque(Collection<? extends E> c) {
    Node<E> h = null, t = null;
    for (E e : c) {
        checkNotNull(e);
        Node<E> newNode = new Node<E>(e);
        if (h == null)
            h = t = newNode;
        else {  // 在队尾插入元素
            t.lazySetNext(newNode);
            newNode.lazySetPrev(t);
            t = newNode;
        }
    }
    initHeadTail(h, t);
}

我们重点看下空构造器,通过空构造器建立的ConcurrentLinkedDeque对象,其head和tail指针并非指向null,而是指向一个item值为null的Node结点——哨兵结点,如下图:

QQ截图20181130105328

3.入队操作

双端队列与普通队列的入队区别是:双端队列既可以在“队尾”插入元素,也可以在“队首”插入元素。ConcurrentLinkedDeque的入队方法有很多:addFirst(e)addLast(e)offerFirst(e)offerLast(e)

public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

public boolean offerFirst(E e) {
    linkFirst(e);
    return true;
}

public boolean offerLast(E e) {
    linkLast(e);
    return true;
}

可以看到,队首“入队”其实就是调用了linkFirst(e)方法,而队尾“入队”是调用了 linkLast(e)方法。我们先来看下队首“入队”——linkFirst(e):

/**
 * 在队首插入一个元素.
 */
private void linkFirst(E e) {
    checkNotNull(e);
    final Node<E> newNode = new Node<E>(e); // 创建待插入的结点

    restartFromHead:
    for (; ; )
        for (Node<E> h = head, p = h, q; ; ) {
            if ((q = p.prev) != null && (q = (p = q).prev) != null)
                // Check for head updates every other hop.
                // If p == q, we are sure to follow head instead.
                p = (h != (h = head)) ? h : q;
            else if (p.next == p) // PREV_TERMINATOR
                continue restartFromHead;
            else {
                // p is first node
                newNode.lazySetNext(p); // CAS piggyback
                if (p.casPrev(null, newNode)) {
                    // Successful CAS is the linearization point
                    // for e to become an element of this deque,
                    // and for newNode to become "live".
                    if (p != h) // hop two nodes at a time
                        casHead(h, newNode);  // Failure is OK.
                    return;
                }
                // Lost CAS race to another thread; re-read prev
            }
        }
}

为了便于理解,我们以示例来看:假设有两个线程ThreadA和ThreadB同时进行入队操作。

①ThreadA先单独入队一个元素9

此时,ThreadA会执行CASE3分支:

else {                              // CASE3: p是队首结点
    newNode.lazySetNext(p);         // “新结点”的next指向队首结点
    if (p.casPrev(null, newNode)) { // 队首结点的prev指针指向“新结点”
        if (p != h) // hop two nodes at a time
            casHead(h, newNode);  // Failure is OK.
        return;
    }
    // 执行到此处说明CAS操作失败,有其它线程也在队首插入元素
}

队列的结构如下:
QQ截图20181130105240


②ThreadA入队一个元素2,同时ThreadB入队一个元素10

此时,依然执行CASE3分支,我们假设ThreadA操作成功,ThreadB操作失败:

else {                              // CASE3: p是队首结点
    newNode.lazySetNext(p);         // “新结点”的next指向队首结点
    if (p.casPrev(null, newNode)) { // 队首结点的prev指针指向“新结点”
        if (p != h) // hop two nodes at a time
            casHead(h, newNode);  // Failure is OK.
        return;
    }
    // 执行到此处说明CAS操作失败,有其它线程也在队首插入元素
}

ThreadA的CAS操作成功后,会进入以下判断:

if (p != h) // hop two nodes at a time
    casHead(h, newNode);  // Failure is OK.

上述判断的作用就是重置head头指针,可以看到,ConcurrentLinkedDeque其实是以每次跳2个结点的方式移动指针,这主要考虑到并发环境以这种hop跳的方式可以提升效率。

此时队列的机构如下:
QQ截图20181130105240

注意,此时ThreadB的p.casPrev(null, newNode)操作失败了,所以会进入下一次自旋,在下一次自旋中继续进入CASE3。如果ThreadA的casHead操作没有完成,ThreadB就进入了下一次自旋,则会进入分支1,重置指针p指向队首。最终队列结构如下:

QQ截图20181130105328

在队尾插入元素和队首类似,不再赘述,读者可以自己阅读源码。

4.出队操作

ConcurrentLinkedDeque的出队一样分为队首、队尾两种情况:removeFirst()pollFirst()removeLast()pollLast()

public E removeFirst() {
    return screenNullResult(pollFirst());
}

public E removeLast() {
    return screenNullResult(pollLast());
}

public E pollFirst() {
    for (Node<E> p = first(); p != null; p = succ(p)) {
        E item = p.item;
        if (item != null && p.casItem(item, null)) {
            unlink(p);
            return item;
        }
    }
    return null;
}

public E pollLast() {
    for (Node<E> p = last(); p != null; p = pred(p)) {
        E item = p.item;
        if (item != null && p.casItem(item, null)) {
            unlink(p);
            return item;
        }
    }
    return null;
}

可以看到,两个remove方法其实内部都调用了对应的poll方法,我们重点看下队尾的“出队”——pollLast方法:

public E pollLast() {
    for (Node<E> p = last(); p != null; p = pred(p)) {
        E item = p.item;
        if (item != null && p.casItem(item, null)) {
            unlink(p);
            return item;
        }
    }
    return null;
}

last方法用于寻找队尾结点,即满足p.next == null && p.prev != p的结点:

Node<E> last() {
    restartFromTail:
    for (; ; )
        for (Node<E> t = tail, p = t, q; ; ) {
            if ((q = p.next) != null &&
                (q = (p = q).next) != null)
                // Check for tail updates every other hop.
                // If p == q, we are sure to follow tail instead.
                p = (t != (t = tail)) ? t : q;
            else if (p == t
                // It is possible that p is NEXT_TERMINATOR,
                // but if so, the CAS is guaranteed to fail.
                || casTail(t, p))
                return p;
            else
                continue restartFromTail;
        }
}

pred方法用于寻找当前结点的前驱结点(如果前驱是自身,则返回队尾结点):

final Node<E> pred(Node<E> p) {
    Node<E> q = p.prev;
    return (p == q) ? last() : q;
}

unlink方法断开结点的链接:

/**
 * Unlinks non-null node x.
 */
void unlink(Node<E> x) {
    // assert x != null;
    // assert x.item == null;
    // assert x != PREV_TERMINATOR;
    // assert x != NEXT_TERMINATOR;

    final Node<E> prev = x.prev;
    final Node<E> next = x.next;
    if (prev == null) {
        unlinkFirst(x, next);
    } else if (next == null) {
        unlinkLast(x, prev);
    } else {
        Node<E> activePred, activeSucc;
        boolean isFirst, isLast;
        int hops = 1;

        // Find active predecessor
        for (Node<E> p = prev; ; ++hops) {
            if (p.item != null) {
                activePred = p;
                isFirst = false;
                break;
            }
            Node<E> q = p.prev;
            if (q == null) {
                if (p.next == p)
                    return;
                activePred = p;
                isFirst = true;
                break;
            } else if (p == q)
                return;
            else
                p = q;
        }

        // Find active successor
        for (Node<E> p = next; ; ++hops) {
            if (p.item != null) {
                activeSucc = p;
                isLast = false;
                break;
            }
            Node<E> q = p.next;
            if (q == null) {
                if (p.prev == p)
                    return;
                activeSucc = p;
                isLast = true;
                break;
            } else if (p == q)
                return;
            else
                p = q;
        }

        // TODO: better HOP heuristics
        if (hops < HOPS
            // always squeeze out interior deleted nodes
            && (isFirst | isLast))
            return;

        // Squeeze out deleted nodes between activePred and
        // activeSucc, including x.
        skipDeletedSuccessors(activePred);
        skipDeletedPredecessors(activeSucc);

        // Try to gc-unlink, if possible
        if ((isFirst | isLast) &&

            // Recheck expected state of predecessor and successor
            (activePred.next == activeSucc) &&
            (activeSucc.prev == activePred) &&
            (isFirst ? activePred.prev == null : activePred.item != null) &&
            (isLast ? activeSucc.next == null : activeSucc.item != null)) {

            updateHead(); // Ensure x is not reachable from head
            updateTail(); // Ensure x is not reachable from tail

            // Finally, actually gc-unlink
            x.lazySetPrev(isFirst ? prevTerminator() : x);
            x.lazySetNext(isLast ? nextTerminator() : x);
        }
    }
}

ConcurrentLinkedDeque相比ConcurrentLinkedQueue,功能更丰富,但是由于底层结构是双链表,且完全采用CAS+自旋的无锁算法保证线程安全性,所以需要考虑各种并发情况,源码比ConcurrentLinkedQueue更加难懂,留待有精力作进一步分析。

五、总结

ConcurrentLinkedDeque使用了自旋+CAS的非阻塞算法来保证线程并发访问时的数据一致性。由于队列本身是一种双链表结构,所以虽然算法看起来很简单,但其实需要考虑各种并发的情况,实现复杂度较高,并且ConcurrentLinkedDeque不具备实时的数据一致性,实际运用中,如果需要一种线程安全的栈结构,可以使用ConcurrentLinkedDeque。

另外,关于ConcurrentLinkedDeque还有以下需要注意的几点:

  1. ConcurrentLinkedDeque的迭代器是弱一致性的,这在并发容器中是比较普遍的现象,主要是指在一个线程在遍历队列结点而另一个线程尝试对某个队列结点进行修改的话不会抛出ConcurrentModificationException,这也就造成在遍历某个尚未被修改的结点时,在next方法返回时可以看到该结点的修改,但在遍历后再对该结点修改时就看不到这种变化。
  2. size方法需要遍历链表,所以在并发情况下,其结果不一定是准确的,只能供参考。

使用C/C++新建了一个类似于Java的StringBuffer类

使用C/C++新建了一个类似于Java的StringBuffer类,主要实现了常规的几种方法:

1.StringBuffer & append(const char * _c) ;
这个方法是往字符串中插入字符到最后;

2.StringBuffer(const StringBuffer & buf);
在C语言中如果需要使用到a=b这种赋值方法,并且数据成员使用指针形式,那么则需要自定义一个复制函数;

3.char* toString();
返回数据成员中的char数据;

4.int length();
返回字符串的长度;

5.std::string substr(int start = 0,int len = 1);
截取字符串,通常需要借助indexOf的方法来查找字符串的位置;

6.void replaceAll(const char * find, const char * des);
替换字符串中的指定文字;

7.int indexOf(const char * find);
查找指定字符串的位置,如果没有则返回-1;

8.bool operator==(const StringBuffer & buf);
C/C++中特有的方法,如果需要使用运算符:a==b,增需要定义一个自定义的运算符方法,这里只定义了:==。

 

接着就是贴出头文件:StringBuffer.h

#pragma once
#include<iostream>

//exmple:
/*
// StringBuffer sb;
// or like this:
// StringBuffer sb("test");
// sb.append("append.");

// and you can like this:
// sb.append("append 1,").append("append 2,");

// equal:
// sb1==sb?1:0
// if(sb1 == sb){//do something...}

// length:
// sb.length();

// substring:
// sb.substr(int strat,int end);
// sb.substr(0,1);//it will be return "t";

// find:
// sb.indexOf(char * find_char);
// sb.indexOf("st");//it will be return 2;
// sb.indexOf("index");//it will be return -1;

// replaceAll:
// sb.replaceAll(char * find_char,char * des_char);
// like this:
// sb.replaceAll("test","1234");

// toString:
// sb.toString();
*/

#ifndef STRING_BUFFER
#define STRING_BUFFER

class StringBuffer
{
   private:
      char * value;
      char * value1;
      int len;
      int _number;
   public:
      StringBuffer();
      StringBuffer(const char * _c);
      StringBuffer & append(const char * _c) ;
      StringBuffer(const StringBuffer & buf);
      char* toString();
      int length();
      std::string substr(int start = 0,int len = 1);
      void replaceAll(const char * find, const char * des);
      int indexOf(const char * find);
      bool operator==(const StringBuffer & buf);
      ~StringBuffer();
};

#endif // !STRING_BUFFER



然后贴出代码:

#include "pch.h"
#include "StringBuffer.h"
#include<iostream>
#include<string.h>


StringBuffer::StringBuffer()
{
   len = 1;
   _number = 0;
   value = new char[2]{"\0"};
}

StringBuffer::StringBuffer(const char * _c) {
   len = std::strlen(_c) + 1;
   _number = 1;
   value = new char[len];
   strcpy_s(value, len, _c);
}

StringBuffer::StringBuffer(const StringBuffer & buf) {
   len = buf.len;
   _number = buf._number;
   value = new char[len];
   strcpy_s(value, len, buf.value);
}

StringBuffer::~StringBuffer()
{
   delete[] value;
   std::cout << "StringBuffer out." << std::endl;
}

StringBuffer & StringBuffer::append(const char * _c) {
   int _l = std::strlen(_c)+1;
   value1 = new char[len+_l];
   strcpy_s(value1, len, value);
   strcat_s(value1, len + _l, _c);

   value = value1;
   
   len += _l;
   _number++;
   return *this;
}

char* StringBuffer::toString() {
   return this->value;
}

int StringBuffer::length() {
   return strlen(value);
}

std::string StringBuffer::substr(int start, int len) {
   std::string s = value;
   return s.substr(start, len);
}

int StringBuffer::indexOf(const char * find) {
   std::string s = value;
   return s.find(find);
}

void StringBuffer::replaceAll(const char * find, const char * des) {
   int idx = 0;
   int _len = std::strlen(find);
   bool has = false;
   std::string s = value;
   while (idx > -1)
   {
      idx = s.find(find);
      if (idx > -1) {
         s = s.replace(idx, _len, des);
         has = true;
      }
   }

   if (has) {
      strcpy_s(value, strlen(s.data()) + 1, s.data());
      len = strlen(s.data()) + 1;
      value1 = value;
   }
   
}

bool StringBuffer::operator==(const StringBuffer & buf) {
   if (this == &buf) {
      return true;
   }
   return strcmp(this->value, buf.value) == 0;
}

来一张效果图呗:

QQ截图20181118163945

C/C++关键字typedef使用指南

搞懂了c++创始人写的中的下面这个例子, 有助于你理解typdef:

typedef int P();
typedef int Q();
class X {
static P(Q); // 等价于`static int Q()`, Q在此作用域中不再是一个类型
static Q(P); // 等价于`static int Q(int ())`, 定义了一个名为Q的function
};

这是一个极好的例子, 先问一下 typedef int P()到底做了什么 ? 其实是 :

declares a function type P as returning an int and taking no arguments.

1. 官方定义

初次接触此类typedef用法的程序员直观上理解这个例子比较困难, 我们来看一下typedef的官方定义 :

Typedef does not work like typedef [type] [new name].The[new name] part does not always come at the end.

You should look at it this way : if[some declaration] declares a variable, typedef [same declaration] would define a type.

总结一下就是 : 任何声明变量的语句前面加上typedef之后,原来是变量的都变成一种类型。不管这个声明中的标识符号出现在中间还是最后。

2. 隐藏技能
typedef 定义的新类型, 使用时可以省略括号。什么意思 ?

typedef int NUM;
NUM a = 10; // 也可写成`NUM(a) = 10;
NUM(b) = 12; // 也可写成`NUM b = 12;

3. 例子(先从初级的开始 :)

int整型

typedef int x; // 定义了一个名为x的int类型

自定义结构体

typedef struct { char c; } s; // 定义名为s的struct类型

指针

typedef int *p; //定义了一个名为p的指针类型, 它指向int

高级的(注意标识符不一定在最后) :

数组

typedef int A[]; // 定义一个名为A的int数组的类型

函数

typedef int f(); // 定义一个名为f, 参数为空, 返回值为int的函数类型

typedef int g(int); // 定义一个名为g, 含一个int参数, 返回值为int行的函数类型

现在回过头看:

typedef int P();
static P(Q);

应该就比较好理解了, P是一个新定义的function类型, 它返回值为int, 无参数
根据我的第2点说明, P(Q); 实际上等价于P Q, 声明Q是一个返回值为int, 无参数的函数.

这玩意有什么用呢 ?
我们都知道C++语言里, 函数都是先声明后使用的(除非在使用之前定义), 看以下例子 :

#include <iostream>
#include <stdio.h>
#include <string>

typedef int P(); // 简单的
typedef void Q(int *p, const std::string& s1, const std::string& s2, size_t size, bool is_true); // 复杂的
class X {
public:
P(eat_shit); // 等价于声明`int eat_shit();`
Q(bullshit); // 等价于声明`void bullshit(int *p, const string& s1, const string& s2, size_t size, bool is_true);`
};

int main() {
X *xx;
printf(“shit ret: %d\n”, xx->eat_shit());
int a[] = { 1, 3, 4, 5, 7 };
xx->bullshit(a, “foo”, “bar”, sizeof(a) / sizeof(int), true);
}

int X::eat_shit() {
return 888;
}

void X::bullshit(int *p, const std::string& s1, const std::string& s2, size_t size, bool is_true) {
std::cout << “s1: ” << s1 << “, s2: ” << s2 << “, size: ” << size << std::endl;
printf(“elems:\n”);
for (int i = 0; i < size; i++) {
printf(“%d %s”, *p++, (i == size – 1) ? “” : “,”);
}
printf(“\n”);
}

理解了上面的再看下面这段,理解复杂的定义和声明:

在阅读Linux的内核代码是经常会遇到一些复杂的声明和定义,例如:

  1.  void * (*(*fp1) (int))[10];
  2. float(*(*fp2) (int, int, float)) (int);
  3. typedef double(*(*(*fp3) ())[10]) ();
    1. fp3 a;
  4. int(*(*fp4())[10]) ();

 

刚看到这些声明或者定义时,初学者可能头皮发毛,基于大惑不解。如果缺乏经验和方法来对这些内容进行理解,势必会让我们浪费大量的时间。

我尝试对这些内容进行疏理和总结,为自己和有同样困惑的同学答疑解惑。要理解这些复杂的声明和定义,我觉得首先不能着急,应该由浅而深,逐步突破。下面先看一些简单的定义:

1. 定义一个整型数

int a;

2. 定义一个指向整型数的指针

int *p;

3. 定义一个指向指针的指针,它指向的指针指向一个整型数

int **pp;

我们可以用一些简单的代码把这三条给串起来:

int a;
int *p;
int **pp;

p = &a; // p指向整数a所在的地址
pp = &p; // pp指向指针p

 

4. 定义一个包含10个整型数的数组

int arr[10];

5. 定义一个指向包含10个整型数数组的指针

int(*pArr)[10];

用几行代码将4、5两个定义串起来:

int arr[10];
int(*pArr)[10];

pArr = &arr;

6. 定义一个指向函数的指针,被指向的函数有一个整型参数并返回整型值

int(*pfunc) (int);

7. 定义一个包含10个指针的数组,其中包含的指针指向函数,这些函数有一个整型参数并返回整型值

int(*arr[10]) (int);

用几行代码将6、7两个定义串起来:

int(*pfunc) (int);
int(*arr[10]) (int);

arr[0] = pfunc;

到这一步,似乎就不是那么好理解了。现在需要请出用于理解复杂定义的“右左法则”:

从变量名看起,先往右,再往左,碰到圆括号就调转阅读的方向;括号内分析完就跳出括号,还是先右后左的顺序。如此循环,直到分析完整个定义。

让我们用这个方法来分析上面的第6条定义:int(*pfunc) (int);

  • 找到变量名pfunc,先往右是圆括号,调转方向,左边是一个*号,这说明pfunc是一个指针;
  • 然后跳出这个圆括号,先看右边,又遇到圆括号,这说明(*pfunc)是一个函数,所以pfunc是一个指向这类函数的指针,即函数指针,这类函数具有一个int类型的参数,返回值类型是int。

接着分析第7条定义:int(*arr[10]) (int);

  • 找到变量名arr,先往右是[]运算符,说明arr是一个数组;
  • 再往左是一个*号,说明arr数组的元素是指针(注意:这里的*修饰的不是arr,而是arr[10]。原因是[]运算符的优先级比*要高,arr先与[]结合。);
  • 跳出圆括号,先往右又遇到圆括号,说明arr数组的元素是指向函数的指针,它指向的函数有一个int类型的参数,返回值类型是int。

分析完这两个定义,相信多数人心里面应该有点谱了。

可应该还有人会问:怎么判断定义的是函数指针(定义6),还是数组指针(定义5),或是数组(定义7)?可以抽象出几个模式:

  • type(*var)(…); // 变量名var与*结合,被圆括号括起来,右边是参数列表。表明这是函数指针
  • type(*var)[]; //变量名var与*结合,被圆括号括起来,右边是[]运算符。表示这是数组指针
  • type(*var[])…; // 变量名var先与[]结合,说明这是一个数组(至于数组包含的是什么,由旁边的修饰决定)

至此,我们应该有能力分析文章开始列出来了几条声明和定义:

(1) void * (*(*fp1) (int))[10];

  • 找到变量名fp1,往右看是圆括号,调转方向往左看到*号,说明fp1是一个指针;
  • 跳出内层圆括号,往右看是参数列表,说明fp1是一个函数指针,接着往左看是*号,说明指向的函数返回值是指针;
  • 再跳出外层圆括号,往右看是[]运算符,说明函数返回的是一个数组指针,往左看是void *,说明数组包含的类型是void *。

简言之,fp1是一个指向函数的指针,该函数接受一个整型参数并返回一个指向含有10个void指针数组的指针。

(2) float(*(*fp2) (int, int, float)) (int);

  • 找到变量名fp2,往右看是圆括号,调转方向往左看到*号,说明fp2是一个指针;
  • 跳出内层圆括号,往右看是参数列表,说明fp2是一个函数指针,接着往左看是*号,说明指向的函数返回值是指针;
  • 再跳出外层圆括号,往右看还是参数列表,说明返回的指针是一个函数指针,该函数有一个int类型的参数,返回值类型是float。

简言之,fp2是一个指向函数的指针,该函数接受三个参数(int, int和float),且返回一个指向函数的指针,该函数接受一个整型参数并返回一个float。

(3) typedef double(*(*(*fp3) ())[10]) ();

fp3 a;

  • 如果创建许多复杂的定义,可以使用typedef。这一条显示typedef是如何缩短复杂的定义的。
  • 跟前面一样,先找到变量名fp3(这里fp3其实是新类型名),往右看是圆括号,调转方向往左是*,说明fp3是一个指针;
  • 跳出圆括号,往右看是空参数列表,说明fp3是一个函数指针,接着往左是*号,说明该函数的返回值是一个指针;
  • 跳出第二层圆括号,往右是[]运算符,说明函数的返回值是一个数组指针,接着往左是*号,说明数组中包含的是指针;
  • 跳出第三层圆括号,往右是参数列表,说明数组中包含的是函数指针,这些函数没有参数,返回值类型是double。

简言之,fp3是一个指向函数的指针,该函数无参数,且返回一个含有10个指向函数指针的数组的指针,这些函数不接受参数且返回double值。

这二行接着说明:a是fp3类型中的一个。

(4) int(*(*fp4())[10]) ();

这里fp4不是变量定义,而是一个函数声明。

  • 找到变量名fp4,往右是一个无参参数列表,说明fp4是一个函数,接着往左是*号,说明函数返回值是一个指针;
  • 跳出里层圆括号,往右是[]运算符,说明fp4的函数返回值是一个指向数组的指针,往左是*号,说明数组中包含的元素是指针;
  • 跳出外层圆括号,往右是一个无参参数列表,说明数组中包含的元素是函数指针,这些函数没有参数,返回值的类型是int。

简言之,fp4是一个返回指针的函数,该指针指向含有10个函数指针的数组,这些函数不接受参数且返回整型值。

用typedef简化复杂的声明和定义,以上我们已经看到了不少复杂的声明和定义,这里再举一个例子:

int *(*a[10]) (int, char*);

  • 用前面的“右左法则”,我们可以很快弄清楚:
  • a是一个包含10个函数指针的数组,这些函数的参数列表是(int, char*),返回值类型是int*。
  • 理解已经不成问题,这里的关键是如果要定义相同类型的变量b,都得重复书写:

int *(*b[10]) (int, char*);

这里有没有方便的办法避免这样没有价值的重复?答案就是用typedef来简化复杂的声明和定义。

typedef可以给现有的类型起个别名。这里用typedef给以上a、b的类型起个别名:

typedef int *(*A[10]) (int, char*); // 在之前定义的前面加入typedef,然后将变量名a替换成类型名A

现在要再定义相同类型的变量c,只需要:
A c;

再看一例:

void(*b[10]) (void(*)());

先替换右边括号里面的参数,将void(*)()的类型起个别名pParam:

18910111218