Модель "Камень, ножницы, бумага"

Написана с помощью метода двойной диспетчеризации.

#include <iostream>

class Rock;
class Paper;
class Scissors;
class Item;

enum Outcome {WIN, LOSE, DRAW};

class Item {
public:
  virtual Outcome hit(Rock&) = 0;
  virtual Outcome hit(Paper&) = 0;
  virtual Outcome hit(Scissors&) = 0;
  virtual Outcome hit(Item&) = 0;
};

class Rock: public Item {
  virtual Outcome hit(Rock& r) {
    return DRAW;
  }

  virtual Outcome hit(Paper& p) {
    return LOSE;
  }

  virtual Outcome hit(Scissors& p) {
    return WIN;
  }

  virtual Outcome hit(Item& i) {
    return i.hit(*this);
  }
};

class Paper: public Item {
  virtual Outcome hit(Rock& r) {
    return WIN;
  }

  virtual Outcome hit(Paper& p) {
    return DRAW;
  }

  virtual Outcome hit(Scissors& p) {
    return LOSE;
  }

  virtual Outcome hit(Item& i) {
    return i.hit(*this);
  }
};

class Scissors: public Item {
  virtual Outcome hit(Rock& r) {
    return LOSE;
  }

  virtual Outcome hit(Paper& p) {
    return WIN;
  }

  virtual Outcome hit(Scissors& p) {
    return DRAW;
  }

  virtual Outcome hit(Item& i) {
    return i.hit(*this);
  }
};

Outcome Compete(Item* a, Item* b) {
  return a->hit(*b);
}

// Quick test:
int main() {
  Rock r;
  Paper p;
  Scissors s;
  std::cout << "Rock vs Paper: " << Compete(&r, &p) << std::endl;
  std::cout << "Scissors vs Paper: " << Compete(&s, &p) << std::endl;
  std::cout << "Rock vs Rock: " << Compete(&r, &r) << std::endl;
  return 0;
}

Аллокатор для объектов маленького размера.

Написан под влиянием книги Александреску.

#include <vector>
#include <algorithm>
#include <iostream>

using std::vector;

const unsigned char kBlocksInChunk = 128;
const size_t kMaxSizeOfSmallObject = 32;
const size_t kBlockSize = 64;

struct Chunk {
  unsigned char* data_;
  unsigned char first_available_block_;
  unsigned char available_blocks_count_;

  void Init(size_t block_size, unsigned char blocks_count) {
    data_ = static_cast<unsigned char*>(::operator new(block_size *
                                                       blocks_count));
    first_available_block_ = 0;
    available_blocks_count_ = blocks_count;
    unsigned char* tmp_data = data_;
    for (unsigned char i = 0; i != blocks_count; ++i) {
      *tmp_data = i;
      tmp_data += block_size;
    }
  }

  void* Allocate(size_t block_size) {
    if (available_blocks_count_ == 0) {
      return NULL;
    }
    unsigned char * result = data_ + first_available_block_ * block_size;
    first_available_block_ = *result;
    --available_blocks_count_;
    return result;
  }

  void Deallocate(void* p, size_t block_size) {
    // Pointer not in chunk.
    if (p < data_) {
      return;
    }
    unsigned char * to_release = static_cast<unsigned char*>(p);
    // Alignment check.
    if ((to_release - data_) % block_size != 0) {
      return;
    }
    *to_release = first_available_block_;
    first_available_block_ = static_cast<unsigned char>((to_release - data_) /
                                                        block_size);
    ++available_blocks_count_;
  }

  void Release() {
    ::operator delete(data_);
  }

  bool operator ==(const Chunk& other) const {
    return (data_ == other.data_) &&
        (first_available_block_ == other.first_available_block_) &&
        (available_blocks_count_ == other.available_blocks_count_);
  }
};

class FixedAllocator {
private:
  friend class SmallObjAllocator;

  size_t block_size_;
  unsigned char blocks_num_;
  vector<Chunk> chunks_;
  Chunk* alloc_chunk_;
  Chunk* dealloc_chunk_;

public:
  FixedAllocator(size_t block_size, unsigned char block_num):
    block_size_(block_size), blocks_num_(block_num), alloc_chunk_(NULL),
    dealloc_chunk_(NULL) {}

  void* Allocate() {
    if (alloc_chunk_ == NULL ||
        alloc_chunk_->available_blocks_count_ == 0) {
      // Seek for another chunk.
      bool is_found = false;
      for (vector<Chunk>::iterator it = chunks_.begin();
           it != chunks_.end(); ++it) {
        if (it->available_blocks_count_ > 0) {
          // New chunk is found.
          alloc_chunk_ = &(*it);
          is_found = true;
          break;
        }
      }
      if (!is_found) {
        // Add new chunk.
        Chunk new_chunk;
        new_chunk.Init(block_size_, blocks_num_);
        chunks_.push_back(new_chunk);
        alloc_chunk_ = &(chunks_.back());
        dealloc_chunk_ = &(chunks_.back());
      }
    }
    return alloc_chunk_->Allocate(block_size_);
  }

