VPF::Реализация контейнера - Форум программистов

SShere

Дата 13.6.2009, 23:46 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 16.3.2009

Репутация: нет
Всего: нет

Задание не сложное, просто я не совсем понимаю что требуется.

Надо написать класс, реализующий контейнер, чтобы пользователь класса не задумывался о динамическом выделении памяти, объявлял объект и что-то с ним делал (если класс - контейнер, то что он будет с ним делать?)

п.с. Об STL не было ни слова.

mes

Дата 13.6.2009, 23:56 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

написать класс динамического массива, т.е Вам надо сделать свое подобие std::vector (скорей всего не шаблонный, т.е для определенного типа)

--------------------

http://opendots.net

SShere

Дата 14.6.2009, 00:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 16.3.2009

Репутация: нет
Всего: нет

Мне бы пример кода...

Cheloveck

Дата 14.6.2009, 00:28 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1578
Регистрация: 26.7.2008
Где: Тула

Репутация: 5
Всего: 32

Код


template<class T>
class cont
{
public:
    cont()
    {
        data_ = new T[data_size_]; 
        counter_= 1;
    }

    cont( const cont & c )
    {
        data_ = new T[data_size_];        
        memcpy( data_, c.data_, data_size_ * sizeof(T) );
        counter_++;
    }
    
    cont operator = ( cont & c )
    {
        // Примерно то же, что и в конструкторе копий
        counter_++;        
    }
    
    ~cont()
    {
        counter_--;
        if( !counter_ )
            delete [] data_;
    }
    
private:
    const int data_size_ = 100500;
    int counter_;
    T * data_;
    
};

Думаю, что-то вроде того...

Ну и плюс обращения к элементам data_ и всякие операции с ними

З.Ы. это был потуг показать умные указатели, но это плохо получилось и к тому же не рбязательно

Это сообщение отредактировал(а) Cheloveck - 14.6.2009, 00:36

--------------------

andrew_121

Дата 14.6.2009, 00:39 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 10
Всего: 33

Если вопрос не однозначный(как на собеседования бывает не редко), то возможно ожидается использование контейнера STL, прямо или косвенно.

--------------------

Удалил аккаунт. Прощайте!

Cheloveck

Дата 14.6.2009, 00:41 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1578
Регистрация: 26.7.2008
Где: Тула

Репутация: 5
Всего: 32

Код


template<class T>
class cont
{
public:
    cont()
    {
        data_ = new T[data_size_]; 
    }
    
    ~cont()
    {
        delete [] data_;
    }
    
    T operator [] ( int index )
    {
        if( index < data_size_ )
            return data_[index];
        else
            // Сообщить об ошибке
    }
    
    bool set_element( int index, T & elem ) 
    {
        if( index < data_size_ )
        {
            data_[index] = elem;
            return true;
        }
        else
            return false;        
    }
    
private:
    const int data_size_ = 100500;
};

Вот так, наверное, понятнее. Без лишней лабуды, но с некоторыми нужными методами

Это сообщение отредактировал(а) Cheloveck - 14.6.2009, 00:44

--------------------

andrew_121

Дата 14.6.2009, 00:47 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 10
Всего: 33

Cheloveck, Можно и так:

Код


template<class T, int S>
class cont {
   T data_[S];
public:
    cont() {}
    
    ~cont() {}
    
    T operator [] ( int index )
    {
        if( index < S )
            return data_[index];
        else
            // Сообщить об ошибке
    }
    
    bool set_element( int index, T & elem ) 
    {
        if( index < S )
        {
            data_[index] = elem;
            return true;
        }
        else
            return false;        
    }
};

--------------------

Удалил аккаунт. Прощайте!

jonie

Дата 14.6.2009, 12:00 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

Репутация: 6
Всего: 118

имхо при set_element в случае ошибки нужно делать throw, ибо это ошибка и она неожидаемая. Ну и незабывать size_t Size() const {return ..}; сделать.

--------------------

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

zim22

Дата 14.6.2009, 12:04 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(jonie @ 14.6.2009, 12:00

)

