Хочется STL подобного

Новый комментарий
 

Стандартная библиотека как-то совсем не зашла. Предлагаю здесь делиться STL подобными поделками.

1. vector

#define GENERATE_VECTOR_GROWTH_FACTOR 2
#define GENERATE_VECTOR(NAME, REF)                                         \
   template <typename T>                                                   \
   class NAME                                                              \
   {                                                                       \
      uint sz;                                                             \
      bool fail_state;                                                     \
   public:                                                                 \
      T a[];                                                               \
      NAME(): sz(0), fail_state(false) {}                                  \
      NAME(uint count): sz(0), fail_state(false) {                         \
         if (ArrayResize(this.a, count) == -1)                             \
            this.fail_state = true;                                        \
         else                                                              \
            this.sz = count;                                               \
      }                                                                    \
      bool operator!()const      {return this.fail_state;}                 \
      uint size()const           {return this.sz;}                         \
      void clear()               {this.sz = 0; this.fail_state = false;}   \
      void push_back(T REF value) {                                        \
         if (this.sz == ArraySize(this.a)  &&                              \
             ArrayResize(this.a, this.sz*                                  \
                           GENERATE_VECTOR_GROWTH_FACTOR+1) == -1) {       \
            this.fail_state = true;                                        \
            return;                                                        \
         }                                                                 \
         this.a[this.sz++] = value;                                        \
      }                                                                    \
      void reserve(uint new_cap) {                                         \
         if ((int)new_cap > ArraySize(this.a))                             \
            ArrayResize(this.a, new_cap);                                  \
      }                                                                    \
      void erase(uint pos) {                                               \
         if ( ! ArrayRemove(this.a, (int)pos, 1) )                         \
            this.fail_state = true;                                        \
         else                                                              \
            -- this.sz;                                                    \
      }                                                                    \
   };
#define GENERATE_VECTOR_EMPTY
GENERATE_VECTOR(vector_fund, GENERATE_VECTOR_EMPTY);
GENERATE_VECTOR(vector_ref, const &);
#undef GENERATE_VECTOR_EMPTY
#undef GENERATE_VECTOR_GROWTH_FACTOR
#undef GENERATE_VECTOR

// использование
struct S {int a;};
class Q {};
bool f() {
   vector_ref<S> v1;
   vector_fund<int> v2;
   vector_ref<Q> v3;
   
   Q q;
   v3.push_back(q);
   v2.push_back(3);
   v2.a[0] = 5;
   
   return !(!v1 || !v2 || !v3);
}

2. сортировка. Пузырьковую удалил, слишком высока сложность вычисления. Сортировка слиянием:

// comp::cb - comparison function object which returns true if the first 
// argument is less than (i.e. is ordered before) the second. The signature
// of the comparison function should be equivalent to the following:
// bool cb(const Type1 &a, const Type2 &b);
// Returns true if success. 
template <typename Vector, typename Compare>
bool sort(Vector &vect, uint first, uint last, Compare &comp)
{
   if (last - first  == 1)
      return true;
   uint mid = (first + last) / 2;
   if ( ! sort(vect, first, mid, comp) )
      return false;
   if ( ! sort(vect, mid, last, comp) )
      return false;
   Vector tmp(last - first);
   if ( ! tmp )
      return false;
   for (uint li = first, ri = mid, tmpi = 0;  li<mid || ri<last;  ++ tmpi)
      if ( (li<mid && ri<last && comp.cb(vect.a[li], vect.a[ri]))  ||  ri == last ) {
         tmp.a[tmpi] = vect.a[li];
         ++ li;
      }
      else {
         tmp.a[tmpi] = vect.a[ri];
         ++ ri;
      }
   for (uint i = 0;  i < tmp.size();  ++ i)
      vect.a[first + i] = tmp.a[i];
   return true;
}

// Пример
struct S {
   int order;
   double data;
};

class Comp {
public:
   bool cb(const S &f, const S & s) {return f.order < s.order;}
};

void OnStart()
{
   vector_ref<S> v;
   MathSrand(GetTickCount());
   
   S s;
   for (uint i = 0;  i < 1000000;  ++ i) {
      s.order = MathRand();
      v.push_back(s);
   }
   
   Comp cmp;
   if ( sort(v, 0, v.size(), cmp) )
         Alert("ok");
}
 