  void Deallocate(void* p) {
    Chunk* found_chunk = NULL;
    if (dealloc_chunk_ != NULL && p >= dealloc_chunk_->data_ &&
        p < dealloc_chunk_->data_ + block_size_ * blocks_num_) {
      found_chunk = dealloc_chunk_;
    } else {
      // Find chunk.
      for (vector<Chunk>::iterator it = chunks_.begin();
           it != chunks_.end(); ++it) {
        if (p >= it->data_ && p < it->data_ + block_size_ * blocks_num_) {
          // Chunk is found.
          found_chunk = &(*it);
          break;
        }
      }
    }
    found_chunk->Deallocate(p, block_size_);
    if (found_chunk->available_blocks_count_ == blocks_num_) {
      // Chunk is free. Erase it.
      vector<Chunk>::iterator to_delete = std::find(chunks_.begin(),
                                                    chunks_.end(),
                                                    *found_chunk);
      to_delete->Release();
      chunks_.erase(to_delete);
    }
  }
};

class SmallObjAllocator {
public:
  SmallObjAllocator(size_t chunk_size, size_t max_obj_size):
    chunk_size_(chunk_size), max_obj_size_(max_obj_size) {}

  void* Allocate(size_t sz) {
    if (sz > max_obj_size_) {
      return ::operator new(sz);
    }
    // Find FixedAllocator.
    FixedAllocator* found_allocator = NULL;
    for (vector<FixedAllocator>::iterator it = pool_.begin();
         it != pool_.end(); ++it) {
      if (it->block_size_ == sz) {
        found_allocator = &(*it);
        break;
      }
    }
    if (found_allocator == NULL) {
      // FixedAllocator is not found.
      // Add new FixedAllocator.
      pool_.push_back(FixedAllocator(chunk_size_, kBlocksInChunk));
      found_allocator = &(pool_.back());
    }

    return found_allocator->Allocate();
  }

  void Deallocate(void* p, size_t sz) {
    if (sz > max_obj_size_) {
      ::operator delete(p);
      return;
    }
    // Find FixedAllocator.
    FixedAllocator* found_allocator = NULL;
    for (vector<FixedAllocator>::iterator it = pool_.begin();
         it != pool_.end(); ++it) {
      if (it->block_size_ == sz) {
        found_allocator = &(*it);
        break;
      }
    }
    if (found_allocator == NULL) {
      // FixedAllocator not found!!!
      return;
    }
    found_allocator->Deallocate(p);
  }

private:
  vector<FixedAllocator> pool_;
  size_t chunk_size_;
  size_t max_obj_size_;
};

class SmallObjAllocatorSingleton {
public:
  static SmallObjAllocator* getInstance() {
    static SmallObjAllocator* instance_ = NULL; // The only instance.
    if (instance_ == NULL) {
      instance_ = new SmallObjAllocator(kBlockSize, kMaxSizeOfSmallObject);
    }
    return instance_;
  }
private:
  SmallObjAllocatorSingleton(); // No new objects.
  SmallObjAllocatorSingleton(const SmallObjAllocatorSingleton&); // No copies.
};

class SmallObject {
public:
  static void* operator new(size_t sz) {
    return SmallObjAllocatorSingleton::getInstance()->Allocate(sz);
  }

  static void operator delete(void* p, size_t sz) {
    SmallObjAllocatorSingleton::getInstance()->Deallocate(p, sz);
  }

  virtual ~SmallObject() {}
};

// STL Allocator
template <class T> class small_obj_allocator {
private:
  SmallObjAllocator soa;
public:
  typedef T value_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef T* pointer;
  typedef const T* const_pointer;
  typedef T& reference;
  typedef const T& const_reference;

  pointer address(reference r) const {
    return &r;
  }
  const_pointer address(const_reference r) const {
    return &r;
  }

  small_obj_allocator() throw():
    soa(SmallObjAllocator(kBlockSize, kMaxSizeOfSmallObject)) {}

  template<class U> small_obj_allocator(const small_obj_allocator<U>& other)
  throw() {
    soa = other.soa;
  }

  ~small_obj_allocator() throw() {}

  // Allocate memory for n objects T:
  pointer allocate(size_type n) {
    soa.Allocate(n * sizeof(T));
  }

  void deallocate(pointer p, size_type n) {
    soa.Deallocate(p, n * sizeof(T));
  }

  void construct(pointer p, const T& val) {
    new(static_cast<void*>(p)) T(val);
  }

  void destroy(pointer p) {
    p->~T();
  }

  size_type max_size() const throw() {
    return 100 * 1024 * 1024; // 100 MB
  }

  template<class U> struct rebind {
    typedef small_obj_allocator<U> other;
  };
};

// Derivative from SmallObject example:
class ExampleObject: public SmallObject {
public:
  ExampleObject(int i): x(i) {
  }

  ~ExampleObject() {}

  int get_x() {
    return x;
  }

  void set_x(int i) {
    x = i;
  }

private:
  int x;
};

