Контейнеры для Swap-able объектов - C/C++

Контейнеры STL требуют от хранимых объектов наличия конструктора копирования и оператора присваивания.

А я хочу хранить объекты, которые имеют простые и быстрые конструктор по умолчанию и функцию swap, но не могут копироваться (или могут, но неэффективно).

Мне кажется, что вполне возможно реализовать контейнеры, похожие на стандартные, но использующие конструктор по умолчанию и функцию swap (вместо конструктора копирования и оператора присваивания). И, наверное, я на днях попробую это сделать (начну с вектора).

Вот только меня терзают сомнения:
1) Может, уже существуют подобные контейнеры? (В Boost-е их вроде нет).
Или какие-нибудь адаптеры к стандартным контейнерам?

2) Может, эта идея изначально порочная и бессмысленная?

Здравствуйте, Atminav, Вы писали:

A>...
A>А я хочу хранить объекты, которые имеют простые и быстрые конструктор по умолчанию и функцию swap, но не могут копироваться (или могут, но неэффективно).
A>...

А что мешает хранить указатели на объекты и их swap-ать? Да и копируются указатели довольно эффективно

Здравствуйте, Аноним, Вы писали:

А>А что мешает хранить указатели на объекты и их swap-ать? Да и копируются указатели довольно эффективно

Нужно выделять память, не забывать освобождать ее, да еще следить, чтобы указатель не был 0... Кроме того, указатели — это лишний уровень косвенности, лишнии операции при обращении к объекту.

Вообще, не хочется без лишней необходимости пользоваться new/delete. Так что указатели, даже смарт-указатели, я не рассматриваю.

Конечно, любой контейнер тоже пользуется new/delete. Но контейнер, который хранит сами объекты, а не указатели на них, выделяет память только при создании, изменении размера и уничтожении контейнера, а при изменении элементов он к аллокатору, по идее, обращаться не должен.

Здравствуйте, Atminav, Вы писали:

Поищи в форуме по слову "movable".

Здравствуйте, Atminav, Вы писали:

A>Нужно выделять память, не забывать освобождать ее, да еще следить, чтобы указатель не был 0... Кроме того, указатели — это лишний уровень косвенности, лишнии операции при обращении к объекту.
По поводу косвенной адресации не так уж она и долго происходит

Что мешает использовать указатели !=0 и без выделения памяти?

MyType A[N];
MyType* idx[N];
for(int i=0;i<N;i++) idx[i]=A+i;

A>Вообще, не хочется без лишней необходимости пользоваться new/delete. Так что указатели, даже смарт-указатели, я не рассматриваю.
не хочется н вызывай. Организуй выделения элементов страницами. На каждой странице по N элементов сразу выделяется.

enum { PageShift=12, PageLimit=1<<PageShift, PageMask=PageLimit-1 };
int N=mongo();
MyType** pages=makeSomePages(N,PageLimit);
...
vector<MyType*> idx;
for(int i=0;i<N;i++) idx.push_back(pages[i>>12]+(i&PageMask));

Если хочется можеш им и конструкторы вызывать переопределив void* operator new(void* where,size_t size);

А в сбалансированном дереве хранить указатели или номера элементов и работать уже с ними. Указатель всего одно машинное слово по сравнению со структурой которая может занимать килобайты.

Здравствуйте, Atminav, Вы писали:

A>Контейнеры STL требуют от хранимых объектов наличия конструктора копирования и оператора присваивания.
A>А я хочу хранить объекты, которые имеют простые и быстрые конструктор по умолчанию и функцию swap, но не могут копироваться (или могут, но неэффективно).

Так не могут, или неэффективно могут? Это две совершенно разные ситуации.

Если неэффективно могут:

1. Можно понадеяться, что для внутренних целей (например, при вставке/удалении/перемещении элементов вектора) STL использует всё-таки swap(), а не копирование.
2. Сделай операции вставки двухступенчатыми. Это всего лишь вопрос практики применения контейнеров.

