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

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

#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;
}

Простейший SMTP клиент.

Принимает ip-адрес smtp сервера, как первый и единственный аргумент, проводит элементарную сессию из сообщений "HELO", затем "QUIT", пишет всю переписку в stdout.

#include <arpa/inet.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <unistd.h>
#include <string.h>
#include <cerrno>
#include <cstdlib>
#include <cstdio>

const int port_number = 25;

void ReadFromSocket(int socket_descriptor, char *server_answer, int len) {
  int num_bytes = read(socket_descriptor, server_answer, len);
  if (num_bytes < 0) {
    perror("ERROR reading socket");
    exit(EXIT_FAILURE);
  }
}

void WriteToSocket(int socket_descriptor, const char *msg, int len) {
  int num_bytes = write(socket_descriptor, msg, len);
  if (num_bytes < 0) {
    perror("ERROR writing socket");
    exit(EXIT_FAILURE);
  }
}

void SimpleSMTPSession(int socket_descriptor) {
  char buffer[256];
  ReadFromSocket(socket_descriptor, buffer, 255);
  printf("Server: %s", buffer);

  strcpy(buffer, "HELO CLIENT\n");
  WriteToSocket(socket_descriptor, buffer, strlen(buffer));
  printf("Client: %s", buffer);

  ReadFromSocket(socket_descriptor, buffer, 255);
  printf("Server: %s", buffer);

  strcpy(buffer, "QUIT\n");
  WriteToSocket(socket_descriptor, buffer, strlen(buffer));
  printf("Client: %s", buffer);

  ReadFromSocket(socket_descriptor, buffer, 255);
  printf("Server: %s", buffer);
}

void EstablishConnection(int *socket_descriptor, char *address) {
  *socket_descriptor = socket(AF_INET, SOCK_STREAM, 0);
  if (*socket_descriptor < 0) {
    perror("ERROR opening socket");
    exit(EXIT_FAILURE);
  }

  struct sockaddr_in server_address;
  memset(&server_address, 0, sizeof(server_address));
  server_address.sin_family = AF_INET;
  int pton_result = inet_pton(AF_INET, address, &(server_address.sin_addr));
  if (pton_result == 0) {
    printf("ERROR argument is not IP address\n");
    exit(EXIT_FAILURE);
  }
  if (pton_result < 0) {
    perror("ERROR argument is not valid IP address");
    exit(EXIT_FAILURE);
  }
  server_address.sin_port = htons(port_number);

  if (connect(*socket_descriptor,
              (struct sockaddr*)&server_address, sizeof(server_address)) < 0) {
    perror("ERROR connecting");
    exit(EXIT_FAILURE);
  }
}

void CloseConnection(int socket_descriptor) {
  if (close(socket_descriptor) < 0) {
    perror("ERROR socket closing");
    exit(EXIT_FAILURE);
  }
}