int main () {
  // ExampleObject test:
  vector<ExampleObject> vec;
  for (int i = 0; i < 10000; ++i) {
    vec.push_back(ExampleObject(i));
  }
  bool test_passed = true;
  int i = 0;
  for (vector<ExampleObject>::iterator it = vec.begin();
       it != vec.end(); ++it, ++i) {
    if (it->get_x() != i) {
      std::cout << "ExampleObject test failed :(" << std::endl;
      test_passed = false;
      break;
    }
  }
  if (test_passed) {
    std::cout << "ExampleObject test passed." << std::endl;
  }

  // STL allocator test:
  vector<int, small_obj_allocator<int> > vec2;
  for (i = 0; i < 10000; ++i) {
    vec2.push_back(i);
  }
  test_passed = true;
  i = 0;
  for (vector<int, small_obj_allocator<int> >::iterator it = vec2.begin();
       it != vec2.end(); ++it, ++i) {
    if (*it != i) {
      std::cout << "STL allocator test failed :(" << std::endl;
      test_passed = false;
      break;
    }
  }
  if (test_passed) {
    std::cout << "STL allocator test passed." << std::endl;
  }
  return 0;
}

Исключения

Собственный класс исключения CastException с перегруженным оператором << для записи в объект исключения и несколько примеров его использования.

#include <climits>
#include <cstring>
#include <exception>
#include <iostream>
#include <string>

using std::cout;
using std::endl;
using std::exception;
using std::string;

class CastException: public exception {
 protected:
  string message;
 public:
  virtual ~CastException () throw() {}

  virtual const char* what() const throw() {
    return message.c_str();
  }

  CastException& operator<< (const char* str) {
    message.append(str);
    return *this;
  }

  CastException& operator<< (const string str) {
    message += str;
    return *this;
  }
};

class TooBigStringException: public CastException {
 public:
  TooBigStringException() {
    message.append("Too big string!");
  }
};

class TooBigCharTypeException: public CastException {
 public:
  TooBigCharTypeException() {
    message.append("Too big CharType!");
  }
};

class IncorrectSymbolException: public CastException {
 public:
  IncorrectSymbolException() {
    message.append("Incorrect symbol!");
  }
};

class OverflowException: public CastException {
 public:
  OverflowException() {
    message.append("Overflow!");
  }
};

class InvalidValueException: public CastException {
 public:
  InvalidValueException() {
    message.append("Invalid value!");
  }
};

template <typename CharType>
inline char CharFromString(const CharType* data, size_t len) {
  if (len > 1) {
    throw TooBigStringException();
  }
  if (sizeof(CharType) > sizeof(char)) {
    throw TooBigCharTypeException();
  }
  return static_cast<char>(*data);
}

bool addition_is_safe(int a, int b) {
  return INT_MAX - b >= a;
}

bool multiplication_is_safe(int a, int b) {
  return INT_MAX / b >= a;
}

template <typename CharType>
inline int IntFromString(const CharType* data, size_t len) {
  int res = 0;
  for (size_t i = 0; i < len; ++i) {
    if (static_cast<char>(data[i]) < '0' || static_cast<char>(data[i]) > '9') {
      throw IncorrectSymbolException();
    }
    if (!multiplication_is_safe(res, 10)) {
      throw OverflowException();
    }
    res *= 10;
    if (!addition_is_safe(res, static_cast<char>(data[i]) - '0')) {
      throw OverflowException();
    }
    res += static_cast<char>(data[i]) - '0';
  }
  return res;
}

bool addition_is_safe(long long a, long long b) {
  return LLONG_MAX - b >= a;
}

bool multiplication_is_safe(long long a, long long b) {
  return LLONG_MAX / b >= a;
}

template <typename CharType>
inline long long LongLongFromString(const CharType* data, size_t len) {
  long long res = 0;
  for (size_t i = 0; i < len; ++i) {
    if (static_cast<char>(data[i]) < '0' || static_cast<char>(data[i]) > '9') {
      throw IncorrectSymbolException();
    }
    if (!multiplication_is_safe(res, 10LL)) {
      throw OverflowException();
    }
    res *= 10;
    if (!addition_is_safe(res, static_cast<long long>(data[i]) - '0')) {
      throw OverflowException();
    }
    res += static_cast<long long>(data[i]) - '0';
  }
  return res;
}

template <typename CharType>
inline bool BoolFromString(const CharType* data, size_t len) {
  if (len == 1) {
    if (*data == '0') {
      return false;
    } else if (*data == '1') {
      return true;
    } else {
      throw IncorrectSymbolException();
    }
  } else if (len == 4 && strncmp(data, "true", 4) == 0) {
    return true;
  } else if (len == 5 && strncmp(data, "false", 5) == 0) {
    return false;
  } else {
    throw InvalidValueException();
  }
}

int main() {
  cout << "From \"a\" to char: ";
  try {
    cout << CharFromString<char>("a", 1) << endl;
  } catch (CastException& ex) {
    cout << ex.what() << endl;
  }
  cout << "From \"ab\" to char: ";
  try {
    cout << CharFromString<char>("ab", 2) << endl;
  } catch (CastException& ex) {
    cout << ex.what() << endl;
  }

  cout << "From 42 to int: ";
  try {
    cout << IntFromString<char>("42", 2) << endl;
  } catch (CastException& ex) {
    cout << ex.what() << endl;
  }
  cout << "From 2147483648 (INT_MAX + 1) to int: ";
  try {
    cout << IntFromString<char>("2147483648", 10) << endl;
  } catch (CastException& ex) {
    cout << ex.what() << endl;
  }

  cout << "From 7500 to long long: ";
  try {
    cout << LongLongFromString<char>("7500", 4) << endl;
  } catch (CastException& ex) {
    cout << ex.what() << endl;
  }
  cout << "From \"STR_NOT_NUM\" to long long: ";
  try {
    cout << LongLongFromString<char>("STR_NOT_NUM", 11) << endl;
  } catch (CastException& ex) {
    cout << ex.what() << endl;
  }

  cout << "From \"true\" to bool: ";
  try {
    cout << BoolFromString<char>("true", 4) << endl;
  } catch (CastException& ex) {
    cout << ex.what() << endl;
  }
  cout << "From \"1234\" to bool: ";
  try {
    cout << BoolFromString<char>("1234", 4) << endl;
  } catch (CastException& ex) {
    cout << ex.what() << endl;
  }
  return 0;
}

Умный указатель.

Реализация умного указателя, написанная под влиянием книги Александреску.

#include <cassert>
#include <iostream>
#include <vector>

template <typename T> class ElementStorageStrategy;
template <typename T> class ArrayStorageStrategy;

template <typename T, template <typename T> class StorageStrategy>
  class NoCopyingOwnershipStrategy;
template <typename T, template <typename T> class StorageStrategy>
  class CounterSimpleOwnershipStrategy;
template <typename T, template <typename T> class StorageStrategy>
  class CounterListOwnershipStrategy;
template <typename T, template <typename T> class StorageStrategy>
  class DestructiveCopyingOwnershipStrategy;

template <typename T,
          template <typename T> class StorageStrategy = ElementStorageStrategy,
          template <typename T, template <typename T> class StorageStrategy >
          class OwnershipStrategy = NoCopyingOwnershipStrategy>
class SmartPointer {
 private:
  T* pointer_;
  OwnershipStrategy<T, StorageStrategy > ownership_;
 public:
  SmartPointer() {}

  explicit SmartPointer(T* pointer) : pointer_(pointer) {}

  SmartPointer(SmartPointer& other) {
    pointer_ = NULL;
    ownership_.Assign(*this, other);
  }

  SmartPointer& operator=(const SmartPointer& other) {
    if (pointer_ != other.pointer_) {
      ownership_.Assign(*this, other);
    }
    return *this;
  }

  // Ambigious casting to prevent delete:
  operator T*() {
    return pointer_;
  }

  operator void*() {
    return pointer_;
  }

  // Comparsion operators:
  bool operator!() const {  // For cases "if (!sp) ..."
    return pointer_ == 0;
  }

  inline friend bool operator==(const SmartPointer& lhs,
                                const SmartPointer& rhs) {
    return lhs.pointer_ == rhs.pointer_;
  }

  inline friend bool operator==(const SmartPointer& lhs, const T* rhs) {
    return lhs.pointer_ == rhs;
  }

  inline friend bool operator==(const T* lhs, const SmartPointer& rhs) {
    return lhs == rhs.pointer_;
  }

  inline friend bool operator!=(const SmartPointer& lhs,
                                const SmartPointer& rhs) {
    return lhs.pointer_ != rhs.pointer_;
  }

  inline friend bool operator!=(const SmartPointer& lhs, const T* rhs) {
    return lhs.pointer_ != rhs;
  }

  inline friend bool operator!=(const T* lhs, const SmartPointer& rhs) {
    return lhs != rhs.pointer_;
  }

  // And template comparsion operators for cases like:
  //
  // SmartPointer<Base> sp;
  // Derived* p;
  // ...
  // if (sp == p) {}
  template <typename R>
  inline friend bool operator==(const SmartPointer& lhs, const R* rhs) {
    return lhs.pointer_ == rhs;
  }

  template <typename R>
  inline friend bool operator==(const R* lhs, const SmartPointer& rhs) {
    return lhs == rhs.pointer_;
  }

  template <typename R>
  inline friend bool operator!=(const SmartPointer& lhs, const R* rhs) {
    return lhs.pointer_ != rhs;
  }

  template <typename R>
  inline friend bool operator!=(const R* lhs, const SmartPointer& rhs) {
    return lhs != rhs.pointer_;
  }

  ~SmartPointer() {
    ownership_.Release(*this);
  }

  T& operator*() const {
    return *pointer_;
  }

  T* operator->() const {
    return pointer_;
  }

  friend T* GetImplPtr(SmartPointer& sp) {
    return sp.pointer_;
  }

  friend void SetImplPtr(SmartPointer& dst, SmartPointer& src) {
    dst.pointer_ = src.pointer_;
  }

  friend void SetImplPtr(SmartPointer& sp, T* ptr) {
    sp.pointer_ = ptr;
  }

  friend OwnershipStrategy<T, StorageStrategy>& GetImplOwn(SmartPointer& sp) {
    return sp.ownership_;
  }
};

template <typename T>
class ElementStorageStrategy {
 public:
  static void Delete(T* ptr) {
    delete ptr;
  }
};

template <typename T>
class ArrayStorageStrategy {
 public:
  static void Delete(T* ptr) {
    delete[] ptr;
  }
};

template <typename T, template <typename T> class StorageStrategy>
class NoCopyingOwnershipStrategy {
 public:
  // Assign is not defined because it is prohibited in this strategy.
  void Assign(SmartPointer<T, StorageStrategy,
              NoCopyingOwnershipStrategy>& dst,
              SmartPointer<T, StorageStrategy,
              NoCopyingOwnershipStrategy>& src);