Идея отличная. Но тут многие не знают про ООП. И не желают ((
 
Alexey Volchanskiy:
Идея отличная. Но тут многие не знают про ООП. И не желают ((

А некоторые желают, но не могут осилить.

 

Прогулялся,,,. подумал

Как собираетесь разобраться с указателями

STL полностью построена на них

 
Alexey Viktorov:

А некоторые желают, но не могут осилить.

***

 

Недели две назад занимался исcледованиями в этом направлении.
Контейнер для любого типа данных можно реализовать стандартными средствами MQL (с помощью шаблонов) без применения макросов.

На текущий момент выполнены  основные работы в сторону реализации "умного" контейнера на MQL.
Контейнер самостоятельно определяет используемый тип данных (класс, указатель, POD структура, не POD структура, string,...). Ожидается поддержка всех типов "из коробки" (за исключением union).
Так для классов, структур и указательной будет проверяться наличие реализованных операторов сравнения и равенства, а так же функций Equals, Compare.

struct Info{
    int ID;
    string data;

    booloperator=(Info &obj){
        returnthis.ID == obj.ID;
    }
}


Нужно просто реализовать нужный метод и информация о его наличии, как в случаи с operator= выше, будет использована для выбора лучшей модели поведения, например в  реализации функции поиска, проверки вхождения или сортировки.
При этом от пользователя не требуя ни каких действий по конфигурации контейнера вообще.

Основные работы по реализации заявленного функционала уже выполнены, но для их завершения необходимо:
- дождаться выхода обновления с внедрением пространства имен;
- дождаться фикса ряда багов с указателями на функции;

Ждёмс...

 
Alexey Volchanskiy:

***

Это ты вторую готовишь к замужеству? Раньше была Оля, я правильно помню:)))

 

3. Бинарный поиск

// comp - binary predicate which returns ​true if the first argument is less than 
// (i.e. is ordered before) the second. The signature of the predicate function
// should be equivalent to the following: comp::cb(const Type1 &a, const Type2 &b).
// Returns index pointing to the first element that is not less than value, or last
// if no such element is found. 
template<typename Vector, typename T, typename Comp>
uint lower_bound(const Vector &vect, uint first, uint last,
                 const T &value, Comp &comp)
{
   uint count = last - first;
   uint res = first;  
   while (count != 0) {
      uint it = res;
      uint step = count / 2;
      it += step;
      if(comp.cb(vect.a[it], value)) {
         res = ++it;
         count -= step + 1;
      }
      else
         count = step;
   }
   return res;
}


//--------------- Пример------------:
struct S {
   uint order;
   double data;
};

class Comp {
public:
   bool cb(const S &f, uint s) {return f.order < s;}
};

void OnStart()
{
   vector_ref<S> v;
 
   S s;
   for (uint i = 10;  i < 40;  i+=2) {
      s.order = i;
      v.push_back(s);
   }
   
   Comp cmp;
   uint value = 19;
   uint res = lower_bound(v, 0, v.size(), value, cmp);
   if ( res == v.size() )
      Alert("not found");
   else
      Alert("index = ", res, " value = ", v.a[res].order);  // Alert: index = 5 value = 20
}

Думаю, что нет смысла заморачиваться с upper_bound() и реверсом, легко реализуется через lower_bound().

На мой взгляд, этот "набор" покрывает большинство задач.

 
Vict:

1. vector

И зачем всю портянку помещать внутрь макроса?   Если требуется лишь один метод с REF, то его и засунуть в макрос.  А всё остальное вынести в базовый класс.

p.s. А вообще всё легко делается и без макросов:

template<typename T>
class vector_ref
{
 public:
  void push_back(const T & value);
};

template<typename T>
class vector : public vector_ref<T>
{
  public:
   void push_back(T value) { vector_ref<T>::push_back(value); }
};
 
А что, пузырьковая сортировка это STL подобно? Вот бы я такое отмочил, вот бы тут было... Но членам клуба можно? Да?
 
Alexey Navoykov:
И зачем всю портянку помещать внутрь макроса?   Если требуется лишь один метод с REF, то его и засунуть в макрос.  А всё остальное вынести в базовый класс.

Пришлось из-за мкл ограничений, нельзя передать в функцию с сигнатурой void fn(const int &) литерал: fn(5). Поэтому решил генерить две версии: для фундаментальных типов и для пользовательских (сигнатура для фундаментальных без ссылки (для передачи литералов без головняков), а для пользовательских с оной).

ЗЫ:

p.s. А вообще всё легко делается и без макросов:


оказывается, что можно даже так:

class S {
public:
   void f(int i) {}
   void f(const int &i) {}
};

start() {
   S s;
   s.f(5);
}
и не будет никакой неопределённости. Я не знал что так можно, в плюсах ошибка. Ну и х.з. насколько можно полагаться на это ...
1234
Новый комментарий