Д. Стефенс - C++. Сборник рецептов

• Название: C++. Сборник рецептов
• Автор: Д. Стефенс
• Издательство: КУДИЦ-ПРЕСС
• Жанр: Программирование
• Год: 2007
• ISBN: 5-91136-030-6

Данная книга написана экспертами по C++ и содержит готовые рецепты решения каждодневных задач для программистов на С++. Один из авторов является создателем библиотеки Boost Iostreams и нескольких других библиотек C++ с открытым исходным кодом. В книге затрагивается множество тем, вот лишь некоторые из них: работа с датой и временем; потоковый ввод/вывод; обработка исключений; работа с классами и объектами; сборка приложений; синтаксический анализ XML-документов; программирование математических задач. Читатель сможет использовать готовые решения, а сэкономленное время и усилия направить на решение конкретных задач.

---

 complex<double> coord = polar(rho, theta);

 cout << "rho = " << abs(coord) << ", theta = " << arg(coord) << endl;

 coord += polar(4.0, 0.0);

 cout << "rho = " << abs(coord) << ", theta = " << arg(coord) << endl;

}

Программа примера 11.34 выдает следующий результат.

rho = 3, theta = 1.5708

rho = 5, theta = 0.643501

Обсуждение

Существует естественная связь между полярными координатами и комплексными числами. Хотя эти понятия в какой-то мере взаимозаменяемы, использование одного и того же типа для представления разных концепций в целом нельзя считать хорошей идеей. Поскольку применение шаблона complex для представления полярных координат не является элегантным решением, я предусмотрел приведенный в примере 11.25 класс полярных координат, допускающий более естественное применение.

Пример 11.35. Класс полярных координат

#include <complex>

#include <iostream>

using namespace std;

template<class T>

struct BasicPolar {

 public typedef BasicPolar self;

 // конструкторы

 BasicPolar() : m() {} BasicPolar(const self& x) : m(x.m) {}

 BasicPolar(const T& rho, const T& theta) : m(polar(rho, theta)) {}

 // операторы присваивания

 self operator-() { return Polar(-m); }

 self& operator+=(const self& x) { m += x.m; return *this; }

 self& operator-=(const self& x) { m -= x.m; return *this; }

 self& operator*=(const self& x) { m *= x.m; return *this; }

 self& operator/=(const self& x) { m /= x.m; return *this; }

 operator complex<T>() const { return m; }

 // открытые функции-члены

 T rho() const { return abs(m); }

 T theta() const { return arg(m); }

 // бинарные операции

 friend self operator+(self x, const self& y) { return x += y; }

 friend self operator-(self x, const self& y) { return x -= y; }

 friend self operator*(self x, const self& y) { return x *= y; }

 friend self operator/(self x, const self& y) { return x /= y; }

 // операторы сравнения

 friend bool operator==(const self& x, const self& y) { return x.m == y.m; }

 friend bool operator!=(const self& x, const self& y) { return x.m ! = y.m; }

private:

 complex<T> m;

};

typedef BasicPolar<double> Polar;

int main() {

 double rho = 3.0; // длина

 double theta = 3.141592 / 2; // угол

 Polar coord(rho, theta);

 cout << "rho = " << coord.rho() << ", theta = " << coord.theta() << endl;

 coord += Polar(4.0, 0.0);

 cout << "rho = " << coord.rho() << ", theta = " << coord.theta() << endl;

 system("pause");

}

В примере 11.35 с помощью typedef я определил тип Polar как специализацию шаблона BasicPolar. Так удобно определять используемый по умолчанию тип, однако вы можете при необходимости специализировать шаблон BasicPolar другим числовым типом. Такой подход используется в стандартной библиотеке в отношении классе string, который является специализацией шаблона basic_string.

11.19. Выполнение операций с битовыми наборами

Проблема

Требуется реализовать основные арифметические операции и операции сравнения для набора бит, рассматривая его как двоичное представление целого числа без знака.

Решение

Программный код примера 11.36 содержит функции, которые позволяют выполнять арифметические операции и операции сравнения с шаблоном класса bitset из заголовочного файла <bitset>, рассматривая его как целый тип без знака.

Пример 11.36. bitset_arithmetic.hpp

#include <stdexcept>

#include <bitset>

bool fullAdder(bool b1, bool b2, bool& carry) {

 bool sum = (b1 ^ b2) ^ carry;

 carry = (b1 && b2) || (b1 && carry) || (b2 && carry);

 return sum;

}

bool fullSubtractor(bool b1, bool b2, bool& borrow) {

 bool diff;

 if (borrow) {

  diff = !(b1 ^ b2);

  borrow = !b1 || (b1 && b2);

 } else {

  diff = b1 ^ b2;

  borrow = !b1 && b2;

 }

 return diff;

}

template<unsigned int N>

bool bitsetLtEq(const std::bitset<N>& x, const std::bitset<N>& y) {

 for (int i=N-1; i >= 0; i--) {

  if (x[i] && !y[i]) return false;

  if (!x[i] && y[i]) return true;

 }

 return true;

}

template<unsigned int N>

bool bitsetLt(const std::bitset<N>& x, const std::bitset<N>& y) {

 for (int i=N-1; i >= 0, i--) {

  if (x[i] && !y[i]) return false;

  if (!x[i] && y[i]) return true;

 }

 return false;

}

template<unsigned int N>

bool bitsetGtEq(const std::bitset<N>& x, const std::bitset<N>& y) {

 for (int i=N-1; i >= 0; i--) {

  if (x[i] && !y[i]) return true;

  if (!x[i] && y[i]) return false;

 }

 return true;

}

template<unsigned int N>

bool bitsetGt(const std::bitset<N>& x, const std::bitset<N>& y) {

 for (int i=N-1; i >= 0; i--) {

  if (x[i] && !y[i]) return true;

  if (!x[i] && y[i]) return false;

 }

 return false;

}

template<unsigned int N>

void bitsetAdd(std::bitset<N>& x, const std::bitset<N>& y) {

 bool carry = false;

 for (int i = 0; i < N; i++) {

  x[i] = fullAdder(x[i], y[x], carry);

 }

}

template<unsigned int N>

void bitsetSubtract(std::bitset<N>& x, const std::bitset<N>& y) {

 bool borrow = false;

 for (int i = 0; i < N; i++) {

  if (borrow) {

   if (x[i]) {

    x[i] = y[i];

    borrow = y[i];

   } else {

    x[i] = !y[i];

    borrow = true;

   }

  } else {

   if (x[i]) {

    x[i] = !y[i];

    borrow = false;

   } else {

    x[i] = y[i];

    borrow = y[i];

   }

  }

 }

}

template<unsigned int N>

void bitsetMultiply(std::bitset<N>& x, const std::bitset<N>& y) {

 std::bitset<N> tmp = x;

 x.reset();

 // мы хотим минимизировать количество операций сдвига и сложения

 if (tmp.count() < y.count()) {

  for (int i=0; i < N; i++) if (tmp[i]) bitsetAdd(x, у << i);

 } else {

  for (int i=0; i < N; i++) if (y[i]) bitsetAdd(x, tmp << i);

 }

}

template<unsigned int N>

void bitsetDivide(std::bitset<N> x, std::bitset<N> y,

 std::bitset<N>& q, std::bitset<N>& r) {

 if (y.none()) {

  throw std::domain_error("division by zero undefined");

 }

 q.reset();

 r.reset();

 if (x.none()) {

  return;

 }

 if (x == y) {

  q[0] = 1;

  return;

 }

 r = x;

 if (bitsetLt(x, y)) {

  return;

 }

 // подсчитать количество значащих цифр в делителе и делимом

 unsigned int sig_x;

 for (int i=N-1; i>=0; i--) {

  sig_x = i;

  if (x[i]) break;

 }

 unsigned int sig_y;

 for (int i=N-1; i>=0; i--) {

  sig_y = i;

  if (y[i]) break;

 }

 // выровнять делитель по отношению к делимому

 unsigned int n = (sig_x — sig_y);

 y <<= n;

 // обеспечить правильное число шагов цикла

 n += 1;

 // удлиненный алгоритм деления со сдвигом и вычитанием

 while (n--) {

  // сдвинуть частное влево

  if (bitsetLtEq(y, r)) {

   // добавить новую цифру к частному

   q[n] = true;

   bitset.Subtract(r, y);

  }

  // сдвинуть делитель вправо

  y >>= 1;

 }

}

Пример 11.37 показывает, как можно использовать заголовочный файл bitset_arithmetic.hpp.

Пример 11.37. Применение функций bitset_arithmetic.hpp

#include "bitset_arithmetic.hpp"

#include <bitset>

#include <iostream>

#include <string>

using namespace std;

int main() {

 bitset<10> bits1(string("100010001"));

 bitset<10> bits2(string("000000011"));

 bitsetAdd(bits1, bits2);

 cout << bits1.to_string<char, char_traits<char>, allocator<char> >() << endl;

}

Программа примера 11.37 выдает следующий результат.

0100010100

Обсуждение

Шаблон класса bitset содержит основные операции по манипулированию битовыми наборами, но не обеспечивает арифметические операции и операции сравнения. Это объясняется тем, что в библиотеке нельзя заранее точно предвидеть, какой числовой тип будет использоваться для представления произвольного битового набора согласно ожиданиям программиста.

В функциях примера 11.36 считается, что bitset представляет собой целый тип без знака, и здесь обеспечиваются операции сложения, вычитания, умножения, деления и сравнения. Эти функции могут составить основу для представления специализированных целочисленных типов, и именно для этого они используются в рецепте 11.20.