int main(int argc, char **argv) {
  if (argc != 2) {
    printf("Not enough arguments!\nUsage: %s ip_address\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  int socket_descriptor;
  EstablishConnection(&socket_descriptor, argv[1]);

  SimpleSMTPSession(socket_descriptor);

  CloseConnection(socket_descriptor);

  return 0;
}

Цитата

Ja! Diesem Sinne bin ich ganz ergeben,
Das ist der Weisheit letzter Schluss:
Nur der verdient sich Freiheit wie das Leben,
Der täglich sie erobern muss.

... Жизни годы
Прошли не даром; ясен предо мной
Конечный вывод мудрости земной:
Лишь тот достоин жизни и свободы,
Кто каждый день за них идёт на бой!

Скачать все ссылки со страницы.

# for i in `lynx --dump $url | awk '/http/{print $2}'`; do wget $i; done

Модель аллокатора с использованием кучи и двусвязного списка

В распоряжении у менеджера памяти находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера - обрабатывать запросы приложений на выделение и освобождение памяти. Запрос на выделение памяти имеет один параметр K. Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом наш менеджер выделяет память из самого длинного свободного блока, а если таких несколько, то из них он выбирает тот, у которого номер первой ячейки - наименьший. После этого выделенный ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется. Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T - запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется. Требуется написать симуляцию менеджера памяти, удовлетворяющую приведенным критериям.
Количество ячеек 1<=N<=2^(31)-1, количество запросов 1<=m<=10^5. На вход подаются числа N и M, а затем M чисел, если число положительное - выделение памяти, отрицательное - освобождение. Для каждого запроса на выделение памяти в выход выводится одно число на отдельной строке с результатом выполнения запроса. Если память была выделена, выводится номер первой ячейки памяти в выделенном блоке, иначе выводится -1.
Для хранения свободных отрезков используется куча с итераторами на отрезки из двусвязного списка, в котором хранятся все отрезки. Приведенное решение имеет асимптотику O(m log(m)).

#include <vector>
#include <list>
#include <algorithm>
#include <cstdio>

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

struct Chunk {
  int start_;
  int length_;
  bool is_free_;
  int index_;

  Chunk(int start = 0, int length = 0, bool is_free = false, int index = 0):
      start_(start), length_(length), is_free_(is_free), index_(index) {}

  bool operator <(const Chunk& other) const {
    if (length_ < other.length_) {
      return true;
    }
    if (length_ == other.length_) {
      return start_ > other.start_;
    }
    return false;
  }

  bool operator ==(const Chunk& other) const {
    return start_ == other.start_ && length_ == other.length_ &&
        is_free_ == other.is_free_ && index_ == other.index_;
  }

  bool operator >(const Chunk& other) const {
    return other < *this;
  }
};

class MaxChunkHeap {
private:
  vector<list<Chunk>::iterator> array;
public:
  bool empty() const {
    return array.empty();
  }

  void Heapify(int root_index) {
    int left_son_index, right_son_index, largest_index;
    left_son_index = 2 * root_index + 1;
    right_son_index = 2 * root_index + 2;
    largest_index = root_index;
    if (left_son_index < array.size() &&
        *(array[left_son_index]) > *(array[largest_index])) {
      largest_index = left_son_index;
    }
    if (right_son_index < array.size() &&
        *(array[right_son_index]) > *(array[largest_index])) {
      largest_index = right_son_index;
    }
    if (largest_index != root_index) {
      swap(array[root_index]->index_, array[largest_index]->index_);
      swap(array[root_index], array[largest_index]);
      Heapify(largest_index);
    }
  }

  void ChangeKey(int index, list<Chunk>::iterator new_key) {
    array[index] = new_key;
    new_key->index_ = index;
    Heapify(index);
    while (index > 0 && *(array[(index - 1) / 2]) < *(array[index])) {
      swap(array[(index - 1) / 2]->index_, array[index]->index_);
      swap(array[(index - 1) / 2], array[index]);
      index = (index - 1) / 2;
    }
  }

  void Insert(list<Chunk>::iterator new_key) {
    array.push_back(new_key);
    ChangeKey(array.size() - 1, new_key);
  }

  list<Chunk>::iterator GetMax() {
    return array[0];
  }

  list<Chunk>::iterator ExtractMax() {
    list<Chunk>::iterator max_element = array[0];
    array[0] = array[array.size() - 1];
    array[0]->index_ = 0;
    array.pop_back();
    Heapify(0);
    return max_element;
  }

  void Remove(int index) {
    if (array.empty())
      return;
    array[index] = array[array.size() - 1];
    array[index]->index_ = index;
    array.pop_back();
    ChangeKey(index, array[index]);
  }

  MaxChunkHeap() {}
};

class Allocator {
private:
  MaxChunkHeap memory_heap_;
  list<Chunk> chunks_list_;
  vector<list<Chunk>::iterator> allocated_chunks_;
  int operations_counter_;
public:
  Allocator(int size_of_memory) {
    chunks_list_.push_back(Chunk(1, size_of_memory , true, 0));
    memory_heap_.Insert(chunks_list_.begin());
    operations_counter_ = 0;
  }

  int allocateMemory(int size) {
    ++operations_counter_;
    allocated_chunks_.resize(operations_counter_, chunks_list_.end());

    if (memory_heap_.empty()) {
      return -1;
    }

    if (memory_heap_.GetMax()->length_ < size) {
      return -1;
    }

    list<Chunk>::iterator free_chunk = memory_heap_.ExtractMax();
    Chunk new_chunk(free_chunk->start_, size, false);
    allocated_chunks_[operations_counter_ - 1] =
        chunks_list_.insert(free_chunk, new_chunk);

    if (free_chunk->length_ == size) {
      chunks_list_.erase(free_chunk);
      return allocated_chunks_[operations_counter_ - 1]->start_;
    }

    free_chunk->length_ -= size;
    free_chunk->start_ += size;
    memory_heap_.Insert(free_chunk);
    return allocated_chunks_[operations_counter_ - 1]->start_;
  }

  void deallocateMemory(int num) {
    ++operations_counter_;
    if (allocated_chunks_[num - 1] == chunks_list_.end()) {
      return;
    }

    allocated_chunks_[num - 1]->is_free_ = true;

    // Merge with prev
    if (allocated_chunks_[num - 1] != chunks_list_.begin()) {
      list<Chunk>::iterator prev_chunk = allocated_chunks_[num - 1];
      --prev_chunk;
      if (prev_chunk->is_free_) {
        allocated_chunks_[num - 1]->length_ += prev_chunk->length_;
        allocated_chunks_[num - 1]->start_ = prev_chunk->start_;
        memory_heap_.Remove(prev_chunk->index_);
        chunks_list_.erase(prev_chunk);
      }
    }
    // Merge with next
    if (allocated_chunks_[num - 1] != --(chunks_list_.end())) {
      list<Chunk>::iterator next_chunk = allocated_chunks_[num - 1];
      ++next_chunk;
      if (next_chunk->is_free_) {
        allocated_chunks_[num - 1]->length_ += next_chunk->length_;
        memory_heap_.Remove(next_chunk->index_);
        chunks_list_.erase(next_chunk);
      }
    }

    memory_heap_.Insert(allocated_chunks_[num - 1]);
  }
};


void readInputToVector(vector<int> *vec) {
  int number_of_numbers, cur_number;
  scanf("%d", &number_of_numbers);
  for (int i = 0; i < number_of_numbers; ++i) {
    scanf("%d", &cur_number);
    vec->push_back(cur_number);
  }
}

void performRequests(const vector<int> &requests, vector<int> *output_vec,
                     Allocator *allocator) {
  for (vector<int>::const_iterator it = requests.begin(); it != requests.end();
  ++it) {
    if (*it > 0) {
      output_vec->push_back(allocator->allocateMemory(*it));
    }
    if (*it < 0) {
      allocator->deallocateMemory(-(*it));
    }
  }
}

void writeOutput(const vector<int> &vec) {
  for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
    printf("%d\n", *it);
  }
}

int main() {
  int size_of_memory;
  scanf("%d", &size_of_memory);
  Allocator allocator(size_of_memory);
  vector<int> requests;
  readInputToVector(&requests);
  vector<int> output_vec;
  performRequests(requests, &output_vec, &allocator);
  writeOutput(output_vec);
  return 0;
}

Универсальное хеширование

Реализован класс для хранения множества целых чисел. FixedSet при вызове Initialize получает набор целых чисел, который впоследствии и будет хранить. Набор чисел не будет изменяться с течением времени (до следующего вызова Initialize). Операция Contains возвращает true, если число number содержится в наборе. Мат. ожидание времени работы Initialize составляет O(n), где n - количество элементов в numbers. Затраты памяти порядка O(n). Операция Contains выполняется за O(1).

С помощью этого класса решается модельная задача: на входе дается множество различных чисел, а затем множество запросов - целых чисел. Для каждого запроса определяется, лежит ли число из запроса в множестве.

#include <cstdio>
#include <vector>
#include <cstdlib>

using std::vector;

const long long g_BigPrimeNumber = 2147483647;

inline long long hashFunction(long long a_coefficient,
                              long long b_coefficient,
                              long long x) {
  return (((a_coefficient * x + b_coefficient) % g_BigPrimeNumber) +
      g_BigPrimeNumber) % g_BigPrimeNumber;
}

inline void generateHashFunctionCoefficients(long long *a, long long *b) {
  *a = rand() % (g_BigPrimeNumber - 1) + 1;
  *b = rand() % g_BigPrimeNumber;
}

class FixedSet {
 private:
  struct PrimaryHashTable {
    long long a_coefficient_, b_coefficient_;  // Hash function coefficients.
    struct SecondaryHashTable {
      long long a_coefficient_, b_coefficient_;  // Hash function coefficients.
      vector<int> numbers_to_store;
      vector<int> numbers;
      vector<int> numbers_empty;  // numbers_empty[i] is true while numbers[i]
                                  // is empty

      SecondaryHashTable(): a_coefficient_(0), b_coefficient_(0) {}
    };

    vector<SecondaryHashTable> secondary_hash_tables_;

    // Returns number of cell needed to keep hash table.
    unsigned long long memoryToKeepNumbers() const {
      unsigned long long result = 0;
      for (vector<SecondaryHashTable>::const_iterator sht =
           secondary_hash_tables_.begin(); sht != secondary_hash_tables_.end();
           ++sht) {
        result += sht->numbers_to_store.size() * sht->numbers_to_store.size();
      }
      return result;
    }

    void cleanNumbersToStore() {
      for (vector<SecondaryHashTable>::iterator sht =
           secondary_hash_tables_.begin(); sht != secondary_hash_tables_.end();
           ++sht) {
        sht->numbers_to_store.clear();
      }
    }

    // Resizes each secondary hash table to numbers_of_numbers_^2 size and
    // generates coefficients a and b for it.
    void prepareSecondaryHashTables() {
      for (vector<SecondaryHashTable>::iterator sht_iter
           = secondary_hash_tables_.begin();
           sht_iter != secondary_hash_tables_.end(); ++sht_iter) {
        sht_iter->numbers.resize(sht_iter->numbers_to_store.size() *
                                   sht_iter->numbers_to_store.size());
        sht_iter->numbers_empty.resize(sht_iter->numbers_to_store.size() *
                                       sht_iter->numbers_to_store.size(), true);
        generateHashFunctionCoefficients(&(sht_iter->a_coefficient_),
                                         &(sht_iter->b_coefficient_));
      }
    }

    void fillHashTable() {
      for (vector<SecondaryHashTable>::iterator sht_iter
           = secondary_hash_tables_.begin();
           sht_iter != secondary_hash_tables_.end(); ++sht_iter) {
        bool success = false;
        while (!success) {
          generateHashFunctionCoefficients(&(sht_iter->a_coefficient_),
                                           &(sht_iter->b_coefficient_));
          // Clear stored numbers.
          sht_iter->numbers_empty.assign(sht_iter->numbers_empty.size(), true);
          // Try to refill secondary hash table.
          success = true;
          for (vector<int>::const_iterator number_iter =
               sht_iter->numbers_to_store.begin();
               number_iter != sht_iter->numbers_to_store.end(); ++number_iter) {
            long long hash_in_sht = hashFunction(sht_iter->a_coefficient_,
                                                 sht_iter->b_coefficient_,
                                                 *number_iter) %
              sht_iter->numbers_to_store.size();
            if (sht_iter->numbers_empty[hash_in_sht]) {
              sht_iter->numbers[hash_in_sht] = *number_iter;
              sht_iter->numbers_empty[hash_in_sht] = false;
            } else if (sht_iter->numbers[hash_in_sht] != *number_iter) {
              // Fail. Collision again.
              success = false;
              break;
            }
          }
        }
      }
    }
  } primary_hash_table_;

  int total_number_of_numbers_;

  static const int k_MemoryLimitMultiplier = 4;

 public:

  void preparePrimaryHashTable(const vector<int> &numbers) {
    primary_hash_table_.secondary_hash_tables_.resize(numbers.size());
    do {
      generateHashFunctionCoefficients(&(primary_hash_table_.a_coefficient_),
                                       &(primary_hash_table_.b_coefficient_));
      primary_hash_table_.cleanNumbersToStore();
      for (vector<int>::const_iterator it  = numbers.begin();
      it != numbers.end(); ++it) {
        primary_hash_table_.secondary_hash_tables_[hashFunction(
            primary_hash_table_.a_coefficient_,
            primary_hash_table_.b_coefficient_, *it) % numbers.size()].
              numbers_to_store.push_back(*it);
      }
    } while (primary_hash_table_.memoryToKeepNumbers() >
             k_MemoryLimitMultiplier * numbers.size());
  }

  void Initialize(const vector<int> &numbers) {
    total_number_of_numbers_ = numbers.size();
    preparePrimaryHashTable(numbers);
    primary_hash_table_.prepareSecondaryHashTables();
    primary_hash_table_.fillHashTable();
  }

  explicit FixedSet() {}

  bool Contains(int number) const {
    int number_of_sht = hashFunction(primary_hash_table_.a_coefficient_,
                                     primary_hash_table_.b_coefficient_,
                                     number) % total_number_of_numbers_;
    if (primary_hash_table_.secondary_hash_tables_[number_of_sht].
        numbers_to_store.size() == 0) {
      return false;
    }
    int hash_in_sht = hashFunction(
      primary_hash_table_.secondary_hash_tables_[number_of_sht].a_coefficient_,
      primary_hash_table_.secondary_hash_tables_[number_of_sht].b_coefficient_,
      number) % primary_hash_table_.secondary_hash_tables_[number_of_sht].
        numbers_to_store.size();
    return (!primary_hash_table_.secondary_hash_tables_[number_of_sht].
              numbers_empty[hash_in_sht] &&
            primary_hash_table_.secondary_hash_tables_[number_of_sht].
              numbers[hash_in_sht] == number);
  }
};

void readInputToVector(vector<int> *result_vector) {
  int number_of_numbers, current_int;
  scanf("%d", &number_of_numbers);
  for (int i = 0; i < number_of_numbers; ++i) {
    scanf("%d", &current_int);
    result_vector->push_back(current_int);
  }
}

void testNumbers(const FixedSet &fixed_set,
                 const vector<int> &numbers_to_test,
                 vector<bool> *result_of_test) {
  for (vector<int>::const_iterator it = numbers_to_test.begin();
       it != numbers_to_test.end(); ++it) {
    result_of_test->push_back(fixed_set.Contains(*it));
  }
}

void writeOutput(const vector<bool> &output_vector) {
  for (vector<bool>::const_iterator it = output_vector.begin();
       it != output_vector.end(); ++it) {
    *it ? printf("Yes\n") : printf("No\n");
  }
}

int main() {
  srand(2010);
  vector<int> numbers, numbers_to_test;
  vector<bool> result_of_test;
  readInputToVector(&numbers);
  readInputToVector(&numbers_to_test);
  FixedSet fixed_set;
  fixed_set.Initialize(numbers);
  testNumbers(fixed_set, numbers_to_test, &result_of_test);
  writeOutput(result_of_test);
  return 0;
}

Кириллица в библиотеке MySQLdb языка python

MySQLdb перед выполнением запроса пытается кодировать запрос в latin-1, поэтому когда в запросе есть кириллические символы в юникоде, вылетает такая ошибка:

"UnicodeEncodeError:'latin-1' codec can't encode character ...".

После того, как я провозился с этим пол дня, я нашел решение в гугле вот здесь http://www.dasprids.de/blog/2007/12/17/python-mysqldb-and-utf-8 (огромное спасибо этому парню). Вкратце необходимо выполнить эти команды после установления соединения:

db.set_character_set('utf8')
dbc.execute('SET NAMES utf8;')
dbc.execute('SET CHARACTER SET utf8;')
dbc.execute('SET character_set_connection=utf8;')

Где db - результат MySQLdb.connect, dbc - результат db.cursor().

Наибольшая общая подпоследовательность

По идее можно решать за O(nlogn), но здесь за O(n^2) простой динамикой:

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

using std::vector;
using std::cin;
using std::cout;
using std::max_element;

int countLongestCommonSubsequenceLength(const vector<int> &first_sequence,
                                        const vector<int> &second_sequence) {
  vector< vector<int> > common_prefix_length(first_sequence.size() +
    1, vector<int>(second_sequence.size() + 1, 0));
  for (size_t first_number = 1;
       first_number <= first_sequence.size();
       ++first_number) {
    for (size_t second_number = 1;
         second_number <= second_sequence.size();
         ++second_number) {
      if (first_sequence[first_number - 1] ==
          second_sequence[second_number - 1]) {
        common_prefix_length[first_number][second_number] =
          common_prefix_length[first_number - 1][second_number - 1] + 1;
      } else if (common_prefix_length[first_number - 1][second_number] >=
          common_prefix_length[first_number][second_number - 1]) {
        common_prefix_length[first_number][second_number] =
          common_prefix_length[first_number - 1][second_number];
      } else {
        common_prefix_length[first_number][second_number] =
          common_prefix_length[first_number][second_number - 1];
      }
    }
  }
  return common_prefix_length.back().back();
}

void readSequence(vector<int> *sequence) {
  int length, tmp_int;
  cin >> length;
  for (int element_number = 0; element_number < length; ++element_number) {
    cin >> tmp_int;
    sequence->push_back(tmp_int);
  }
}

int main() {
  vector<int> first_sequence, second_sequence;
  readSequence(&first_sequence);
  readSequence(&second_sequence);
  cout << countLongestCommonSubsequenceLength(first_sequence, second_sequence)
       << std::endl;
  return 0;
}

Циклический сдвиг последовательности на заданное число позиций

Параметры begin и end могут быть либо указателями на ячейки массива, либо итераторами, указывающими на начало и конец последовательности. Параметр k может принимать отрицательные значения, что означает сдвиг в другом направлении. Продемонстрирована работа функции с обычным массивом и вектором.

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

using std::vector;
using std::cout;
using std::endl;
using std::swap;

template <typename T> void rotate(T begin, T end, int k) {
  if (k > 0) {
    for (int i = 0; i < k; ++i) {
      for (T j = end - 1; j != begin; --j) {
        swap(*j, *(j-1));
      }
    }
  }
  if (k < 0) {
    for (int i = 0; i > k; --i) {
      for (T j = begin; j != end - 1; ++j) {
        swap(*j, *(j+1));
      }
    }
  }
}

// Test.
int main() {
  vector<int> a;
  a.push_back(1);
  a.push_back(2);
  a.push_back(3);
  a.push_back(4);
  rotate(a.begin(), a.end(), 2);
  for (vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
  int b[] = {1,2,3,4};
  rotate(b+0, b+4, -1);
  for (int i = 0; i < 4; i++) {
    cout << b[i] << " ";
  }
  cout << endl;
  return 0;
}

Метод деления пополам

Нахождение корня передаваемой в качестве параметра монотонной функции f на отрезке [a, b] методом деления пополам.

//Fuction returns b+1 if solution does not exist.
double solve(double a, double b, double (*f)(double)) {
  if (a > b) {
    return b+1;
  }
  if (f(a) * f(b) >= 0) {
    if (f(a) == 0) {
      return a;
    }
    if (f(b) == 0) {
      return b;
    }
    return b+1;
  }
  double x = (a + b) / 2;
  if (f(a) * f(x) <= 0) {
    return solve(a, x, f);
  }
  if (f(x) * f(b) <= 0) {
    return solve(x, b, f);
  }
  return b+1;
}

Расширенный алгоритм Евклида и вычисление обратного элемента по модулю в кольце

Написана функция, вычисляющая НОД целых чисел a и b и находящая целые коэффициенты x и y, такие, что ax + by = НОД(a, b). На основе этой функции написана новая функция, вычисляющая обратный элемент к a в кольце вычетов по модулю n, или сообщающая, что такого элемента не существует.

int gcdex(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int x1, y1;
  int d1 = gcdex(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return d1;
}

// Function returns 1 if such element doesn't exist and 0 if exists and puts it
// in result.
int ReverseElement(int a, int N, int &result) {
  int x, y, d;
  d = gcdex(a, N, x, y);
  if (d != 1) {
    return 1;
  } else {
    result = x;
    return 0;
  }
}

Определение дня недели по заданной дате

Для хранения информации о количестве дней в месяце используется константный массив. Написана функция, определяющая, является ли год високосным.

#include <iostream>
#include <algorithm>

using std::cout;
using std::cin;
using std::endl;
using std::min;
using std::max;

bool IsLeapYear(const int year) {
  if (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)) {
    return true;
  } else {
    return false;
  }
}

const int days_in_month[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int DefineWeekday(const int number, const int month, const int year) {
  // Reference date is 1 Jan 1990 and it is monday.
  int smaller_year = min(1990, year), bigger_year = max(1990, year);
  int days_difference = 0;
  // Count the day of the the 1 Jan of needed year.
  for (int i = smaller_year; i < bigger_year; ++i) {
    if (year > 1990) {
      days_difference += 365;
      if (IsLeapYear(i)) {
        ++days_difference;
      }
    } else {
      days_difference -= 365;
      if (IsLeapYear(i)) {
        --days_difference;
      }
    }
  }
  // Count difference between 1 Jan and our date.
  for (int i = 0; i < month - 1; ++i) {
    days_difference += days_in_month[i];
    if (i == 1 && IsLeapYear(year)) {
      ++days_difference;
    }
  }
  days_difference += number - 1;
  if (days_difference < 0) {
    return (7 + (days_difference % 7)) % 7 + 1;
  } else {
    return (days_difference % 7) + 1;
  }
}
    
  

void ReadInput(int &number, int &month, int &year) {
  cout << "Enter the number of day in month:";
  cin >> number;
  cout << "Enter the number of month:";
  cin >> month;
  if (month < 1 || month > 12) {
    cout << "Wrong number of month" << endl;
  }
  cout << "Enter the number of year:";
  cin >> year;
  if (number < 1 || number > days_in_month[ month - 1]) {
    if (month == 2 && IsLeapYear(year))
      if (number == 29) {
 return;
      }
    cout << "Wrong number" << endl;
  }
}

void WriteOutput(const int number_of_day) {
  switch(number_of_day) {
    case 1: {
      cout << "It is Monday" << endl;
      break;
    }
    case 2: {
      cout << "It is Tuesday" << endl;
      break;
    }
    case 3: {
      cout << "It is Wednesday" << endl;
      break;
    }
    case 4: {
      cout << "It is Thursday" << endl;
      break;
    }
    case 5: {
      cout << "It is Friday" << endl;
      break;
    }
    case 6: {
      cout << "It is Saturday" << endl;
      break;
    }
    case 7: {
      cout << "It is Sunday" << endl;
      break;
    }
  }
}

int main() {
  int number, month, year, day;
  ReadInput(number, month, year);
  day = DefineWeekday(number, month, year);
  WriteOutput(day);
  return 0;
}

Подсветка синтаксиса в Blogspot.

Так как частенько здесь будет появляться код, то подсветка синтаксиса не помешает. Google предложил эту статью, но заработало не сразу. Адреса, которые там используются устарели и по ним уже нет ни скриптов, ни стилей.
Поэтому делаем так: в часть <head>...</head> пишем:

<script src='http://softwaremaniacs.org/media/soft/highlight/highlight.pack.js'/>
<script type='text/javascript'>
initHighlightingOnLoad();
</script>

А еще надо все содержимое подходящего стиля скопировать в html код блога. Стили лежат по адресу  http://softwaremaniacs.org/media/soft/highlight/styles/. Посмотреть примеры стилей можно по адресу http://softwaremaniacs.org/media/soft/highlight/test.html.
После этого код надо заключать в теги <pre><code>...</code></pre> и он будет подсвечен, как показано выше.

Об этом блоге и обо мне

Здравствуйте, меня зовут Василий, и я алк студент МФТИ. Обучаюсь по специализации системного программирования, пишу на c++, python, bash. Здесь буду публиковать код, который пишу. Использование его по любому назначению не запрещается, однако я никакой ответственности за последствия не несу. Может кому-нибудь будет полезно, да и мне самому на память останется.