если пошла критика, то я бы добавил константный оператор индексирования наряду с обычным

Код


T &operator [] ( size_t index );
const T &operator [] ( size_t index ) const;

эту функцию вообще бы удалил

Код


bool set_element( int index, T & elem )

и внутри operator[] проверял диапазон индекса и бросал exception

Это сообщение отредактировал(а) zim22 - 14.6.2009, 12:10

--------------------

C++ FAQ Lite

gosn1ck

Дата 15.6.2009, 19:14 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 103
Регистрация: 18.4.2009

Репутация: 1
Всего: 1

zim22, можно в студию ваш варинт решения задачи? был бы благодарен очень smile

zim22

Дата 15.6.2009, 19:36 (ссылка)

(голосов:1)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(gosn1ck @ 15.6.2009, 19:14

)

можно в студию ваш варинт решения задачи? был бы благодарен очень

по минимуму я бы его так реализовал:
только основные операции:
1) перераспределение вектора в другую область памяти при исчерпании резервной памяти - функция reallocate
2) вставка элемента в вектор
3) итераторы для работы с алгоритмами
4) размер вектора - функция size

Код


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

template <class T>
class Vector {
public:
  typedef T* iterator;
  iterator beg_it;
  iterator end_it;

  Vector() : elements(0), first_free(0), end(0),
    beg_it(elements), end_it(first_free) { }
  T &operator[](size_t pos) { return elements[pos]; }
  const T &operator[](size_t pos) const { return elements[pos]; }
  void push_back(const T&);
  size_t size() const;
private:
  static std::allocator<T> alloc;
  void reallocate();
  T* elements;
  T* first_free;
  T* end;
};

template <class T>
std::allocator<T> Vector<T>::alloc;

template <class T>
size_t Vector<T>::size() const {
  return first_free - elements;
}

template <class T>
void Vector<T>::push_back(const T& t)
{
  if (first_free == end) reallocate();
  alloc.construct(first_free, t);
  end_it = ++first_free;
}

template <class T>
void Vector<T>::reallocate()
{
  ptrdiff_t size = first_free - elements;
  ptrdiff_t newcapacity = 2 * std::max(size, 1);

  T* newelements = alloc.allocate(newcapacity);
  std::uninitialized_copy(elements, first_free, newelements);

  for (T *p = first_free; p != elements; /* empty */)
    alloc.destroy(--p);

  if (elements) alloc.deallocate(elements, end - elements);

  elements = newelements;
  first_free = elements + size;
  end = elements + newcapacity;

  beg_it = elements;
  end_it = first_free;
}

int main()
{
  Vector<int> v;
  v.push_back(30);
  v.push_back(20);
  v.push_back(60);
  v.push_back(40);
  v.push_back(10);
  size_t sz = v.size();

  std::sort(v.beg_it, v.end_it);
  std::copy(v.beg_it, v.end_it, std::ostream_iterator<int>(std::cout, "\n"));

  return 0;
}

Это сообщение отредактировал(а) zim22 - 15.6.2009, 19:41

--------------------

C++ FAQ Lite

sdukshis

Дата 15.6.2009, 21:10 (ссылка)

(голосов:1)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 92
Регистрация: 23.3.2009

Репутация: нет
Всего: 1

Мой вариант (буду признателен за конструктивную критику)

Код


#ifndef VECTOR1_HPP
#define VECTOR1_HPP

#include <stdlib.h>

#include "iterator.hpp"

namespace posod{

class OutOfRange{};

template<class T>
class Vector {
private:
    size_t Size;
    size_t Capicity;
    T *array;
public:
    Vector():Size(0),Capicity(0),array(NULL) {};
    Vector(const size_t _size):Size(_size),Capicity(_size){ if(Capicity) array = new T[Capicity]; }
    Vector(const size_t _size , const T val);
    Vector(const Vector&);

    ~Vector(){delete[] array;}