vec.push_back(Value());
swap(vec.back(), v);

Если не могут:

Прямая дорога к указателям с разделяемым владением.

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, Atminav, Вы писали:

A>Контейнеры STL требуют от хранимых объектов наличия конструктора копирования и оператора присваивания.

A>А я хочу хранить объекты, которые имеют простые и быстрые конструктор по умолчанию и функцию swap, но не могут копироваться (или могут, но неэффективно).

A>Мне кажется, что вполне возможно реализовать контейнеры, похожие на стандартные, но использующие конструктор по умолчанию и функцию swap (вместо конструктора копирования и оператора присваивания). И, наверное, я на днях попробую это сделать (начну с вектора).

A>Вот только меня терзают сомнения:
A>1) Может, уже существуют подобные контейнеры? (В Boost-е их вроде нет).
A> Или какие-нибудь адаптеры к стандартным контейнерам?

A>2) Может, эта идея изначально порочная и бессмысленная?

Boost.PtrContainers подойдет ?

Здравствуйте, Atminav, Вы писали:

A>2) Может, эта идея изначально порочная и бессмысленная?

Со swap есть небольшие трудности, так как всё время надо порождать/разрушать пустые эл-ты.

Тогда уж проще иметь перегруженную функцию типа move_container_element( void* dst, T* src ), которая для копируемых объектов реализуется так:

template<typename T>
void move_container_element( void* dst, T* src )
{
    new( dst ) T( *src );
    src->~T();
}

для swap-able объектов так:

template<typename T>
void move_container_element( void* dst, T* src )
{
    std::swap( *new( dst )T, *src );
    src->~T();
}

а для чего-нибудь вроде POD или даже вроде auto_ptr или shared_ptr так:

template<typename T>
void move_container_element( void* dst, T* src )
{
    memmove( dst, src, sizeof( *src ) );
}

Ну а потом реализуешь контейнер через вызовы такой функции...

В моей любимой библиотеке сделано примерно так, только там ещё много всяких хитростей на тему о том, как определять такого типа функции автоматически...

Здравствуйте, _nn_, Вы писали:

A>>Контейнеры STL требуют от хранимых объектов наличия конструктора копирования и оператора присваивания.

A>>А я хочу хранить объекты, которые имеют простые и быстрые конструктор по умолчанию и функцию swap, но не могут копироваться (или могут, но неэффективно).

__>Boost.PtrContainers подойдет ?

Так он, вроде, требует клонируемости (практически то же, что и копируемость) объектов и клонирует их при вставке в контейнер.

Здравствуйте, Кодт, Вы писали:

A>>хранить объекты, которые имеют простые и быстрые конструктор по умолчанию и функцию swap, но не могут копироваться (или могут, но неэффективно).

К>Так не могут, или неэффективно могут? Это две совершенно разные ситуации.
Помоему, разница невелика. В одном случае, их НЕЛЬЗЯ копировать, а в другом — НЕЖЕЛАТЕЛЬНО.

К>Если неэффективно могут:

К>1. Можно понадеяться, что для внутренних целей (например, при вставке/удалении/перемещении элементов вектора) STL использует всё-таки swap(), а не копирование.
Сомнительно. Откуда STL знает, что эффективнее: swap или копирование? Основной шаблон swap использует три копирования и один деструктор, так что он в три раза менее эффективен, чем копирование. Однако, для некоторых объектов swap может быть на порядки эфективнее, чем копирование.

К>2. Сделай операции вставки двухступенчатыми. Это всего лишь вопрос практики применения контейнеров.
К>

К>vec.push_back(Value());
К>swap(vec.back(), v);
К>

К>
Если при операции push_back произойдет расширение выделенной памяти, то потребуется копирование всех уже сохраненых в контейнере объектов

Здравствуйте, Atminav, Вы писали:

A>>>хранить объекты, которые имеют простые и быстрые конструктор по умолчанию и функцию swap, но не могут копироваться (или могут, но неэффективно).

К>>Так не могут, или неэффективно могут? Это две совершенно разные ситуации.
A>Помоему, разница невелика. В одном случае, их НЕЛЬЗЯ копировать, а в другом — НЕЖЕЛАТЕЛЬНО.

Разница гигантская.
Если некий объект вовсю эксплуатирует свою идентичность, либо монопольно владеет ресурсами, то копирование запрещено.
А если это просто тяжеловесное значение (большая строка), то копировать или нет — лишь вопрос эффективности. Кстати, посмотри на идиому COW (copy on write).

К>>Если неэффективно могут:

К>>1. Можно понадеяться, что для внутренних целей (например, при вставке/удалении/перемещении элементов вектора) STL использует всё-таки swap(), а не копирование.
A>Сомнительно. Откуда STL знает, что эффективнее: swap или копирование?

STL думает, что swap эффективнее.

A> Основной шаблон swap использует три копирования и один деструктор, так что он в три раза менее эффективен, чем копирование.
A> Однако, для некоторых объектов swap может быть на порядки эфективнее, чем копирование.

И именно для этих объектов пишется специализация swap. Например, для всех контейнеров.
А если пользователь тормоз, и положился на основной шаблон (реализованный через копирования и присваивания) — его программа просто будет работать медленнее.

К>>2. Сделай операции вставки двухступенчатыми. Это всего лишь вопрос практики применения контейнеров.
К>>

К>>vec.push_back(Value());
К>>swap(vec.back(), v);
К>>

К>>
A>Если при операции push_back произойдет расширение выделенной памяти, то потребуется копирование всех уже сохраненых в контейнере объектов

Можно подумать, если ты сделаешь

vec.push_back(v);
// или
vec.push_back_and_swap(v);

этого копирования не произойдёт?

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, Atminav, Вы писали:

A>Здравствуйте, _nn_, Вы писали:

A>>>Контейнеры STL требуют от хранимых объектов наличия конструктора копирования и оператора присваивания.

A>>>А я хочу хранить объекты, которые имеют простые и быстрые конструктор по умолчанию и функцию swap, но не могут копироваться (или могут, но неэффективно).

__>>Boost.PtrContainers подойдет ?

A>Так он, вроде, требует клонируемости (практически то же, что и копируемость) объектов и клонирует их при вставке в контейнер.

См. тут:

3. Can be used for types that are neither Assignable nor Copy Constructible.

The Clone Allocator concept

Здравствуйте, Atminav, Вы писали:

A>А я хочу хранить объекты, которые имеют простые и быстрые конструктор по умолчанию и функцию swap, но не могут копироваться (или могут, но неэффективно).

A> Или какие-нибудь адаптеры к стандартным контейнерам?
Мне кажется правильное направление — не так сложно создать swapable адаптер для объектов. Но, думается что лучше использовать некоторую связку:
адаптер + надстройка над стандартными контейнерами с ограниченными возможностями (что-бы можно было следить за операциями, когда требуется действительно копирование, а не swap).

Ещё следует не забывать о том, что с контейнерами могут работать различные алгоритмы, которые могут подразумевать, что переданные итераторы указывают на copy-constructable данные.

Надеюсь у Вас появятся хорошие идеи

	От:	Atminav
	Дата:	10.12.07 21:58
	Оценка:

	От:	Аноним
	Дата:	10.12.07 22:27
	Оценка:

	От:	Atminav
	Дата:	11.12.07 06:36
	Оценка:

	От:	Bell
	Дата:	11.12.07 09:22
	Оценка:

	От:	Аноним
	Дата:	11.12.07 14:36
	Оценка:

	От:	Кодт
	Дата:	12.12.07 09:37
	Оценка:

	От:	_nn_
	Дата:	12.12.07 14:30
	Оценка:

	От:	spring
	Дата:	13.12.07 15:02
	Оценка: