Подскажите с STL

[Алексей++]

ой, я и забыл. Вот, что получилось, будучи заточенное для моих нужд и специфику применения ))
Только вряд ли кому-то это пригодится.

Код:

#pragma once

#include <vector>

	//CSimpleTypesFIFO стек FIFO для простых типов.
	//Под простыми понимаются типы, которые можно безболезненно
	//копировать побайтово (например, функцией memmove)
	//
	//Работает следующим образом: пока возможно, добавляет элементы в конец буфера.
	//Если достигнут конец буфера, то делается попытка сдвинуть все данные в начало
	//буфера (ведь там могут быть уже извлечённые элементы) и новые данные пишутся
	//снова в конец. Если стек переполнен, то ничего не делается
	//Таким образом, массив элементов всегда линейный и сплошной
	template<typename ASimpleType>
	class CSimpleTypesFIFO
	{
		std::vector<ASimpleType> m_buff;
		DWORD m_BegIndx;
		DWORD m_EndIndx;//всегда m_EndIndx>=m_BegIndx

	public:

		CSimpleTypesFIFO(DWORD dwdMaxLen=0)
		{
			m_BegIndx=0;
			m_EndIndx=0;
			m_buff.resize(dwdMaxLen);
		}

		void Clear()
		{
			m_BegIndx=0;
			m_EndIndx=0;
		}

		//вернёт true, если было сжато пустое место
		bool DeleteEmptySpace()
		{
			if(!m_buff.size())return false;
			if(!m_BegIndx)return false;//нечего сжимать

			if(m_BegIndx==m_EndIndx)
			{
				//стек полностью пуст
				m_BegIndx=0;
				m_EndIndx=0;
			}
			else
			{
				DWORD count=GetDataSize();
				//сдвигаем всё к началу вектора
				memmove(&m_buff[0],&m_buff[m_BegIndx],count*sizeof(m_buff[0]));
				//корректируем индексы
				m_BegIndx=0;
				m_EndIndx=m_BegIndx+count;
			}

			return true;
		}

		//возвращает, сколько элементов можно положить в стек
		DWORD GetCommonEmptySize() const
		{
			if(!m_buff.size())return 0;
			ASSERT(m_buff.size()>=GetDataSize());
			return m_buff.size() -GetDataSize();
		}

		//возвращает полный размер всего буфера
		DWORD GetCommonBufferSize() const
		{
			return m_buff.size();
		}

		void Resize(DWORD dwdMaxLen)
		{
			if(m_buff.size()==dwdMaxLen)return;

			//сдвигаем всё к началу
			DeleteEmptySpace();
			if(!dwdMaxLen)
			{
				m_buff.resize(0);
				m_BegIndx=0;
				m_EndIndx=0;
				return;
			}

			//запоминаем предыдущее количество элементов в стеке
			DWORD count=GetDataSize();

			if(count>dwdMaxLen)
			{
				//удалить самые первые элементы
				DWORD dwdToDel=(count-dwdMaxLen);
				//новое количество
				count=dwdMaxLen;

				ASSERT(dwdToDel>0);
				ASSERT(count>0);

				//сдвигаем всё к началу вектора
				memmove(&m_buff[0],&m_buff[dwdToDel-1],count*sizeof(m_buff[0]));
				//корректируем индексы
				m_BegIndx=0;
				m_EndIndx=m_BegIndx+count;
			}

			//меняем размер стека
			m_buff.resize(dwdMaxLen,0);

			count=min(count,m_buff.size());

			m_BegIndx=0;
			m_EndIndx=m_BegIndx+count;
		}

		//возвращает длину пустого хвоста
		DWORD GetTailSize() const
		{
			if(!m_buff.size())return 0;
			//if(!GetDataSize())return 0;
			ASSERT(m_buff.size()>=m_EndIndx);
			return m_buff.size() -m_EndIndx;
		}

		ASimpleType* GetTailBeg() const
		{
			if(!m_buff.size())return 0;

			if(m_BegIndx>=m_buff.size())
			{
				ASSERT(m_BegIndx==m_EndIndx);
				ASSERT(m_BegIndx==m_buff.size());
				return 0;
			}

			if(m_EndIndx==m_buff.size())return 0;
			ASSERT(m_EndIndx<m_buff.size());
			(ASimpleType*)return &m_buff[m_EndIndx];
		}

		DWORD GetDataSize() const
		{
			ASSERT(m_EndIndx>=m_BegIndx);
			return m_EndIndx -m_BegIndx;
			//0 1 2 3 4 5 6 7 8 9| 10
			//. . . * * * * . . .|
			//      B       E    |
			//
			//7-3 == 4
		}

		ASimpleType* GetDataBeg() const
		{
			if(!m_buff.size())return 0;
			if(m_BegIndx>=m_buff.size())
			{
				ASSERT(m_BegIndx==m_EndIndx);
				ASSERT(m_BegIndx==m_buff.size());
				return 0;
			}

			return (ASimpleType*)&m_buff[m_BegIndx];
		}

		//сказать классу, что в хвост вручную записали элементы
		//(количество - не более GetTailSize() - на совести программиста,
		//ведь счётчик то не сдвинется дальше, но память будет уже испорчена
		//извне)
		DWORD ImitatePush(DWORD dwdCount)
		{
			ASSERT(dwdCount<=GetTailSize());
			DWORD dwdToSave=min(dwdCount,GetTailSize());
			m_EndIndx+=dwdToSave;
			ASSERT(m_EndIndx<=m_buff.size());
			return dwdToSave;
		}

		//сказать классу, что из начала вручную извлечены элементы
		//(количество - не более GetDataSize() )
		void ImitatePop(DWORD dwdCount)
		{
			ASSERT(m_BegIndx<m_buff.size());
			m_BegIndx+=min(dwdCount,GetDataSize());
			ASSERT(m_BegIndx<=m_EndIndx);

			ASSERT(m_BegIndx<=m_buff.size());
			ASSERT(m_EndIndx<=m_buff.size());

			if(m_BegIndx==m_EndIndx)
			{
				m_BegIndx=0;
				m_EndIndx=0;
			}
		}
	};

[Вад]

То есть, он у тебя не кольцевой, ты его просто расширяешь для дозаписи?
Я бы, наверное, сделал по образцу stl - сделал бы вставку в него push(IterType first, IterType last), а доступ к памяти не открывал бы. Правда, там ещё извлечение данных из головы сразу куском...

[Алексей++]

Вад, нет, я не расширяю, размер буфера постоянный. Аналогия с кольцом в том, что begin и end (m_BegIndx и m_EndIndx) "ползут" по буферу в старшие адреса - при добавлении данных сдвигается end, при выборке - begin. То есть в начале буфера начинает образовываться "пустота". Как только end сдвинуть некуда, пустота уничтожается сдвигом данные в начало буфера, а новые данные начинают записываться в освободившуюся конечную часть.

Если весь буфер оказался забит, а сообщение по протоколу так и не выделено, значит сообщение слишком велико для буфера - буфер просто очищу.
(последнее предложение - это внешняя логика, а не класса)

Данные принимаются произвольными кусками, а потом только анализируются на протокол. Отсюда такая открытость памяти класса - для простоты

Чего добивался:
1) отсутствие переаллокации
2) терпимо редкий вызов memmove (сообщения много короче буфера)
3) запись в буфер кусками, и чтение тоже кусками
4) массив с данными непрерывен

[Вад]

Теперь понятно, почему так

[Dimka]

Как только end сдвинуть некуда, пустота уничтожается сдвигом данные в начало буфера, а новые данные начинают записываться в освободившуюся конечную часть.

По-моему это лишнее действие. Достаточно end перенести в начало. При этом лишь несколько усложнится определение количества занятых и свободных, а всё остальное останется более-менее без изменений.

[Алексей++]

Dimka, не, не пойдёт: для пользователя класса массив непрерывен

(4-й пункт добавил теперь )) )

[lapulya]

Я бы сделал так, как предложил Димка в последнем посте, а твой 4 пункт обеспечился бы твоей же функцией сдвига всего в начало ТОЛЬКО при запросе самого массива (т.е. при вставке/выборке мы ничего никуда не двигаем, а именно смещаем по кольцу, но при этом end может быть меньше begin). так будет быстрее работать.

[Антон (LogRus)]

какой смыл иметь непрерывный блок элементов?

[Алексей++]

Так пришлось бы сначала копировать часть массива, а только потом разбирать. Другие составляющие программы не умеют с кольцом работать, им подавай буфер и длину буфера

[Антон (LogRus)]

я полагал, что обычно сообщения обрабатываются по одному
почему внешняя хреновина должны пытаться выдрать их пачкой?

[Алексей++]

почему пачкой?

Ситуация такая: в кольце лежит неразобранный протокол. Чтобы обработать сообщение, нужно взять буфер с данными и подсунуть на обработку. Из данных выделяется одно сообщение и отдаётся на обработку дальше, а из кольца удаляется.

Если ситуация будет такой, что начало данный в конце буфера, а конец - в начале (как может быть в кольце), то функция разбора это не поймёт - ей нужен непрерывный участок памяти

Отдал сегодня тестировать программу в полевых условиях ))

Добавлено через 1 минуту и 23 секунды:
Антон (LogRus), я, кажется, понял, что тебя смущает. Дело в том, что у меня ASimpleType==BYTE , а не <некая структура>

[Антон (LogRus)]

тогда понятно, просто я бы наверное резал был на сообщения при входе в очередь

[Алексей++]

тогда понятно, просто я бы наверное резал бы на сообщения при входе в очередь

представь - с ком-порта идут данные, причём произвольными кусками (но в правильной очерёдности). Чтобы не терять время на таймаутах, я смотрю, сколько байтов лежит в буфере кома и сразу считываю все или меньше (таким образом таймауты не возникают, так как это количестко точно прочитается прямо сейчас).
Это всё читается в тот самый буфер.
Конечно, можно и разрезАть сразу, но это дополнительный контейнер, а если без дополнительного - то проще сразу из буфера доставать, никуда промежуточно не копируя. Что и сделал )

Или ты как имел в виду сделать ?

[Антон (LogRus)]

ну у тебя и так получилось промежуточное хранилище
наверное у меня черезмерное стремление всё усложнять

[Алексей++]

Написал, кстати, только что аналогичный (но реально кольцевой) буфер для элементов-контейнеров (щас тестировать сажусь )) )
Подойдёт, в принципе, для любых типов, не только контейнеров

Код:

	template<typename ASTLType>
	class CSTLTypesRING
	{
		CCriticalSection m_cris;
		struct s_ptr
		{
			ASTLType* m_p;

			s_ptr()
			{
				m_p=0;
			}

			void createIfNotYet()
			{
				if(!m_p)
				{
					m_p=new ASTLType;
				}
			}

			~s_ptr()
			{
				if(m_p)
				{
					delete m_p;
					m_p=0;
				}
			}

			void operator=(const s_ptr& o2)
			{
				ASTLType* p=o2.m_p;
				((s_ptr&)o2).m_p=0;
				m_p=p;
			}
		};

		typedef std::vector<s_ptr> td_buff;
		td_buff m_buff;
		DWORD m_BegIndx;//указывает на 1-й элемент
		DWORD m_EndIndx;//указывает на следующий за последним (поэтому размер буфера +1 - всегда один пустой элемент)
		//если пусто, то m_BegIndx==m_EndIndx

		bool m_bUseThreadSyncronizing;

	public:

		CSTLTypesRING(bool bUseThreadSyncronizing,DWORD dwdMaxLen=0)
		{
			m_bUseThreadSyncronizing=bUseThreadSyncronizing;
			DWORD dwdRealSize=dwdMaxLen+1;
			m_BegIndx=0;
			m_EndIndx=0;
			m_buff.resize(dwdRealSize);
		}

		//если размер меняется, всё предыдущие значения очищаются
		//если остаётся такой же - ничего не происходит
		void Resize(DWORD dwdMaxLen)
		{
			CSingleLock SL(&m_cris,m_bUseThreadSyncronizing?1:0);

			DWORD dwdRealSize=dwdMaxLen+1;
			if(m_buff.size()==dwdRealSize)return;

			m_buff.clear();
			m_buff.resize(dwdRealSize);
			m_BegIndx=0;
			m_EndIndx=0;
		}

		ASTLType* TestCanPush()
		{
			CSingleLock SL(&m_cris,m_bUseThreadSyncronizing?1:0);
			if(!IncrementEnd(true))return 0;
			m_buff[m_EndIndx].createIfNotYet();
			return m_buff[m_EndIndx].m_p;
		}

		//возвращает указатель на контейнер, который можно заполнять
		//если нет места - вернёт 0
		void Imitate_Push()
		{
			CSingleLock SL(&m_cris,m_bUseThreadSyncronizing?1:0);
			IncrementEnd();
		}

		ASTLType* TestCanPop()
		{
			CSingleLock SL(&m_cris,m_bUseThreadSyncronizing?1:0);
			if(!IncrementBeg(true))return 0;
			return m_buff[m_BegIndx].m_p;
		}

		void Imitate_Pop()
		{
			CSingleLock SL(&m_cris,m_bUseThreadSyncronizing?1:0);
			IncrementBeg();
		}

	private:
		bool IncrementEnd(bool bJustTest=false)
		{
			if(m_buff.size()<1)return false;
			ASSERT(m_EndIndx<m_buff.size());
			ASSERT(m_BegIndx<m_buff.size());

			if(m_BegIndx<=m_EndIndx)
			{
				//..*****+..|
				//..b....e..|
				//или
				//....+.....|
				//....b.....|
				//....e.....|

				if(m_EndIndx+1==m_buff.size())
				{
					//..*******+|
					//..b......e|
					//или
					//.........+|
					//.........b|
					//.........e|

					if(m_BegIndx==0)
					{
						//*********+|
						//b........e|
						//или
						//----------|
						//----------|
						//----------|
						return false;
						
					}
					else
					{
						//..*******+|
						//..b......e|
						//или
						//.........+|
						//.........b|
						//.........e|
						if(!bJustTest)m_EndIndx=0;
						return true;
					}
				}
				else
				{
					//..*****+..|
					//..b....e..|
					//или
					//....+.....|
					//....b.....|
					//....e.....|
					if(!bJustTest)m_EndIndx++;
					return true;
				}
			}
			else
			{
				//**+....***|
				//..e....b..|

				if(m_EndIndx+1==m_BegIndx)
				{
					//******+***|
					//......eb..|
					return false;
				}
				else
				{
					//**+....***|
					//..e....b..|
					if(!bJustTest)m_EndIndx++;
					return true;
				}
			}

			return false;//сюда не попадём
		}

		bool IncrementBeg(bool bJustTest=false)
		{
			if(m_buff.size()<1)return false;
			ASSERT(m_EndIndx<m_buff.size());
			ASSERT(m_BegIndx<m_buff.size());

			if(m_BegIndx==m_EndIndx)
			{
				//....+.....|
				//....b.....|
				//....e.....|
				return false;
			}

			if(!bJustTest)
			{
				if(m_BegIndx<m_EndIndx)
				{
					//..*****+..|
					//..b....e..|

					m_BegIndx++;
				}
				else
				{
					//**+....***|
					//..e....b..|

					if(m_BegIndx+1==m_buff.size())
					{
						m_BegIndx=0;
					}
					else
					{
						//**+....***|
						//..e....b..|
						m_BegIndx++;
					}
				}
			}


			return true;

		}
	};

вроде работает )

возможность использования при многопоточности также учтена - можно выбрать в конструкторе

Добавлено через 22 дня, 4 часа, 11 минут и 26 секунд:
любопытный спецэффект

Код:

std::string s;
s.resize(5,0);//теперь строка считает, что состоит из 5 нулей

std::string s2;

s2="111"+s2+"222"; // по сути, получается "111\0\0\0\0\0222"
//в итоге s2=="111"

эхъ. Час парился, пока допёрло

А применил resuze случайно при работе с mysql_real_escape_string

[Антон (LogRus)]

и правильно считает, очень правильное поведение

[Алексей++]

С точки зрения контейнера - да, но с точки зрения строки - лажа полная.

[Антон (LogRus)]

по моему и так и так правильно, всё таки string и Null Terminated String это разные вещи
Кстати, стринг отлично заменяет vector<char> сам много раз им пользовался при передаче данных по сети

[Алексей++]

Антон (LogRus), ну, скажем так, string - это аналог вектора с парочкой "но" :

1) свои методы, немного облегчающие работу со строками (хотя, до MFC::CString по удобству ему оооочень далеко )
2) всё-таки, string всегда принудительно ставит терминатор в конце данных.

[Антон (LogRus)]

не ставит он терминатор в конце данных, с чего ты взял

[Алексей++]

ну я же не задумываюсь об этом во время манипулирования со строками (в отличие от того, когда я использую для этого вектор), значит всё не просто так

[Антон (LogRus)]

ну это не означает, что они используют терминатор, значение длинны у них отдельным полем, есть нафига им терминатор.

[Вад]

нафига им терминатор.

Для корректного c_str()? Глянул исходник в VS 2008 - там при append вызывается функция:

Код:

	void __CLR_OR_THIS_CALL _Eos(size_type _Newsize)
		{	// set new length and null terminator
		_Traits::assign(_Myptr()[_Mysize = _Newsize], _Elem());
		}

[Алексей++]

Для корректного c_str()

о, да ) Я забыл упомянуть это чудо

[Антон (LogRus)]

c_str это преобразование string к null terminated string
и к внутреннему представлению данных он имеет отношение опосредованное
если ты оперируешь только std::string, то этот терминатор может никогда не появится, поэтому не аргумент

[lapulya]

если не ошибаюсь, то стандартом не регламентировано использование или неиспользование терминаторора в std::string, поэтому тут все завист от реализации. В 99% случаев терминатор в реализации есть, но понятно, что полагаться на это нельзя.

[Вад]

если не ошибаюсь, то стандартом не регламентировано использование или неиспользование терминаторора в std::string, поэтому тут все завист от реализации. В 99% случаев терминатор в реализации есть, но понятно, что полагаться на это нельзя.

Или, говоря проще, если кто оперирует не-нуль-терминированными строками - тот сам себе злобный буратино. А предохранители вроде вышеуказанного у MS предназначены для снятия ответственности с поставщика библиотеки за отстреленные ноги

[Алексей++]

у bitset есть метод none, который, так понимаю, возвращает истину, когда все биты сброшены. А как определить, что все биты установлены? Можно, конечно, flip()+none()+flip(), но это же несерьёзно

Добавлено через 35 минут и 24 секунды:
о, count()==size() подходит

[Антон (LogRus)]

опередил

[Алексей++]

но всё равно, поленились такой очевидный метод добавить

Добавлено через 13 дней, 9 часов, 9 минут и 22 секунды:
интересно, как-нибудь можно заставить std::search искать с конца, а не с начала ?