vector<MyClass> V;
while(...){
MyClass O(...);
if (O.init(...)) V.push_back(O);
}
Есть ли эффективный vector<>?
Давно мучает такой вопрос.
Можно ли в С++ эффективно реализовать шаблон vector<> ?
К примеру есть такой типичный код:
Реализация вектора из STL вообще никуда не годится (в ней при добавлении элемента копируется весь вектор).
До некоторой степени ее улучшить можно, но идеала достичь не получается.
А в идеале нужно следующее:
1) класс MyClass не обязан иметь конструктора по-умолчанию, а также конструктора и оператора копирования;
2) при добавлении элемента не должны перемещаться помещенные ранее;
3) возможность обходиться без вспомогательной переменной O (а значит, без лишнего копирования).
Все проблемы решаются, если вектор составлять не из самих объектов, а из указателей на объекты.
Но это тоже не идеальный вариант, так как происходит выделение памяти мелкими порциями. Хотя в большинстве случаев это единственный выход.
Есть ли для описанной задачи изящное решение?
Например, можно ли как-то вызвать конструктор для уже выделенной области памяти, а также вызвать деструктор объекта, не освобождая память?
Можно ли в С++ эффективно реализовать шаблон vector<> ?
К примеру есть такой типичный код:
Код:
Реализация вектора из STL вообще никуда не годится (в ней при добавлении элемента копируется весь вектор).
До некоторой степени ее улучшить можно, но идеала достичь не получается.
А в идеале нужно следующее:
1) класс MyClass не обязан иметь конструктора по-умолчанию, а также конструктора и оператора копирования;
2) при добавлении элемента не должны перемещаться помещенные ранее;
3) возможность обходиться без вспомогательной переменной O (а значит, без лишнего копирования).
Все проблемы решаются, если вектор составлять не из самих объектов, а из указателей на объекты.
Но это тоже не идеальный вариант, так как происходит выделение памяти мелкими порциями. Хотя в большинстве случаев это единственный выход.
Есть ли для описанной задачи изящное решение?
Например, можно ли как-то вызвать конструктор для уже выделенной области памяти, а также вызвать деструктор объекта, не освобождая память?
Цитата:
Originally posted by nvm
Реализация вектора из STL вообще никуда не годится (в ней при добавлении элемента копируется весь вектор).
Реализация вектора из STL вообще никуда не годится (в ней при добавлении элемента копируется весь вектор).
Я бы не был столь категоричным.
Может, тебе просто не хватает знаний по STL?
Посмотри классы list, queue, deque и т.д.
Цитата:
Originally posted by Green
Я бы не был столь категоричным.
Может, тебе просто не хватает знаний по STL?
Посмотри классы list, queue, deque и т.д.
Я бы не был столь категоричным.
Может, тебе просто не хватает знаний по STL?
Посмотри классы list, queue, deque и т.д.
Я говорил исключительно про шаблон vector<>. При чем здесь list и пр..?!
Мне нужен динамический массив с индексированным доступом!
Цитата:
Originally posted by nvm
Я говорил исключительно про шаблон vector<>. При чем здесь list и пр..?!
Мне нужен динамический массив с индексированным доступом!
Я говорил исключительно про шаблон vector<>. При чем здесь list и пр..?!
Мне нужен динамический массив с индексированным доступом!
Тогда я не понимаю, какие претензии к "в ней при добавлении элемента копируется весь вектор".
Элемент добавляется, размер вектора увеличивается, необходимо выделить больший объем памяти и скопировать в него старые элементы с добавлением нового(новых).
Как ты представляешь это себе иначе?
Кроме того.
Цитата:
Originally posted by nvm
1) класс MyClass не обязан иметь конструктора по-умолчанию, а также конструктора и оператора копирования;
1) класс MyClass не обязан иметь конструктора по-умолчанию, а также конструктора и оператора копирования;
Это несколько противоречит ООП.
Если класс имеет конструктор с параметрами, то значит, происходит инициализация некоторых членов класса некоторыми внешними данными напрямую или косвенно. Тогда как же должен выглядеть экземпляр класса созданный конструктором без параметров? Как скопировать такой экземпляр, ведь копирование экземпляра это не примитивное копирование участка памяти? Это все должен определить программист. Поэтому хорошим стилем программирования считается сразу определять конструкторы копирования, операторы присвоения и виртуальный деструктор.
А STL разрабатывался в хорошем стиле и для хорошего стиля программирования.
Цитата:
Originally posted by nvm
2) при добавлении элемента не должны перемещаться помещенные ранее;
2) при добавлении элемента не должны перемещаться помещенные ранее;
Ну это невозможно, т.к. увеличение вектора влечет увеличение занимаемого им места в памяти. А так как вектор располагается в памяти линейно, то приходиться перевыделять кусок памяти большего размера. Здесь приходиться идти на компромисс между линейностью и производительностью и это не зависит от реализации STL, любой другой алгоритм будет иметь такой же характер.
Кстати, тебе никто не мешает сразу создать вектор необходимого размера (resize), а потом просто проинициализировать его элементы.
Цитата:
Originally posted by nvm
3) возможность обходиться без вспомогательной переменной O (а значит, без лишнего копирования).
3) возможность обходиться без вспомогательной переменной O (а значит, без лишнего копирования).
Ну это просто твой стиль программирования.
Никто не мешает обойтись без "переменной O".
В твоем примере для этого достаточно сначала добавить элемент в вектор, а потом уже вызывать его методы.
Цитата:
Originally posted by nvm
Например, можно ли как-то вызвать конструктор для уже выделенной области памяти, а также вызвать деструктор объекта, не освобождая память?
Например, можно ли как-то вызвать конструктор для уже выделенной области памяти, а также вызвать деструктор объекта, не освобождая память?
Конструктор, как и деструктор вызывается не для памяти, а для экземпляра класса, и вызываются в момент его создания и уничтожения. Объект можно создать в заданном участке памяти, указав как параметр new указатель на этот участок, но я считаю это плохим стилем. Никто не мешает вынести действия выполняемые в конструкторе и деструкторе в отдельные методы. Можно даже запретить создавать и уничтожать экземпляры извне (т.е. запретить вызов конструкторов и деструкторов) и т.о. заставить класс самому решать когда следует создавать экземпляры, а когда не следует, когда уничтожать их, а когда нет.
STL действительно не идеален, как и все в этом мире, но его неидеальность лежит не в той области, в которой ты попытался представить, а несколько в другой, например, в threadsave.
Твоя же проблема в том, что неправильно пользуешься этим инструментом, возможно, в силу недостаточного опыта, невыработанного стиля, а так же неправильно составленной архитектуры.
2 nvm :
Никто не мешает написать свой "vector".
По сути дела тебе может подойти одно- или
двухсвязный список. Недавно занимался этим.
Занятие нудное и не доделал до конца(лень), но работает(почти).
При желании можно написать за несколько дней. Основная нудность - написание всех методов, которыми обладает тот же вектор (ЛЕНЬ! ЛЕНЬ!).
Но универсальности вектора будет трудно достичь!
Никто не мешает написать свой "vector".
По сути дела тебе может подойти одно- или
двухсвязный список. Недавно занимался этим.
Занятие нудное и не доделал до конца(лень), но работает(почти).
При желании можно написать за несколько дней. Основная нудность - написание всех методов, которыми обладает тот же вектор (ЛЕНЬ! ЛЕНЬ!).
Но универсальности вектора будет трудно достичь!
Цитата:
Originally posted by Green
Тогда я не понимаю, какие претензии к "в ней при добавлении элемента копируется весь вектор".
Элемент добавляется, размер вектора увеличивается, необходимо выделить больший объем памяти и скопировать в него старые элементы с добавлением нового(новых).
Как ты представляешь это себе иначе?
Тогда я не понимаю, какие претензии к "в ней при добавлении элемента копируется весь вектор".
Элемент добавляется, размер вектора увеличивается, необходимо выделить больший объем памяти и скопировать в него старые элементы с добавлением нового(новых).
Как ты представляешь это себе иначе?
Как минимум, можно выделять память с запасом, т.е. увеличивать не на один элемент, а, скажем, на 10%
Цитата:
Это несколько противоречит ООП.
Если класс имеет конструктор с параметрами, то значит, происходит инициализация некоторых членов класса некоторыми внешними данными напрямую или косвенно. Тогда как же должен выглядеть экземпляр класса созданный конструктором без параметров?
Если класс имеет конструктор с параметрами, то значит, происходит инициализация некоторых членов класса некоторыми внешними данными напрямую или косвенно. Тогда как же должен выглядеть экземпляр класса созданный конструктором без параметров?
В том-то и дело, что никак! А STL требует наличие конструктора без параметров - и в этом его огромный недостаток и нарушение стиля ООП.
Цитата:
Поэтому хорошим стилем программирования считается сразу определять конструкторы копирования, операторы присвоения..
Я их всегда определяю. Но только как private, без реализации. Потому что для 90% классов, которые у меня возникали, операция копирования не имеет содержательного смысла. То есть, объект, будучи проинициализирован, никогда не копируется, а доступ к нему только по ссылкам.
Конечно, для каких-нибудь хрестоматийных complex или point копирование необходимо. А мне приходится работать с контейнерами данных, возможность копирования которых в программе бессысленна и просто вредна (в лучшем случае снижение производительности, а в худшем - ошибка из-за случайного "клонирования").
Цитата:
Кстати, тебе никто не мешает сразу создать вектор необходимого размера (resize), а потом просто проинициализировать его элементы.
Теряется почти весь смысл вектора.
Цитата:
Ну это просто твой стиль программирования.
Никто не мешает обойтись без "переменной O".
В твоем примере для этого достаточно сначала добавить элемент в вектор, а потом уже вызывать его методы.
Никто не мешает обойтись без "переменной O".
В твоем примере для этого достаточно сначала добавить элемент в вектор, а потом уже вызывать его методы.
Это не стиль. Это семантика метода push_back(). Так как его параметр - объект класса, то этот объект в любом случае будет создан в момент или перед вызовом метода, а затем внутри метода скопирован в новый объект.
То есть создание лишнего объекта неизбежно.
Цитата:
Объект можно создать в заданном участке памяти, указав как параметр new указатель на этот участок..
Хорошо.
А уничтожить объект, без освобождения памяти - возможно?
Цитата:
Твоя же проблема в том, что неправильно пользуешься этим инструментом, возможно, в силу недостаточного опыта, невыработанного стиля, а так же неправильно составленной архитектуры.
Я имел дело с "правильно" составленными программами (прямо образец для учебников) - они работают на порядки (например, в 100 раз) медленнее, чем это оправдано сложностью задачи. И часто - именно из-за STL.
Цитата:
Originally posted by Green
Тогда я не понимаю, какие претензии к "в ней при добавлении элемента копируется весь вектор".
Элемент добавляется, размер вектора увеличивается, необходимо выделить больший объем памяти и скопировать в него старые элементы с добавлением нового(новых).
Как ты представляешь это себе иначе?
... это невозможно, т.к. увеличение вектора влечет увеличение занимаемого им места в памяти. А так как вектор располагается в памяти линейно, то приходиться перевыделять кусок памяти большего размера.
Тогда я не понимаю, какие претензии к "в ней при добавлении элемента копируется весь вектор".
Элемент добавляется, размер вектора увеличивается, необходимо выделить больший объем памяти и скопировать в него старые элементы с добавлением нового(новых).
Как ты представляешь это себе иначе?
... это невозможно, т.к. увеличение вектора влечет увеличение занимаемого им места в памяти. А так как вектор располагается в памяти линейно, то приходиться перевыделять кусок памяти большего размера.
Вот пример, позволяющий обойтись вообще без копирования.
Код:
template <class T, int BufIncrement=100> class vectorus
{
public:
vectorus()
: m_BufInc(BufIncrement)
{
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
~vectorus()
{
empty();
}
void leave()
{
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
void empty()
{
for (int i=0; i<m_BufLen; i++) delete [] m_Buffer;
delete [] m_Buffer;
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
bool push_back(const T &v)
{
int i1=m_N/m_BufInc;
while (i1>=m_BufLen){
int oLen=m_BufLen;
m_BufLen+=m_BufInc;
T** b=new T*[m_BufLen];
for (int i=0; i[list=1]=m_N) throw("vectorus:: - out of range");
return m_Buffer[i/m_BufInc][i%m_BufInc];
}
const T& operator[](int i) const
{
if (i<0 || i>=m_N) throw("vectorus:: - out of range");
return m_Buffer[i/m_BufInc][i%m_BufInc];
}
private:
int m_BufInc;
int m_BufLen;
int m_N;
T** m_Buffer;
};
{
public:
vectorus()
: m_BufInc(BufIncrement)
{
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
~vectorus()
{
empty();
}
void leave()
{
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
void empty()
{
for (int i=0; i<m_BufLen; i++) delete [] m_Buffer;
delete [] m_Buffer;
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
bool push_back(const T &v)
{
int i1=m_N/m_BufInc;
while (i1>=m_BufLen){
int oLen=m_BufLen;
m_BufLen+=m_BufInc;
T** b=new T*[m_BufLen];
for (int i=0; i[list=1]=m_N) throw("vectorus:: - out of range");
return m_Buffer[i/m_BufInc][i%m_BufInc];
}
const T& operator[](int i) const
{
if (i<0 || i>=m_N) throw("vectorus:: - out of range");
return m_Buffer[i/m_BufInc][i%m_BufInc];
}
private:
int m_BufInc;
int m_BufLen;
int m_N;
T** m_Buffer;
};
Это тоже до безобразия криво - но хотя бы можно пользоваться..
Цитата:
Originally posted by _anton
2 nvm :
Никто не мешает написать свой "vector".
По сути дела тебе может подойти одно- или
двухсвязный список.
2 nvm :
Никто не мешает написать свой "vector".
По сути дела тебе может подойти одно- или
двухсвязный список.
Список никак не пойдет - смысл вектора в произвольной индексации..
Цитата:
Основная нудность - написание всех методов, которыми обладает тот же вектор (ЛЕНЬ! ЛЕНЬ!).
Но универсальности вектора будет трудно достичь!
Но универсальности вектора будет трудно достичь!
Да этих методов нужно-то всего ничего:
- добавление,
- считывание с удалением элемента,
- доступ по индексу (константный и неконстантный),
- resize в сторону уменьшения (увеличение невозможно, т.к. нет конструктора объектов по-умолчанию).
Итого 5 штук.
PS. Про итераторы напоминать не нужно - я и так прекрасно знаю, насколько это сейчас модно... Желающие могут добавить.
Цитата:
Originally posted by nvm
Список никак не пойдет - смысл вектора в произвольной индексации..
Список никак не пойдет - смысл вектора в произвольной индексации..
Можно сделать отдельный массив с указателями на элементы списка и с его помощью получить произвольную индексациюю.
Цитата:
Originally posted by nvm
Вот пример, позволяющий обойтись вообще без копирования.
Это тоже до безобразия криво - но хотя бы можно пользоваться..
Вот пример, позволяющий обойтись вообще без копирования.
Код:
template <class T, int BufIncrement=100> class vectorus
{
public:
vectorus()
: m_BufInc(BufIncrement)
{
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
~vectorus()
{
empty();
}
void leave()
{
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
void empty()
{
for (int i=0; i<m_BufLen; i++) delete [] m_Buffer;
delete [] m_Buffer;
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
bool push_back(const T &v)
{
int i1=m_N/m_BufInc;
while (i1>=m_BufLen){
int oLen=m_BufLen;
m_BufLen+=m_BufInc;
T** b=new T*[m_BufLen];
for (int i=0; i[list=1]=m_N) throw("vectorus:: - out of range");
return m_Buffer[i/m_BufInc][i%m_BufInc];
}
const T& operator[](int i) const
{
if (i<0 || i>=m_N) throw("vectorus:: - out of range");
return m_Buffer[i/m_BufInc][i%m_BufInc];
}
private:
int m_BufInc;
int m_BufLen;
int m_N;
T** m_Buffer;
};
{
public:
vectorus()
: m_BufInc(BufIncrement)
{
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
~vectorus()
{
empty();
}
void leave()
{
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
void empty()
{
for (int i=0; i<m_BufLen; i++) delete [] m_Buffer;
delete [] m_Buffer;
m_Buffer=0;
m_BufLen=0;
m_N=0;
}
bool push_back(const T &v)
{
int i1=m_N/m_BufInc;
while (i1>=m_BufLen){
int oLen=m_BufLen;
m_BufLen+=m_BufInc;
T** b=new T*[m_BufLen];
for (int i=0; i[list=1]=m_N) throw("vectorus:: - out of range");
return m_Buffer[i/m_BufInc][i%m_BufInc];
}
const T& operator[](int i) const
{
if (i<0 || i>=m_N) throw("vectorus:: - out of range");
return m_Buffer[i/m_BufInc][i%m_BufInc];
}
private:
int m_BufInc;
int m_BufLen;
int m_N;
T** m_Buffer;
};
Это тоже до безобразия криво - но хотя бы можно пользоваться..
Да уж действительно криво :D
Я бы пользовался с осторожностью, т.к. есть явные и неочень ошибки. Если нужно, могу показать где.
Не скажу, что сильно вчитывался в код, но как понял твоя идея сводится к тому, что ты имеешь массив указателей на объекты, причем массив несколько больше, чем количество объектов, и разница забита нулевыми указателями.
Это конечно повысит скорость индексного доступа, но замедляет операции добавления удаления по сравнению, например, с list, для которого можно реализовать индексный доступ.
Цитата:
Originally posted by Hearse
Можно сделать отдельный массив с указателями на элементы списка и с его помощью получить произвольную индексациюю.
Можно сделать отдельный массив с указателями на элементы списка и с его помощью получить произвольную индексациюю.
А тогда зачем список?! Тогда и работать с массивом указателей.
Этот вариант решает все проблемы. Но имеет недостаток: выделение памяти в куче мелкими порциами (для каждого объекта, вместо того, чтобы сразу для вектора).
Цитата:
Originally posted by Green
Да уж действительно криво :D
Да уж действительно криво :D
Кривость в-основном в том, что при добавлении элемента используется оператор копирования, а не конструктор.
Цитата:
Я бы пользовался с осторожностью, т.к. есть явные и неочень ошибки. Если нужно, могу показать где.
Назвал бы хоть одну для примера.
Этот класс очень опасен в использовании (хотя на самом деле ошибки доступа к памяти - не самые опасные, так как программа ломается вполне воспроизводимо, и их относительно легко исправить).
Да, он рассчитан на дефолтный оператор копирования, после использования которого необходимо явно вызвать leave().
Но это, собственно, только пример, показывающий, что копирования при расширении вектора можно избежать вовсе.
Цитата:
Не скажу, что сильно вчитывался в код, но как понял твоя идея сводится к тому, что ты имеешь массив указателей на объекты, причем массив несколько больше, чем количество объектов, и разница забита нулевыми указателями.
А как же ошибки нашел, если не вчитывался?
Вообще, так как я не давал спецификацию, то ошибок там нельзя найти по-определению ;)
А идею ты не увидел.
Она в том, что используется двумерный массив!
Точнее, массив указателей на одномерные массивы фиксированного размера.
Выгода здесь в том, что увеличивать размер может понадобиться только у "внешнего" массива указателей - а он много меньше числа элементов, поэтому если и приходится копировать, то лишь небольшое число указателей.
Цитата:
Это конечно повысит скорость индексного доступа, но замедляет операции добавления удаления по сравнению, например, с list, для которого можно реализовать индексный доступ.
Списки имеют смысл только, если предполагается вставка элемента в середину.
В остальных случаях вектор указателей по всем параметрам лучше.
Цитата:
Originally posted by nvm
А как же ошибки нашел, если не вчитывался?
Вообще, так как я не давал спецификацию, то ошибок там нельзя найти по-определению ;)
А как же ошибки нашел, если не вчитывался?
Вообще, так как я не давал спецификацию, то ошибок там нельзя найти по-определению ;)
Ну скорее, из-за отсутствия спецификации и неглубокой вчитки мне и показались некоторые места ошибочными.
Кстати, я не вижу смысла в m_BufInc, IMHO можно обойтись и параметром шаблона. И еще неплохо бы вставить проверку, что BufIncrement!=0. Это можно сделать на этапе компиляции, чтоб не тащить проверку в рантайм.
Также не вижу смысла в возвращении результата в push_back. Он всегда true.
Не совсем ясен смысл m_BufLen вместе с m_N. IMHO от чего-то одного можно отказаться, производительность упадет незначительно мало.
Цитата:
Originally posted by nvm
Но это, собственно, только пример, показывающий, что копирования при расширении вектора можно избежать вовсе.
Но это, собственно, только пример, показывающий, что копирования при расширении вектора можно избежать вовсе.
Ну все же не совсем...
Копирование массивов указателей на подмассивы все же присутствует. Кстати, все усложниться при реализации вставки, удаления элементов.
Цитата:
Originally posted by nvm
А идею ты не увидел.
Она в том, что используется двумерный массив!
Точнее, массив указателей на одномерные массивы фиксированного размера.
Выгода здесь в том, что увеличивать размер может понадобиться только у "внешнего" массива указателей - а он много меньше числа элементов, поэтому если и приходится копировать, то лишь небольшое число указателей.
А идею ты не увидел.
Она в том, что используется двумерный массив!
Точнее, массив указателей на одномерные массивы фиксированного размера.
Выгода здесь в том, что увеличивать размер может понадобиться только у "внешнего" массива указателей - а он много меньше числа элементов, поэтому если и приходится копировать, то лишь небольшое число указателей.
Каюсь, не усмотрел.
Цитата:
Originally posted by nvm
Списки имеют смысл только, если предполагается вставка элемента в середину.
В остальных случаях вектор указателей по всем параметрам лучше.
Списки имеют смысл только, если предполагается вставка элемента в середину.
В остальных случаях вектор указателей по всем параметрам лучше.
Ну это, конечно, зависит от применения.
:)
Еще бы я вынес определение int i за пределы цикла в push_back, чтоб быть ближе к стандарту С++.
Кстати, обнулять b IMHO нет особого смысла.
Еще бы я вынес определение int i за пределы цикла в push_back, чтоб быть ближе к стандарту С++.
Кстати, обнулять b IMHO нет особого смысла.
Цитата:
Originally posted by Green
Еще бы я вынес определение int i за пределы цикла в push_back, чтоб быть ближе к стандарту С++.
Еще бы я вынес определение int i за пределы цикла в push_back, чтоб быть ближе к стандарту С++.
..Ох эти Соломоновы стандарты.
Плохо, что объявление в цикле не делает переменную локальной по отношению к циклу.
А так действительно, вроде как есть основания ее выносить.
Но ИМХО, это совершенная мелочь..
Цитата:
Кстати, обнулять b IMHO нет особого смысла.
Согласен.
Цитата:
Originally posted by Green
:)
Еще бы я вынес определение int i за пределы цикла в push_back, чтоб быть ближе к стандарту С++.
Кстати, обнулять b IMHO нет особого смысла.
:)
Еще бы я вынес определение int i за пределы цикла в push_back, чтоб быть ближе к стандарту С++.
Кстати, обнулять b IMHO нет особого смысла.
Что за стандарт?
Цитата:
Originally posted by Winnie
Что за стандарт?
Что за стандарт?
Стандарт языка С++
ISO/ANSI C++
конкретно пункт про область видимости в циклах for - 6.5.3.1
Цитата:
Originally posted by Green
Стандарт языка С++
ISO/ANSI C++
конкретно пункт про область видимости в циклах for - 6.5.3.1
Стандарт языка С++
ISO/ANSI C++
конкретно пункт про область видимости в циклах for - 6.5.3.1
Спасибо, понял, не на ту функцию смотрел
Нашел более-менее решение..
Использование:
vector<Class> V;
Class &E=*new(V.new_back()) Class(...);
- создание элемента.
V.cut_back(); - удаление последнего элемента.
Код:
template <class T, int BufIncrement=256> class vectorus
{
public:
vectorus()
{
int inc=BufIncrement;
if (inc<sizeof(T)) inc=sizeof(T);
if (inc<sizeof(char*)) inc=sizeof(char*);
m_Buffer=0;
m_Len1=0;
m_Len1Step=(inc-1)/sizeof(char*)+1;
m_Len2=(inc-1)/sizeof(T)+1;
m_Count=0;
}
~vectorus()
{
empty();
}
void empty()
{
for (int i=0; i<m_Count; i++) operator[](i).~T();
int fil1=0;
if (m_Count>0) fil1=(m_Count-1)/m_Len2+1;
for (i=0; i<fil1; i++) delete [] m_Buffer;
delete [] m_Buffer;
m_Buffer=0;
m_Count=0;
}
void* new_back()
{
if (m_Count%m_Len2==0){ // need new subbuffer
int fil1=m_Count/m_Len2;
if (fil1>=m_Len1){ // extend buffer
int oLen=m_Len1;
m_Len1+=m_Len1Step;
char** b=new char*[m_Len1];
for (int i=0; i[list=1]0){
operator[](m_Count-1).~T();
m_Count--;
if (m_Count%m_Len2==0) delete [] m_Buffer[m_Count/m_Len2];
}
}
int size() const
{
return m_Count;
}
T& operator[](int i)
{
if (i<0 || i>=m_Count) throw("vectorus:: - out of range");
return *((T*)(m_Buffer[i/m_Len2]+(i%m_Len2)*sizeof(T)));
}
const T& operator[](int i) const
{
if (i<0 || i>=m_Count) throw("vectorus:: - out of range");
return *((T*)(m_Buffer[i/m_Len2]+(i%m_Len2)*sizeof(T)));
}
private:
int m_Len1Step; // in char*
int m_Len2; // in T
int m_Len1;
int m_Count; // number of elements
char** m_Buffer;
vectorus(const vectorus&);
vectorus& operator=(const vectorus&);
};
{
public:
vectorus()
{
int inc=BufIncrement;
if (inc<sizeof(T)) inc=sizeof(T);
if (inc<sizeof(char*)) inc=sizeof(char*);
m_Buffer=0;
m_Len1=0;
m_Len1Step=(inc-1)/sizeof(char*)+1;
m_Len2=(inc-1)/sizeof(T)+1;
m_Count=0;
}
~vectorus()
{
empty();
}
void empty()
{
for (int i=0; i<m_Count; i++) operator[](i).~T();
int fil1=0;
if (m_Count>0) fil1=(m_Count-1)/m_Len2+1;
for (i=0; i<fil1; i++) delete [] m_Buffer;
delete [] m_Buffer;
m_Buffer=0;
m_Count=0;
}
void* new_back()
{
if (m_Count%m_Len2==0){ // need new subbuffer
int fil1=m_Count/m_Len2;
if (fil1>=m_Len1){ // extend buffer
int oLen=m_Len1;
m_Len1+=m_Len1Step;
char** b=new char*[m_Len1];
for (int i=0; i[list=1]0){
operator[](m_Count-1).~T();
m_Count--;
if (m_Count%m_Len2==0) delete [] m_Buffer[m_Count/m_Len2];
}
}
int size() const
{
return m_Count;
}
T& operator[](int i)
{
if (i<0 || i>=m_Count) throw("vectorus:: - out of range");
return *((T*)(m_Buffer[i/m_Len2]+(i%m_Len2)*sizeof(T)));
}
const T& operator[](int i) const
{
if (i<0 || i>=m_Count) throw("vectorus:: - out of range");
return *((T*)(m_Buffer[i/m_Len2]+(i%m_Len2)*sizeof(T)));
}
private:
int m_Len1Step; // in char*
int m_Len2; // in T
int m_Len1;
int m_Count; // number of elements
char** m_Buffer;
vectorus(const vectorus&);
vectorus& operator=(const vectorus&);
};
Использование:
vector<Class> V;
Class &E=*new(V.new_back()) Class(...);
- создание элемента.
V.cut_back(); - удаление последнего элемента.
Предложения, замечания принимаются?
1. Для чего такие сложности c BufIncrement? Не проще ли использовать два параметра: размер подмассива в элементах и шаг приращения массива указателей?
2. Массив указателей не уменьшается (по граничным условиям) в cat_back, это такая задумка? Есть ли необходимость держать неиспользуемые объемы памяти? Тогда m_Len1 будет не нужен.
3. В строке m_Buffer[fil1++]=new char[m_Len2*sizeof(T)]; зачем ++?
4. Еще не нравиться использование, точнее вот это:
new(V.new_back()) Class(1);
Class &E = *new(V.new_back()) Class();
1. Для чего такие сложности c BufIncrement? Не проще ли использовать два параметра: размер подмассива в элементах и шаг приращения массива указателей?
2. Массив указателей не уменьшается (по граничным условиям) в cat_back, это такая задумка? Есть ли необходимость держать неиспользуемые объемы памяти? Тогда m_Len1 будет не нужен.
3. В строке m_Buffer[fil1++]=new char[m_Len2*sizeof(T)]; зачем ++?
4. Еще не нравиться использование, точнее вот это:
new(V.new_back()) Class(1);
Class &E = *new(V.new_back()) Class();
Я предлагаю немного изменить код и получить что-то вроде этого:
Использование:
Код:
#include <new>
#include <memory.h>
template <class T, size_t SubbufSize=256, size_t PtrArrayIncrement=256>
class vectorus
{
private:
// Для проверки валидности параметров шаблона
template<size_t> struct ERROR_TEMPLATE_PARAMETER{};
template<> struct ERROR_TEMPLATE_PARAMETER<0>;
typedef T* TSubbuf;
typedef TSubbuf* TSubbufArray;
vectorus(const vectorus&);
vectorus& operator=(const vectorus&);
TSubbufArray m_PtrArray;
size_t m_PtrArrayLen;
size_t m_Count;
public:
vectorus()
{
// Проверка валидности параметров шаблона
ERROR_TEMPLATE_PARAMETER< SubbufSize >();
ERROR_TEMPLATE_PARAMETER< PtrArrayIncrement >();
m_PtrArray = NULL;
m_PtrArrayLen = 0;
m_Count = 0;
}
~vectorus()
{ empty(); }
size_t size() const
{ return m_Count; }
T& operator[](size_t i)
{
if (i>=m_Count) throw("vectorus:: - out of range");
return m_PtrArray[i/SubbufSize][i%SubbufSize];
}
const T& operator[](size_t i) const
{ return operator[](i); }
void empty()
{
if(m_Count>0)
{
for(size_t i=0; i<m_Count; i++) operator[](i).~T();
for( size_t i=(m_Count-1)/SubbufSize+1; i; delete[] reinterpret_cast<char*>(m_PtrArray[--i]) );
m_Count = 0;
}
if(m_PtrArray)
{
delete[] m_PtrArray;
m_PtrArray = NULL;
}
}
T* new_back()
{
// проверка необходимости создания нового подбуфера
if(m_Count%SubbufSize == 0)
{
// проверка необходимости увеличения массива указателей
size_t fil = m_Count/SubbufSize;
if(fil >= m_PtrArrayLen)
{ // расширение массива указателей
size_t oldLen = m_PtrArrayLen;
m_PtrArrayLen += PtrArrayIncrement;
TSubbufArray b = new TSubbuf[m_PtrArrayLen];
if(m_PtrArray)
{
memcpy(b, m_PtrArray, oldLen*sizeof(TSubbuf));
delete[] m_PtrArray;
}
m_PtrArray = b;
}
// создание нового подмассива
m_PtrArray[fil] = reinterpret_cast<TSubbuf>(new char[SubbufSize*sizeof(T)]);
}
return &operator[](m_Count++);
}
void cut_back()
{
if(m_Count>0)
{
operator[](m_Count-1).~T();
m_Count--;
if(m_Count%SubbufSize == 0)
delete[] reinterpret_cast<char*>(m_PtrArray[m_Count/SubbufSize]);
}
}
// Вызов конструктора T с количеством аргументов от 0 до 9
T& add_back()
{ return *new( new_back() ) T; }
template<class T1>
T& add_back(T1 arg1)
{ return *new( new_back() ) T(arg1); }
template<class T1,class T2>
T& add_back(T1 arg1,T2 arg2)
{ return *new( new_back() ) T(arg1,arg2); }
template<class T1,class T2,class T3>
T& add_back(T1 arg1,T2 arg2,T3 arg3)
{ return *new( new_back() ) T(arg1,arg2,arg3); }
template<class T1,class T2,class T3,class T4>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4); }
template<class T1,class T2,class T3,class T4,class T5>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4,T5 arg5)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4,arg5); }
template<class T1,class T2,class T3,class T4,class T5,class T6>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4,T5 arg5,T6 arg6)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4,arg5,arg6); }
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4,T5 arg5,T6 arg6,T7 arg7)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4,arg5,arg6,arg7); }
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7,class T8>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4,T5 arg5,T6 arg6,T7 arg7,T8 arg8)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4,arg5,arg6,arg7,arg8); }
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7,class T8,class T9>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4,T5 arg5,T6 arg6,T7 arg7,T8 arg8,T9 arg9)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4,arg5,arg6,arg7,arg8,arg9); }
};
#include <memory.h>
template <class T, size_t SubbufSize=256, size_t PtrArrayIncrement=256>
class vectorus
{
private:
// Для проверки валидности параметров шаблона
template<size_t> struct ERROR_TEMPLATE_PARAMETER{};
template<> struct ERROR_TEMPLATE_PARAMETER<0>;
typedef T* TSubbuf;
typedef TSubbuf* TSubbufArray;
vectorus(const vectorus&);
vectorus& operator=(const vectorus&);
TSubbufArray m_PtrArray;
size_t m_PtrArrayLen;
size_t m_Count;
public:
vectorus()
{
// Проверка валидности параметров шаблона
ERROR_TEMPLATE_PARAMETER< SubbufSize >();
ERROR_TEMPLATE_PARAMETER< PtrArrayIncrement >();
m_PtrArray = NULL;
m_PtrArrayLen = 0;
m_Count = 0;
}
~vectorus()
{ empty(); }
size_t size() const
{ return m_Count; }
T& operator[](size_t i)
{
if (i>=m_Count) throw("vectorus:: - out of range");
return m_PtrArray[i/SubbufSize][i%SubbufSize];
}
const T& operator[](size_t i) const
{ return operator[](i); }
void empty()
{
if(m_Count>0)
{
for(size_t i=0; i<m_Count; i++) operator[](i).~T();
for( size_t i=(m_Count-1)/SubbufSize+1; i; delete[] reinterpret_cast<char*>(m_PtrArray[--i]) );
m_Count = 0;
}
if(m_PtrArray)
{
delete[] m_PtrArray;
m_PtrArray = NULL;
}
}
T* new_back()
{
// проверка необходимости создания нового подбуфера
if(m_Count%SubbufSize == 0)
{
// проверка необходимости увеличения массива указателей
size_t fil = m_Count/SubbufSize;
if(fil >= m_PtrArrayLen)
{ // расширение массива указателей
size_t oldLen = m_PtrArrayLen;
m_PtrArrayLen += PtrArrayIncrement;
TSubbufArray b = new TSubbuf[m_PtrArrayLen];
if(m_PtrArray)
{
memcpy(b, m_PtrArray, oldLen*sizeof(TSubbuf));
delete[] m_PtrArray;
}
m_PtrArray = b;
}
// создание нового подмассива
m_PtrArray[fil] = reinterpret_cast<TSubbuf>(new char[SubbufSize*sizeof(T)]);
}
return &operator[](m_Count++);
}
void cut_back()
{
if(m_Count>0)
{
operator[](m_Count-1).~T();
m_Count--;
if(m_Count%SubbufSize == 0)
delete[] reinterpret_cast<char*>(m_PtrArray[m_Count/SubbufSize]);
}
}
// Вызов конструктора T с количеством аргументов от 0 до 9
T& add_back()
{ return *new( new_back() ) T; }
template<class T1>
T& add_back(T1 arg1)
{ return *new( new_back() ) T(arg1); }
template<class T1,class T2>
T& add_back(T1 arg1,T2 arg2)
{ return *new( new_back() ) T(arg1,arg2); }
template<class T1,class T2,class T3>
T& add_back(T1 arg1,T2 arg2,T3 arg3)
{ return *new( new_back() ) T(arg1,arg2,arg3); }
template<class T1,class T2,class T3,class T4>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4); }
template<class T1,class T2,class T3,class T4,class T5>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4,T5 arg5)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4,arg5); }
template<class T1,class T2,class T3,class T4,class T5,class T6>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4,T5 arg5,T6 arg6)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4,arg5,arg6); }
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4,T5 arg5,T6 arg6,T7 arg7)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4,arg5,arg6,arg7); }
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7,class T8>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4,T5 arg5,T6 arg6,T7 arg7,T8 arg8)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4,arg5,arg6,arg7,arg8); }
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7,class T8,class T9>
T& add_back(T1 arg1,T2 arg2,T3 arg3,T4 arg4,T5 arg5,T6 arg6,T7 arg7,T8 arg8,T9 arg9)
{ return *new( new_back() ) T(arg1,arg2,arg3,arg4,arg5,arg6,arg7,arg8,arg9); }
};
Использование:
Код:
struct A
{
A(int){}
A(int,int*){}
};
vectorus<A> V;
int i;
V.add_back(i);
V.add_back(i,&i);
V.cut_back();
{
A(int){}
A(int,int*){}
};
vectorus<A> V;
int i;
V.add_back(i);
V.add_back(i,&i);
V.cut_back();
Цитата:
Originally posted by Green
Предложения, замечания принимаются?
Предложения, замечания принимаются?
Конечно. Затем и постилось.
Цитата:
1. Для чего такие сложности c BufIncrement? Не проще ли использовать два параметра: размер подмассива в элементах и шаг приращения массива указателей?
Реализация шаблона проще, а использование будет сложнее - пользователю нужно задавать два параметра вместо одного.
Интуитивно мне кажется, что одинаковый размер подмассива и приращения - как раз оптимально.
Цитата:
2. Массив указателей не уменьшается (по граничным условиям) в cat_back, это такая задумка? Есть ли необходимость держать неиспользуемые объемы памяти? Тогда m_Len1 будет не нужен.
Уменьшать действительно нужно (только, естественно, не менее, чем на инкремент).
Насчет m_Len1 тоже согласен.
Цитата:
3. В строке m_Buffer[fil1++]=new char[m_Len2*sizeof(T)]; зачем ++?
Исключительно для сохранения изначальной семантики fil1. Вдруг потом добавится код, который будет ее дальше использовать.
Цитата:
4. Еще не нравиться использование, точнее вот это:
new(V.new_back()) Class(1);
Class &E = *new(V.new_back()) Class();
new(V.new_back()) Class(1);
Class &E = *new(V.new_back()) Class();
Мне это тоже не нравится.
Честно признаться, я не знал той возможности синтаксиса, которую ты использовал для передачи параметров. Так действительно лучше.