    typedef T value_type;
    typedef T* iterator;
    typedef const T* const_iterator;
    typedef Reverse_iterator<iterator,T> reverse_iterator;
    typedef const Reverse_iterator<iterator,T> const_reverse_iterator;


    inline T& operator[](const size_t i) {return array[i]; }
    inline const T& operator[](const size_t i) const {return array[i]; }
    T& at(const size_t i);
    const T& at(const size_t i) const;

    Vector& operator=(const Vector& rhs);

    bool operator==(const Vector& rhs) const;

    void push_back(const T& val);
    T pop_back();

    inline size_t size() const {return Size; }
    inline size_t capicity() const {return Capicity; }

    inline iterator begin() const {return array; }
    inline iterator end()   const {return array+Size; }

    // for Ad_stack
    inline reverse_iterator rbegin() const {return reverse_iterator(iterator(array+Size-1)); }
    inline reverse_iterator rend() const {return reverse_iterator(iterator(array-1)); }


    bool compare(const T*) const;

    inline bool empty() const {return Size == 0; }
};// class Vector


template<class T>
Vector<T>::Vector(const size_t _size, const T val):Size(_size),Capicity(_size){
    array = new T[Capicity];

    for(size_t i = 0; i != Size; ++i)
        array[i] = val;
}

template<class T>
Vector<T>::Vector(const Vector& v):Size(v.Size),Capicity(v.Size){
    array = new T[Capicity];
    
    for(size_t i = 0; i != Size; ++i)
        array[i] = v.array[i];
}

template<class T>
T& Vector<T>::at(const size_t i){
    if(i >= Size) throw OutOfRange();

    return array[i];
}

template<class T>
const T& Vector<T>::at(const size_t i) const {
    if(i >= Size) throw OutOfRange();

    return array[i];
}

template<class T>
Vector<T>& Vector<T>::operator=(const Vector<T>& rhs){
    if (*this == rhs) return *this;

    delete[] array;
    Size = rhs.Size;
    Capicity = rhs.Size;

    array = new T[Capicity];

    for(size_t i = 0; i != Size; ++i)
        array[i] = rhs.array[i];

    return *this;
}

template<class T>
bool Vector<T>::operator==(const Vector& rhs) const{
    return Size == rhs.Size && compare(rhs.array);
}

template<class T>
void Vector<T>::push_back(const T& val){
    if(Size == Capicity) {

        Capicity = (Capicity)?Capicity*2:64;

        T *new_array = new T[Capicity];

        for(size_t i = 0; i != Size; ++i)
            new_array[i] = array[i];

        delete [] array;
        array = new_array;
    }

    array[Size++] = val;
}

template<class T>
T Vector<T>::pop_back(){
    return array[(Size--) - 1];
}

template<class T>
bool Vector<T>::compare(const T *rhs) const {
    for(size_t i = 0; i!= Size; ++i)
        if(array[i] != rhs[i]) return false;
    
    return true;
}

}// namespace posod
#endif

jonie

Дата 15.6.2009, 21:28 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

Репутация: 6
Всего: 118

а я б на собеседовании сказал бы что не велосипедист и отнаследовался от std::vector, если бы "заставили" 8-)

... для пущей важности аллокатор можно передавать как параметр шаблона с значеним по умолчанию 8))

Добавлено через 1 минуту и 58 секунд
T *array; - бяка. Никогда так не делайте 8)

--------------------

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

jonie

Дата 15.6.2009, 21:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

Репутация: 6
Всего: 118

Цитата

Код


 Capicity = (Capicity)?Capicity*2:64;

Magic numbers?

Цитата

Код


template<class T>
T Vector<T>::pop_back(){
    return array[(Size--) - 1];
}

на пустом векторе выполните ?

Цитата

Код


        T *new_array = new T[Capicity];

        for(size_t i = 0; i != Size; ++i)
            new_array[i] = array[i];

std::copy своими руками - сомнительное удовольствие.

operator= и конструктор копирования почему-то непохожи, хотя делают сутью одно и тоже.... да при желании много чего можно наплести, не надо просто изобретать велосипеды)

--------------------

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »