Отделено отсюда: viewtopic.php?p=40457#p40457Извините за длинное сообщение.
Высказывание интересно. И очень - из жизни.
После многих лет применения stl и прочего похожего (и своего подобного), написал свой класс очереди-списка.
Совместимость по типу нужна только в операции получения элемента. В остальном - самодостаточная вещь.
Перевести на КП, думаю, будет не так сложно. Потокобезопасность должна обеспечиваться внешними средствами.
Код:
//----------------------------------------------------------------------------
class Queue
{
public:
typedef void(FreeObjectFunc_t) ( void* object );
typedef bool(FindIfCheckFunc_t)( void* object, void *data );
typedef void(ForEachFunc_t) ( void* object, void *data );
private:
struct QueueItem
{
QueueItem *prev_, *next_;
void* object_;
QueueItem( QueueItem *prev = NULL, QueueItem *next = NULL, void* object = NULL )
: prev_( prev ), next_( next ), object_( object )
{ };
};
QueueItem *freeItems_;
QueueItem *items_;
QueueItem *last_;
int count_;
int capacityDelta_;
FreeObjectFunc_t *pFreeObjectFunc_;
static void FreeQueueItems( QueueItem* *items, FreeObjectFunc_t *pFreeObjectFunc );
void InnerRemove( QueueItem* item );
void AddToFree ( QueueItem* item );
void FreeItem ( QueueItem* item );
void MakeFirst ( QueueItem* item );
public:
//---------------------------------------------------------------------------
Queue( FreeObjectFunc_t *pFreeObjectFunc = NULL, int startCapacity = 16, int capacityDelta = 4 );
~Queue();
//---------------------------------------------------------------------------
int Count ();
bool Put ( void* object );
void* Front ();
void* Get ();
bool Remove( void* object );
//---------------------------------------------------------------------------
bool Has ( void* object, bool makeFirst = false );
void* FindIf ( FindIfCheckFunc_t *pCheckFunc, void *data, bool makeFirst = false );
void ForEach( ForEachFunc_t *pForEachFunc, void *data = NULL );
//---------------------------------------------------------------------------
};
//----------------------------------------------------------------------------
//---------------------------------------------------------------------------
Queue::Queue( FreeObjectFunc_t *pFreeObjectFunc, int startCapacity, int capacityDelta )
: freeItems_ ( NULL ),
items_ ( NULL ),
last_ ( NULL ),
count_ ( 0 ),
capacityDelta_ ( capacityDelta ),
pFreeObjectFunc_( pFreeObjectFunc )
{
while( startCapacity-- )
{
QueueItem *item;
try{ item = new QueueItem( NULL, freeItems_, NULL ); }catch(...){ item = NULL; }
if( ! item )
throw -1;
freeItems_ = item;
}
}
//---------------------------------------------------------------------------
void Queue::FreeQueueItems( QueueItem* *items, FreeObjectFunc_t *pFreeObjectFunc )
{
while( *items )
{
QueueItem *item = *items; *items = item->next_;
if( pFreeObjectFunc && item->object_ )
(*pFreeObjectFunc)( item->object_ );
delete item;
}
}
Queue::~Queue()
{
FreeQueueItems( &items_, pFreeObjectFunc_ );
FreeQueueItems( &freeItems_, NULL );
}
//---------------------------------------------------------------------------
int Queue::Count()
{
return count_;
}
//---------------------------------------------------------------------------
bool Queue::Put( void* object )
{
QueueItem *item = freeItems_;
if( item )
freeItems_ = item->next_;
else
{
try{ item = new QueueItem(); }catch(...){ item = NULL; }
if( ! item )
return false;
if( (capacityDelta_-1) > 0 )
for( int i = 1; i < capacityDelta_; ++i )
{
QueueItem *freeItem;
try{ freeItem = new QueueItem( NULL, freeItems_, NULL ); }catch(...){ freeItem = NULL; }
if( ! freeItem )
break;
freeItems_ = freeItem;
}
}
*item = QueueItem( last_, NULL, object );
if( last_ )
last_->next_ = item;
else
items_ = item;
last_ = item;
++count_;
return true;
}
//---------------------------------------------------------------------------
void* Queue::Front()
{
return (items_) ? items_->object_ : NULL ;
}
void Queue::InnerRemove( QueueItem* item )
{
if( item->prev_ )
item->prev_->next_ = item->next_;
else
items_ = item->next_;
if( item->next_ )
item->next_->prev_ = item->prev_;
else
last_ = item->prev_;
item->next_ = item->prev_ = NULL;
}
void Queue::AddToFree( QueueItem* item )
{
item->next_ = freeItems_;
freeItems_ = item;
}
void Queue::FreeItem( QueueItem* item )
{
InnerRemove( item );
AddToFree( item );
--count_;
}
void Queue::MakeFirst( QueueItem* item )
{
InnerRemove( item );
item->next_ = items_;
items_ = item;
}
//---------------------------------------------------------------------------
void* Queue::Get()
{
QueueItem *item = items_; if( ! item ) return NULL;
FreeItem( item );
return item->object_;
}
//---------------------------------------------------------------------------
bool Queue::Remove( void* object )
{
bool res;
QueueItem *item = items_;
for( ; item && item->object_ != object ; item = item->next_ ) /* !!! */ ;
if( (res = (item != NULL)) )
FreeItem( item );
return res;
}
//---------------------------------------------------------------------------
void* Queue::FindIf( FindIfCheckFunc_t *pCheckFunc, void *data, bool makeFirst )
{
void* object;
if( ! pCheckFunc )
object = NULL;
else
{
QueueItem *item = items_;
for( ; item && !(*pCheckFunc)( item->object_, data ) ; item = item->next_ ) /* !!! */ ;
if( ! item )
object = NULL;
else
{
object = item->object_;
if( makeFirst && item != items_ )
MakeFirst( item );
}
}
return object;
}
//---------------------------------------------------------------------------
bool Queue::Has( void* object, bool makeFirst )
{
QueueItem *item = items_;
for( ; item && (item->object_ != object) ; item = item->next_ ) /* !!! */ ;
if( ! item )
return false;
if( makeFirst && item != items_ )
MakeFirst( item );
return true;
}
//-----------------------------------------------------------------------------
void Queue::ForEach( ForEachFunc_t *pForEachFunc, void *data )
{
if( pForEachFunc )
{
for( QueueItem *item = items_; item ; item = item->next_ )
(*pForEachFunc)( item->object_, data );
}
}