实现动态大数结构

  大数结构是一种常见的数据结构，在C++当中，我们常用vector来动态实现。除此之外，我们也可以仿照vector的思路，自己实现内存的动态分配，当内存容量达到上限时，用C-api realloc进行内存的重新分配。

#define REQUIRE2(p, q) assert((p) || (q)) #define REQUIRE1(p) assert(p) #define INITSIZE 24

  先定义了几个宏，前两个是对表达式的判断，INITSIZE是动态大数结构的初始阈值，当超过了这个阈值之后，便发生扩容。

public:         BigNum(const BigNum& other) : sign(other.sign), p(other.p) {}         BigNum() {             p = static_cast<char *>(malloc(INITSIZE));             REQUIRE1(p);         }         BigNum(BigNum&& other) : sign(other.sign), p(other.p) {}         ~BigNum() {             free(p);         }          BigNum& operator=(const BigNum& other) = default;         bool operator==(const BigNum& other) const = default;

  构造析构......注意析构要释放内存，防止发生内存泄漏。

void init() {             sign = getchar();             REQUIRE2(sign == '+', sign == '-');                          char c;             char *start = p;             while ((c = getchar()) != ' ' && c != 'n' && c != 't' && c != 'r') {                 REQUIRE1(isdigit(c));                 if (start - p >= threshold - 1) {                     void *mem = realloc(p, threshold << 1);                     REQUIRE1(mem);                     p = static_cast<char *>(mem);                     start = p + threshold - 1;                     threshold <<= 1;                 }                 *start = c;                 ++start;             }             start = nullptr;         }

  这是关键的一部分，通过getchar函数，使得从键盘上动态读取字符，并且维护一个指针start，这样就可以实时统计大数结构当中的容量。在这里，前面定义的宏就派上用场了，需要严格检查读入的字符是否为数字（第一个读入的字符必须是+或者-符号）。

friend std::ostream& operator<<(std::ostream& os, const BigNum& big) {             os << big.sign << big.p;             return os;         }

  重载输出函数。

private:         char sign;         char *p;         std::size_t threshold = INITSIZE;

  在内部，维护了三个成员，分别是数的符号，指向初始内存位置的指针与阈值（阈值每次发生扩容时会乘2）。

 

  完整代码如下

#define REQUIRE2(p, q) assert((p) || (q)) #define REQUIRE1(p) assert(p) #define INITSIZE 24  class BigNum {     public:         BigNum(const BigNum& other) : sign(other.sign), p(other.p) {}         BigNum() {             p = static_cast<char *>(malloc(INITSIZE));             REQUIRE1(p);         }         BigNum(BigNum&& other) : sign(other.sign), p(other.p) {}         ~BigNum() {             free(p);         }          BigNum& operator=(const BigNum& other) = default;         bool operator==(const BigNum& other) const = default;          void init() {             sign = getchar();             REQUIRE2(sign == '+', sign == '-');                          char c;             char *start = p;             while ((c = getchar()) != ' ' && c != 'n' && c != 't' && c != 'r') {                 REQUIRE1(isdigit(c));                 if (start - p >= threshold - 1) {                     void *mem = realloc(p, threshold << 1);                     REQUIRE1(mem);                     p = static_cast<char *>(mem);                     start = p + threshold - 1;                     threshold <<= 1;                 }                 *start = c;                 ++start;             }             start = nullptr;         }          friend std::ostream& operator<<(std::ostream& os, const BigNum& big) {             os << big.sign << big.p;             return os;         }      private:         char sign;         char *p;         std::size_t threshold = INITSIZE; };