  void Release(SmartPointer<T, StorageStrategy,
               NoCopyingOwnershipStrategy>& smart_ptr) {
    StorageStrategy<T>::Delete(GetImplPtr(smart_ptr));
  }
};

template <typename T, template <typename T> class StorageStrategy>
class CounterSimpleOwnershipStrategy {
 private:
  unsigned int* counter_;
 public:
  CounterSimpleOwnershipStrategy() : counter_(new unsigned int(1)) {}

  void Assign(SmartPointer<T, StorageStrategy,
              CounterSimpleOwnershipStrategy>& dst,
              SmartPointer<T, StorageStrategy,
              CounterSimpleOwnershipStrategy>& src) {
    SetImplPtr(dst, src);
    ++*(GetImplOwn(src).counter_);
    delete GetImplOwn(dst).counter_;
    GetImplOwn(dst).counter_ = GetImplOwn(src).counter_;
  }

  void Release(SmartPointer<T, StorageStrategy,
               CounterSimpleOwnershipStrategy>& smart_ptr) {
    if (--*(GetImplOwn(smart_ptr).counter_) == 0) {
      StorageStrategy<T>::Delete(GetImplPtr(smart_ptr));
      delete counter_;
    }
  }
};

template <typename T, template <typename T> class StorageStrategy>
class CounterListOwnershipStrategy {
 private:
  CounterListOwnershipStrategy<T, StorageStrategy> *prev_, *next_;
 public:
  CounterListOwnershipStrategy() : prev_(NULL), next_(NULL) {}

  void Assign(SmartPointer<T, StorageStrategy,
              CounterListOwnershipStrategy>& dst,
              SmartPointer<T, StorageStrategy,
              CounterListOwnershipStrategy>& src) {
    CounterListOwnershipStrategy<T, StorageStrategy> *last_ptr =
        &(GetImplOwn(src));
    while (last_ptr->next_ != NULL) {
      last_ptr = last_ptr->next_;
    }
    last_ptr->next_ = this;
    if (prev_ != NULL) {
      prev_->next_ = next_;
    }
    if (next_ != NULL) {
      next_->prev_ = prev_;
    }
    prev_ = last_ptr;
    next_ = NULL;
    SetImplPtr(dst, src);
  }

  void Release(SmartPointer<T, StorageStrategy,
               CounterListOwnershipStrategy>& smart_ptr) {
    CounterListOwnershipStrategy<T, StorageStrategy> *own_ptr =
        &GetImplOwn(smart_ptr);
    if (own_ptr->prev_ == NULL && own_ptr->next_ == NULL) {
      StorageStrategy<T>::Delete(GetImplPtr(smart_ptr));
    }
    if (own_ptr->prev_ != NULL) {
      own_ptr->prev_->next_ = own_ptr->next_;
    }
    if (own_ptr->next_ != NULL) {
      own_ptr->next_->prev_ = own_ptr->prev_;
    }
  }
};

template <typename T, template <typename T> class StorageStrategy>
class DestructiveCopyingOwnershipStrategy {
 public:
  void Assign(SmartPointer<T, StorageStrategy,
              DestructiveCopyingOwnershipStrategy>& dst,
              SmartPointer<T, StorageStrategy,
              DestructiveCopyingOwnershipStrategy>& src) {
    StorageStrategy<T>::Delete(GetImplPtr(dst));
    SetImplPtr(dst, src);
    SetImplPtr(src, NULL);
  }

  void Release(SmartPointer<T, StorageStrategy,
               DestructiveCopyingOwnershipStrategy>& smart_ptr) {
    StorageStrategy<T>::Delete(GetImplPtr(smart_ptr));
  }
};

int main() {
  // Tests
  // NoCopyingOwnershipStrategy:
  std::cout << "Testing NoCopyingOwnershipStrategy...";
  {
    int *my_int = new int(24);
    SmartPointer<int> sp1(new int(42));
    SmartPointer<int> sp2(my_int);
    assert(*sp1 == 42);
    assert(*sp2 == *my_int);
    assert(sp1 != sp2);
  }
  std::cout << "done" << std::endl;
  // CounterSimpleOwnershipStrategy:
  std::cout << "Testing CounterSimpleOwnershipStrategy...";
  {
    SmartPointer<int,
        ElementStorageStrategy,
        CounterSimpleOwnershipStrategy> sp1(new int(42));
    SmartPointer<int,
        ElementStorageStrategy,
        CounterSimpleOwnershipStrategy> sp2(sp1);
    assert(*sp1 == 42);
    assert(sp1 == sp2);
    std::vector<SmartPointer<int, ElementStorageStrategy,
        CounterSimpleOwnershipStrategy>*> my_vec;
    for (int i = 0; i < 1000; ++i) {
      my_vec.push_back(new SmartPointer<int, ElementStorageStrategy,
                       CounterSimpleOwnershipStrategy>(new int(i)));
    }
    for (int i = 0; i < 1000; ++i) {
      delete my_vec[i];
    }
  }
  std::cout << "done" << std::endl;
  // CounterListOwnershipStrategy:
  std::cout << "Testing CounterListOwnershipStrategy...";
  {
    SmartPointer<int,
        ElementStorageStrategy,
        CounterListOwnershipStrategy> sp1(new int(42));
    SmartPointer<int,
        ElementStorageStrategy,
        CounterListOwnershipStrategy> sp2(sp1);
    assert(*sp1 == 42);
    assert(sp1 == sp2);
    std::vector<SmartPointer<int, ElementStorageStrategy,
        CounterListOwnershipStrategy>*> my_vec;
    for (int i = 0; i < 1000; ++i) {
      my_vec.push_back(new SmartPointer<int, ElementStorageStrategy,
                       CounterListOwnershipStrategy>(new int(i)));
    }
    for (int i = 0; i < 1000; ++i) {
      delete my_vec[i];
    }
  }
  std::cout << "done" << std::endl;
  // DestructiveCopyingOwnershipStrategy
  std::cout << "Testing DestructiveCopyingOwnershipStrategy...";
  {
    SmartPointer<int,
        ElementStorageStrategy,
        DestructiveCopyingOwnershipStrategy> sp1(new int(42));
    SmartPointer<int,
        ElementStorageStrategy,
        DestructiveCopyingOwnershipStrategy> sp2(sp1);
    assert(sp2 != sp1);
    assert(!sp1);
  }
  std::cout << "done" << std::endl;
  std::cout << "All tests successfully passed." << std::endl;
  return 0;
}

Поиск кратчайшего пути в графе

Дан неориентированный граф, длины ребер в котором равны 0 или 1. Необходимо найти длину кратчайшего пути из вершины A в вершину B.
В первой строке входа задано 4 целых числа n, m, a, b количество вершин и ребер графа, номер вершины A и номер вершины B соответственно. Вершины пронумерованы от 1 до n. 1 ≤ m, n ≤ 100 000, 1 ≤ a, b ≤ n. В каждой из следующих m строк по три целых числа, первое из которых означает номер начальной вершины ребра, второе номер конечной вершины ребра, третье длину ребра (0 или 1).
Выведите длину кратчайшего пути из вершины A в вершину B . Если пути из A в B не существует, выведите -1.

#include <stdio.h>
#include <vector>
#include <algorithm>

using std::vector;
using std::swap;

const int kMaxDistance = 1000000;

struct NodeLengthPair {
  int node_;
  int length_;

  NodeLengthPair(int node, int length):
    node_(node), length_(length) {}
};

struct DistancePositionPair {
  int distance_;
  int heap_position_;
  DistancePositionPair(int distance, int heap_position):
    distance_(distance), heap_position_(heap_position) {}
};

void ReadInput(vector< vector<NodeLengthPair> >& graph_edges,
               int& source_node,
               int& destination_node) {
  int nodes_num, edges_num, source, destination;
  scanf("%d %d %d %d", &nodes_num, &edges_num, &source, &destination);
  graph_edges.resize(nodes_num);
  source_node = source - 1;
  destination_node = destination - 1;
  int node_from, node_to, length;
  for (int counter = 0; counter < edges_num; ++counter) {
    scanf("%d %d %d", &node_from, &node_to, &length);
    graph_edges[node_from - 1].push_back(NodeLengthPair(node_to - 1, length));
    graph_edges[node_to - 1].push_back(NodeLengthPair(node_from - 1, length));
  }
}

void Heapify(int root_index,
             vector<int>& nodes_heap,
             vector<DistancePositionPair>& distance) {
  int left_son_index, right_son_index, smallest_index;
  left_son_index = 2 * root_index + 1;
  right_son_index = 2 * root_index + 2;
  smallest_index = root_index;
  if (left_son_index < nodes_heap.size() &&
      distance[nodes_heap[left_son_index]].distance_ <
          distance[nodes_heap[smallest_index]].distance_) {
    smallest_index = left_son_index;
  }
  if (right_son_index < nodes_heap.size() &&
      distance[nodes_heap[right_son_index]].distance_ <
          distance[nodes_heap[smallest_index]].distance_) {
    smallest_index = right_son_index;
  }
  if (smallest_index != root_index) {
    swap(distance[nodes_heap[root_index]].heap_position_,
         distance[nodes_heap[smallest_index]].heap_position_);
    swap(nodes_heap[root_index], nodes_heap[smallest_index]);
    Heapify(smallest_index, nodes_heap, distance);
  }
}

void MakeHeap(vector<int>& nodes_heap,
              vector<DistancePositionPair>& distance) {
  for (int counter = nodes_heap.size() / 2; counter >= 0; --counter) {
    Heapify(counter, nodes_heap, distance);
  }
}

int ExtractMin(vector<int>& nodes_heap,
               vector<DistancePositionPair>& distance) {
  int min = nodes_heap.front();
  nodes_heap.front() = nodes_heap.back();
  nodes_heap.pop_back();
  distance[nodes_heap.front()].heap_position_ = 0;
  Heapify(0, nodes_heap, distance);
  return min;
}

void ShiftUp(int index,
            vector<int>& nodes_heap,
            vector<DistancePositionPair>& distance) {
  if (index == 0) {
    return;
  }
  int parent_index = index % 2 == 0 ? (index - 2) / 2 : index / 2;
  if (distance[nodes_heap[parent_index]].distance_ >
          distance[nodes_heap[index]].distance_) {
    swap(distance[nodes_heap[parent_index]].heap_position_,
         distance[nodes_heap[index]].heap_position_);
    swap(nodes_heap[parent_index], nodes_heap[index]);
    ShiftUp(parent_index, nodes_heap, distance);
  }
}

int FindMinPath(const vector< vector<NodeLengthPair> >& graph_edges,
              int source_node,
              int destination_node) {
  vector<DistancePositionPair> distance(graph_edges.size(),
      DistancePositionPair(kMaxDistance, 0));
  distance[source_node].distance_ = 0;
  vector<int> nodes_heap(graph_edges.size());
  for (int counter = 0; counter < nodes_heap.size(); ++counter) {
    nodes_heap[counter] = counter;
    distance[counter].heap_position_ =  counter;
  }
  MakeHeap(nodes_heap, distance);
  int current_node;
  while (!nodes_heap.empty()) {
    current_node = ExtractMin(nodes_heap, distance);
    if (current_node == destination_node) {
      break;
    }
    for (vector<NodeLengthPair>::const_iterator adjanced_it =
             graph_edges[current_node].begin();
         adjanced_it != graph_edges[current_node].end();
         ++adjanced_it) {
      if (distance[adjanced_it->node_].distance_ >
              distance[current_node].distance_ + adjanced_it->length_) {
        distance[adjanced_it->node_].distance_ =
            distance[current_node].distance_ + adjanced_it->length_;
        ShiftUp(distance[adjanced_it->node_].heap_position_,
                nodes_heap,
                distance);
      }
    }
  }
  return distance[destination_node].distance_ == kMaxDistance ?
        -1 : distance[destination_node].distance_;
}

int main() {
  vector< vector<NodeLengthPair> > graph_edges;
  int source_node, destination_node;
  ReadInput(graph_edges, source_node, destination_node);
  printf("%d\n", FindMinPath(graph_edges, source_node, destination_node));
  return 0;
}

Поиск моста в неориентированном графе

Хонти хочет начать войну против Пандеи. План Хонти состоит в том, чтобы используя эффект неожиданности навести ужас на пандейцев, создать хаос, и в этих условиях быстро завоевать страну. Чтобы успешно воплотить этот план в жизнь, хонтийцам необходимо провести первую, самую важную операцию.
Цель операции разделить Пандею на две несвязанные части, разрушив всего лишь
одну дорогу (изначально карта Пандеи представляет собой связный граф). Хонтийская разведка уже добыла карты Пандеи, передала их экспертам, которые провели исследование и выяснили стоимость разрушения каждой из дорог страны-противника. Вам передали карту всех дорог вместе со стоимостями их разрушения. Вам нужно выбрать самую дешевую дорогу, удовлетворяющую запросам хонтийцев: предстоящая война еще потребует значительных ресурсов.
В первой строке входа заданы два целых числа n и m количество городов и количество дорог Пандеи соответственно. Дороги в Пандее двусторонние. В каждой из следующих m строк по три числа a, b и c номера начального и конечного горо дов дороги (города нумеруются с единицы) и стоимость разрушения данной дороги. 1 ≤ m, n ≤ 50 000. 1 ≤ a, b ≤ n. a = b. 1 ≤ c ≤ 1 000 000 000.
Выведите единственное число наименьшую стоимость дороги, которую можно разрушить, чтобы нарушить связность Пандеи. Если таких дорог не существует, выведите -1.

Проводится поиск в ширину, чтобы найти так называемые "мосты" - ребра, удаление которых, делает граф несвязным. Затем выбирается тот мост, разрушение которого самое дешевое.

#include<stdio.h>
#include<stack>
#include<vector>
#include<algorithm>

struct NodeCostPair {
  int node_;
  int cost_;

  NodeCostPair(int node, int cost):
    node_(node), cost_(cost) {}
};

struct ReturnInfo {
  int current_node_;
  int prev_node_;
  std::vector<NodeCostPair>::const_iterator node_it_;

  ReturnInfo(int current_node,
             int prev_node,
             std::vector<NodeCostPair>::const_iterator node_it):
    current_node_(current_node), prev_node_(prev_node), node_it_(node_it) {}
};

struct Edge {
  int node_from_;
  int node_to_;
  int cost_;

  Edge(int node_from, int node_to, int cost):
    node_from_(node_from), node_to_(node_to), cost_(cost) {}
};

enum Colors {
  WHITE = 0,
  GRAY = 1,
  BLACK = 2
};

template <typename T>
const T& min3(const T& a, const T& b, const T& c) {
  return std::min(a, std::min(b, c));
}

const int kMaxNodesNumber = 100000;

void DFS(const std::vector< std::vector<NodeCostPair> >& graph_edges,
         std::vector<int>& times_in,
         std::vector<int>& min_enter_time,
         std::vector<Edge>& dfs_edges) {
  std::stack<ReturnInfo> stack_nodes;
  std::vector<char> colors(graph_edges.size(), 0);
  int current_node = 0;  // Begin from the node 0.
  int prev_node = -1;
  int timer = 0;
  times_in.resize(graph_edges.size(), kMaxNodesNumber);
  times_in[0] = timer;
  min_enter_time.resize(graph_edges.size(), kMaxNodesNumber);
  bool go_deeper;
  bool exist_not_visited_nodes = true;
  std::vector<NodeCostPair>::const_iterator node_next_to_visit =
      graph_edges[current_node].begin();
  while (exist_not_visited_nodes) {
    colors[current_node] = GRAY;
    go_deeper = false;
    for (/* Loop initialization not needed. */;
         node_next_to_visit != graph_edges[current_node].end();
         ++node_next_to_visit) {
      if (node_next_to_visit->node_ != prev_node &&
          colors[node_next_to_visit->node_] == GRAY) {
        // Back edge.
        min_enter_time[current_node]
            = min3(times_in[node_next_to_visit->node_],
                   times_in[current_node],
                   min_enter_time[current_node]);
      }
      if (colors[node_next_to_visit->node_] == BLACK) {
        // Tree edge.
        min_enter_time[current_node]
            = min3(min_enter_time[node_next_to_visit->node_],
                   min_enter_time[current_node],
                   times_in[current_node]);
      }
      if (colors[node_next_to_visit->node_] == WHITE) {
        dfs_edges.push_back(Edge(current_node,
                                 node_next_to_visit->node_,
                                 node_next_to_visit->cost_));
        stack_nodes.push(ReturnInfo(current_node,
                                    prev_node,
                                    node_next_to_visit));
        prev_node = current_node;
        current_node = node_next_to_visit->node_;
        node_next_to_visit = graph_edges[current_node].begin();
        ++timer;
        times_in[current_node] = min_enter_time[current_node] = timer;
        go_deeper = true;
        break;
      }
    }
    if (!go_deeper) {
      colors[current_node] = BLACK;
      if (stack_nodes.empty()) {
        exist_not_visited_nodes = false;
      } else {
        // Return to the previous node
        current_node = stack_nodes.top().current_node_;
        prev_node = stack_nodes.top().prev_node_;
        node_next_to_visit = stack_nodes.top().node_it_;
        stack_nodes.pop();
      }
    }
  }
}

void ReadGraphEdges(std::vector< std::vector<NodeCostPair> >& graph_edges) {
  int nodes_num, edges_num;
  scanf("%d %d", &nodes_num, &edges_num);
  graph_edges.resize(nodes_num);
  int node_from, node_to, cost;
  for (int counter = 0; counter < edges_num; ++counter) {
    scanf("%d %d %d", &node_from, &node_to, &cost);
    graph_edges[node_from - 1].push_back(NodeCostPair(node_to - 1, cost));
    graph_edges[node_to - 1].push_back(NodeCostPair(node_from - 1, cost));
  }
}

const int kMinCost = -1;

int FindMinBridgeCost(const
                      std::vector< std::vector<NodeCostPair> >& graph_edges) {
  int min_cost = kMinCost;
  std::vector<int> times_in;
  std::vector<int> min_enter_time;
  std::vector<Edge> dfs_edges;
  DFS(graph_edges, times_in, min_enter_time, dfs_edges);
  for (std::vector<Edge>::const_iterator edge_it = dfs_edges.begin();
       edge_it != dfs_edges.end(); ++edge_it) {
    if (min_enter_time[edge_it->node_to_] > times_in[edge_it->node_from_]) {
      if (min_cost == -1) {
        min_cost = edge_it->cost_;
      } else {
        min_cost = std::min(min_cost, edge_it->cost_);
      }
    }
  }
  return min_cost;
}

int main() { 
  std::vector< std::vector<NodeCostPair> > graph_edges;
  ReadGraphEdges(graph_edges);
  printf("%d\n", FindMinBridgeCost(graph_edges));
  return 0;
}

Z-функция

Дана строка s. Нужно вычислить Z-функцию s - для каждого i от 1 до |s|.

Z[i]=max{j: 0 <= j <= |s| - i + 1, s[1..j] = s[i..i + j -1]}.

В единственной строке входа - строка s длиной не более 1 000 000 символов, состоящая из маленьких латинских букв.
В выходной файл выводится для каждого i от 1 до |s| число Z[i]. Числа разделены пробелами.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::max;

inline int LongestCommonPrefix(const string& input_string,
                       int first_start,
                       int second_start) {
  int index = 0;
  while (max(first_start + index, second_start + index) < input_string.size() &&
         input_string[first_start + index] ==
           input_string[second_start + index]) {
    ++index;
  }
  return index;
}

void ZFunction(const string& input_string, vector<int>& result_values) {
  result_values.resize(input_string.size());
  result_values[0] = input_string.size();
  int left_index = 0;
  int right_index = 0;
  int index;
  for (int current_index = 1; current_index < input_string.size();
       ++current_index) {
    if (current_index > right_index) {
      index = LongestCommonPrefix(input_string, 0, current_index);
      result_values[current_index] = index;
      left_index = current_index;
      right_index = current_index + index - 1;
    } else if (result_values[current_index - left_index] <
               right_index - current_index + 1) {
      result_values[current_index] = result_values[current_index - left_index];
    } else {
      index = LongestCommonPrefix(input_string, right_index + 1,
                                 right_index - current_index + 1) + 1;
      result_values[current_index] = right_index - current_index + index;
      left_index = current_index;
      right_index = right_index + index - 1;
    }
  }
}

void WriteOutput(const vector<int>& vec) {
  for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

int main() {
  string input_string;
  vector<int> z_function_values;
  cin >> input_string;
  ZFunction(input_string, z_function_values);
  WriteOutput(z_function_values);
  return 0;
}