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

[Антон (LogRus)]

multi_map

[Алексей++]

Вот такое теперь безобразие, оформил в виде шаблона

Код:

	template<class Tid,class Tdata>
	class CDataCash
	{
		typedef DWORD Ttime;

		enum
		{
			e_max_count     =10000,
			e_old_TO        =30000,//~30 секунд
		};

		typedef std::map<Tid,Tdata> td_IdDataMap;
		typedef std::map<Ttime,Tid> td_TimeIdMap;
		typedef std::map<Tid,Ttime> td_IdTimeMap;

		typedef bool (*tdf_GetNewData)(
					void* pSomeThis,	//можно что угодно передать в колбэк
					typename const Tid Id,//идентификатор данных
					typename Tdata* pData//возвращаемые данные
					);

		typedef bool (*tdf_SetNewData)(
					void* pSomeThis,	//можно что угодно передать в колбэк
					typename const Tid Id,//идентификатор данных
					typename const Tdata* pData//данные
					);

		CCriticalSection m_cris;
		td_IdDataMap m_IdDataMap;
		td_TimeIdMap m_TimeIdMap;
		td_IdTimeMap m_IdTimeMap;


	public:

		void DeleteTheOldest()
		{
			CSingleLock(&m_cris,1);

			if(!m_TimeIdMap.size())return;

			//самое "молодое" время
			Ttime dwdCurrTime=-1;

			td_TimeIdMap::iterator it=m_TimeIdMap.end();
			it--;
			dwdCurrTime=it->first;

			//есть ли вообще чего удалять ?
			if(dwdCurrTime<e_old_TO)return;

			//время, меньше которого удалять
			Ttime dwdTimeToDelFrom_including=dwdCurrTime-e_old_TO;

			it=m_TimeIdMap.find(dwdTimeToDelFrom_including);
			if(it==m_TimeIdMap.end())return;
			it++;

			//собственно, чистим
			td_TimeIdMap::iterator itdel=m_TimeIdMap.begin();
			for(;;)
			{
				if(itdel==it)break;
				m_IdDataMap.erase(itdel->second);
				m_IdTimeMap.erase(itdel->second);
				itdel++;
			}

			m_TimeIdMap.erase(m_TimeIdMap.begin(),it);
		}

		void SetData(const Tid Id,Tdata* pData,void* pSomeThis,tdf_SetNewData GetNewDataCallBack)
		{
			//засовывание в БД
			GetNewDataCallBack(pSomeThis,Id,pData);
		}

		void GetData(const Tid IdToFind,Tdata* pData,void* pSomeThis,tdf_GetNewData GetNewDataCallBack)
		{
			if(!pData)return;

			CSingleLock(&m_cris,1);

			//-------------------------------------------------
			//находим новое время - оно понадобится в любом случае
			Ttime dwdNewTime=::GetTickCount();

			//нужно проконтролировать на переполнение и на повтор
			{
				//смотрим время самой свежей записи
				td_TimeIdMap::iterator it=m_TimeIdMap.end();
				it--;
				Ttime dwdLastTime=it->first;

				//повтор?
				if(dwdLastTime==dwdNewTime)
				{
					dwdNewTime++;
				}

				//переполнение?
				if(dwdNewTime<dwdLastTime)
				{
					m_IdDataMap.clear();

					m_TimeIdMap.clear();
					m_IdTimeMap.clear();
				}
			}

			//-------------------------------------------------
			//dwdNewTime - время для новой записи

			//ищем id в кеше
			td_IdDataMap::iterator it=m_IdDataMap.find(IdToFind);
			if(it!=m_IdDataMap.end())
			{
				//нашли
				*pData=it->second;

				//обновляем время
				m_TimeIdMap.erase(m_IdTimeMap[IdToFind]);
				m_IdTimeMap.erase(IdToFind);
			}
			else
			{
				//освобождаем место для новой записи
				Tid IdToDel;
				for(;m_IdDataMap.size()>=e_max_count;)
				{
					//определяем самый "старый" id

					IdToDel=m_TimeIdMap.begin()->second;

					//и удаляем
					m_TimeIdMap.erase(m_TimeIdMap.begin());

					m_IdTimeMap.erase(IdToDel);
					m_IdDataMap.erase(IdToDel);
				}

				//добавляем запись c IdToFind в мапы из базы
				Tdata data;

				//подгрузка из базы данных[IdToFind]
				if(!GetNewDataCallBack) return;
				if(!GetNewDataCallBack(pSomeThis,IdToFind,&data))return;

				//получена новая запись
				*pData=data;
				//вставляем текст
				m_IdDataMap[IdToFind]=data;
			}
		
			//обновляем время
			m_TimeIdMap[dwdNewTime]=IdToFind;
			m_IdTimeMap[IdToFind]=dwdNewTime;
		}
	};

Добавлено через 26 минут и 38 секунд:

multi_map

а это что ? )

Кстати, горожу я тут, горожу - а нет в STL уже какого-нибудь  готового кеша ?

[Антон (LogRus)]

есть map а есть multi_map, всё тоже самое, но можно дублировать ключи

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

[Алексей++]

есть multi_map, всё тоже самое, но можно дублировать ключи

разум отказался принять этот факт Не хочу дублировать

[Антон (LogRus)]

ага... А как быть с тем, что с GetTickCount индекс в m_TimeIdMap может слегка повториться ?

Мысль - эсли это произошло, то брать значение "время самой новой записи+1" , переполнение же в двух местах теперь надо учитывать

этот огород ты готов городить , а взять контейнер который не требует уникальных ключей не готов

[Алексей++]

LogRus, я не хочу доблированные ключи. Отмазался ? ))

[Антон (LogRus)]

дублирование ключей это нормальная практика

[Алексей++]

с multimap

Код:

	template<class Tid,class Tdata>
	class CDataCash
	{
		typedef DWORD Ttime;
		typedef std::map       <Tid,Tdata> td_IdDataMap;
		typedef std::multimap  <Ttime,Tid> td_TimeIdMmap;
		typedef std::map       <Tid,Ttime> td_IdTimeMap;

		typedef bool (*tdf_GetNewData)(
					void* pSomeThis,	//можно что угодно передать в колбэк
					typename const Tid Id,//идентификатор данных
					typename Tdata* pData//возвращаемые данные
					);

		typedef bool (*tdf_SetNewData)(
					void* pSomeThis,	//можно что угодно передать в колбэк
					typename const Tid Id,//идентификатор данных
					typename const Tdata* pData//данные
					);

		CCriticalSection m_cris;
		td_IdDataMap  m_IdDataMap;
		td_TimeIdMmap m_TimeIdMmap;
		td_IdTimeMap  m_IdTimeMap;

		const DWORD m_dwdMaxCount;
		const DWORD m_dwdLifeTimeOut;

	public:

		CDataCash(DWORD dwdMaxCount=10000,DWORD dwdLifeTimeOut=30000)
			:m_dwdMaxCount(dwdMaxCount)
			,m_dwdLifeTimeOut(dwdLifeTimeOut)
		{
		}

		void DeleteTheOldest()
		{
			CSingleLock(&m_cris,1);

			if(!m_TimeIdMmap.size())return;

			//самое "молодое" время
			Ttime dwdCurrTime=0;

			td_TimeIdMap::iterator it=m_TimeIdMmap.end();
			it--;
			dwdCurrTime=it->first;

			//есть ли вообще чего удалять ?
			if(dwdCurrTime<m_dwdLifeTimeOut)return;

			//время, меньше которого удалять
			Ttime dwdTimeToDelFrom_including=dwdCurrTime-m_dwdLifeTimeOut;

			it=m_TimeIdMmap.find(dwdTimeToDelFrom_including);
			if(it==m_TimeIdMmap.end())return;
			it++;

			//собственно, чистим
			td_TimeIdMap::iterator itdel=m_TimeIdMmap.begin();
			for(;;)
			{
				if(itdel==it)break;
				m_IdDataMap.erase(itdel->second);
				m_IdTimeMap.erase(itdel->second);
				itdel++;
			}

			m_TimeIdMmap.erase(m_TimeIdMap.begin(),it);
		}

		void SetData(const Tid Id,Tdata* pData,void* pSomeThis,tdf_SetNewData GetNewDataCallBack)
		{
			//засовывание в БД
			GetNewDataCallBack(pSomeThis,Id,pData);
		}

		void GetData(const Tid IdToFind,Tdata* pData,void* pSomeThis,tdf_GetNewData GetNewDataCallBack)
		{
			if(!pData)return;

			CSingleLock(&m_cris,1);

			//-------------------------------------------------
			//находим новое время - оно понадобится в любом случае
			Ttime dwdNewTime=::GetTickCount();

			//нужно проконтролировать на переполнение и на повтор
			{
				//смотрим время самой свежей записи
				td_TimeIdMap::iterator it=m_TimeIdMmap.end();
				it--;
				Ttime dwdLastTime=it->first;

				//переполнение?
				if(dwdNewTime<dwdLastTime)
				{
					m_IdDataMap.clear();

					m_TimeIdMmap.clear();
					m_IdTimeMap.clear();
				}
			}

			//-------------------------------------------------
			//dwdNewTime - время для новой записи

			//ищем id в кеше
			td_IdDataMap::iterator it=m_IdDataMap.find(IdToFind);
			if(it!=m_IdDataMap.end())
			{
				//нашли
				*pData=it->second;

				//обновляем время
				m_TimeIdMmap.erase(m_IdTimeMap[IdToFind]);
				m_IdTimeMap.erase(IdToFind);
			}
			else
			{
				//освобождаем место для новой записи
				Tid IdToDel;
				for(;m_IdDataMap.size()>=m_dwdMaxCount;)
				{
					//определяем самый "старый" id

					IdToDel=m_TimeIdMmap.begin()->second;

					//и удаляем
					m_TimeIdMmap.erase(m_TimeIdMmap.begin());

					m_IdTimeMap.erase(IdToDel);
					m_IdDataMap.erase(IdToDel);
				}

				//добавляем запись c IdToFind в мапы из базы
				Tdata data;

				//подгрузка из базы данных[IdToFind]
				if(!GetNewDataCallBack) return;
				if(!GetNewDataCallBack(pSomeThis,IdToFind,&data))return;

				//получена новая запись
				*pData=data;
				//вставляем текст
				m_IdDataMap[IdToFind]=data;
			}
		
			//обновляем время
			//m_TimeIdMmap[dwdNewTime]=IdToFind;  --->
			m_TimeIdMmap.insert(std::pair<td_TimeIdMmap::key_type,td_TimeIdMmap::mapped_type>(dwdNewTime,IdToFind));
		}
	};

Добавлено через 5 часов, 15 минут и 57 секунд:
стал компилировать и ага ))) Ну нет у multimap оператора [ ]

исправил

Код:

//	m_TimeIdMmap[dwdNewTime]=IdToFind;  --->
	m_TimeIdMmap.insert(std::pair<td_TimeIdMmap::key_type,td_TimeIdMmap::mapped_type>(dwdNewTime,IdToFind));

поленились дописать что ли? )

[RXL]

Леш, [] возвращает lvalue - ссылку, а какое может быть lvalue при множественных значениях на один ключ?

[Алексей++]

ну так то да, не подумал )

Добавлено через 15 часов, 50 минут и 47 секунд:

Код:

//смотрим время самой свежей записи
td_TimeIdMap::iterator it=m_TimeIdMap.end();
it--;

а вот и фиг - ломается )
Как последний элемент в мапе посмотреть ?

Добавлено через 22 минуты и 12 секунд:
воть

Код:

td_TimeIdMmap::reverse_iterator rit=m_TimeIdMmap.rbegin();
if(rit!=m_TimeIdMmap.rend())
{
}

[RXL]

Леш, end() указывает "за" последним элементом. Если итератор реверсный или двунаправленный, то выполни it--.

[Алексей++]

Ром, я выполнил --, программа упала )) Правда, это был дебаг, может, в релизе ассерт не покажется. Но неприятно

[RXL]

А итератор у тебя правильный был - не forward?

[Алексей++]

Код:

//смотрим время самой свежей записи
td_TimeIdMap::iterator it=m_TimeIdMap.end();
it--;

а вот и фиг - ломается )
Как последний элемент в мапе посмотреть ?

вот так было

Добавлено через 46 дней, 19 часов, 41 минуту и 2 секунды:
сунулся было попробовать заменить MFC-ный CString на std::string...   А не могу найти у него аналог CString::Format()

есть такой ? Должен же быть

[RXL]

Штатного нет, т.к. это, #####, C++-стиль.
Зато поиском можно найти заменители - оболочки для связывания сишного *prinf() с std::string.
http://www.senzee5.com/2006/05/c-formatting-stdstring.html

[Алексей++]

хорошо, посмотрю. А вообще, std::string меня жутько разочаровал ) Даже тем, что занимает при пустой строке аж 32 байта в дебаге и 28 в релизе. CString - 4 байта

Добавлено через 17 минут и 13 секунд:
вот это

Код:

#include <stdio.h>
#include <stdarg.h>
#include <string>
std::string format_arg_list(DWORD dwdResLenToTryFirst,const char *fmt, va_list args)
{
	if(!fmt)return"";
	int result=-1;
	int length=dwdResLenToTryFirst;
	char *buffer=0;
	while(result==-1)
	{
		if(buffer)delete[]buffer;
		buffer=new char[length+1];
		::memset(buffer,0,length+1);
		result=_vsnprintf(buffer,length,fmt,args);
		length *= 2;
	}
	std::string s(buffer);
	delete[]buffer;
	return s;
}

std::string format(const char *fmt, ...)
{
	va_list args;
	va_start(args, fmt);
	std::string s=format_arg_list(256,fmt,args);
	va_end(args);
	return s;
}

std::string formatLen(DWORD dwdResLenToTryFirst,const char *fmt, ...)
{
	va_list args;
	va_start(args, fmt);
	std::string s=format_arg_list(dwdResLenToTryFirst,fmt,args);
	va_end(args);
	return s;
}

я добавил ещё функцию - чторы можно было задать примерную начальную длину результата

[Антон (LogRus)]

хорошо, посмотрю. А вообще, std::string меня жутько разочаровал ) Даже тем, что занимает при пустой строке аж 32 байта в дебаге и 28 в релизе. CString - 4 байта

да но за это ты получаешь бонус в виде скорости при работе с короткими строками сравни скорость конкатенации 2-х слов из 5 символов

[Алексей++]

LogRus, выигрыш в скорости при работе с короткими строками - это да, это круто А почему только с короткими, почему для длинных строк скорость лучше не сделали ?

Тесты не делал

Я вообще-то взялся за замену CString на string только для совместимости кода с другим проектом, не на MFC.

[Антон (LogRus)]

потому, что внутри std::string есть char[16] для хранения коротких строк, который часто создаётся на стеке, как и сам стринг
а CString такой штуки нет и он вынужден для хранения даже одного символа вызывать new char[n]

[Алексей++]

потому, что внутри std::string есть char[16] для хранения коротких строк, который часто создаётся на стеке,

а, ну, я видел в дебаге , что в дампе тела класса короткая строка появилась - думал глюки ) Понятно теперь. Но такие короткие строки редко требуются в большом количестве, обычно, если много строк, то они и длинные. А собирать в один CString много мелких удобно и быстро как раз через Format

Добавлено через 7 дней, 59 минут и 15 секунд:
код форматирования string стал быть у меня в таком виде )

Код:

//#include <stdio.h>
//#include <stdarg.h>
#include <string>

	void st_FormatStringArgList(std::string& s,DWORD dwdResLenToTryFirst,const char *fmt, va_list args)
	{
		if(s.size()!=0)
		{
			s="";
		}

		if(!fmt)
		{
			return;
		}
		
		DWORD length=max(dwdResLenToTryFirst,256);
		s.resize(length,0);

		for(int result=-1;result==-1 && length;length<<=1)
		{
			s.resize(length,0);
			if(s.size()!=length)
			{
				s="";
				break;
			}

			//result=_vsnprintf...
			result=_vsnprintf_s(
				&s[0],
				s.size()*sizeof(s[0]),
				s.size(),
				fmt,
				args
				);
		}
	}

	void st_FormatString(std::string& s,const char *fmt, ...)
	{
		va_list args;
		va_start(args, fmt);
		st_FormatStringArgList(s,16,fmt,args);
		va_end(args);
	}

	void st_FormatString(DWORD dwdResLenToTryFirst,std::string& s,const char *fmt, ...)
	{
		va_list args;
		va_start(args, fmt);
		st_FormatStringArgList(s,dwdResLenToTryFirst,fmt,args);
		va_end(args);
	}

[clearance]

Код:

va_list args)

без указателя может не прокатить

это максимум из того, что сработало

Код:

void TRACE(const char *f, va_list *p)
{
    va_list n;
    
    n = *p;
    
    vprintf(f, n);
}

на gcc

[Алексей++]

clearance,

Код:

typedef char *  va_list;

это и так указатель )


зы Ты, наверное, не в ту тему запостил ? Перенести ?

[clearance]

всё, это непонятка была
ошибся я

[Алексей++]

Вот такой вопрос: есть ли в STL уже готовый кольцевой буфер ? Или стек FIFO

[Вад]

FIFO - это адаптер std:queue (по умолчанию использует контейнер deque для хранения содержимого)
Кольцевого буфера нет.

[Алексей++]

Рационально ли его применять, если мне нужен буфер размером в килобайт (то есть аналог BYTE arr[1024] ), или же лучше будет посидеть свой класс написать ?
Как он внутри устроен ?

FIFO подойдёт, так как мой кольцевой буфер не должен "перехлёстываться"

Добавлено через 47 минут и 35 секунд:
а, то есть в качестве "ядра" можно и вектор применить ?

Код:

std::queue < BYTE, std::vector<BYTE> > m_buff;

так?

(а размер меняться у меня не будет)

И будет ли переаллокация производиться при вызовах push и pop, если я буду заранее учитывать, чтоб размер не превысил изначально заданного ?
И что будет, если попытаюсь "лишний" элемент затолкнуть ?

----------------
Так, шота я запутался )))

допустим, сконструировал переменную так

Код:

	std::queue < BYTE, std::vector<BYTE> > m_buff(std::vector<BYTE>(1024,0));

затем

Код:

	m_buff.push(2);
	m_buff.push(2);
	m_buff.push(2);

	//m_buff.size()==1027;

size() что должно вернуть - 1024 или количество элементов ?

И нельзя ещё, получается, вставить несколько элементов сразу (

Чувствую, халява не предвидится

[Вад]

Если ты хочешь писать не побайтово, то это уже и не вполне FIFO, а именно что буфер Вектор в качестве контейнера для queue, думаю, использовать не стоит (подозреваю, будут чудовищные переаллокации при удалении из начала, хотя и не проверял ). Скорее, тут можно list как альтернативу deque вставить, или свою реализацию контейнера - надо думать, гибкость решения именно в этом.

size возвращает число элементов. Их у тебя получается 1027: при конструировании скопировано 1024 из вектора (сделана копия во "внутренний" вектор), а потом ещё 3. Ты пытался размер ограничить?

[RXL]

Лучше не vector, а deque.

[Алексей++]

Вад, я уже понял ошибку - я сначала подумал, что так можно изначально (а вообще - и жёстко) задать максимальный размер стека. Потом дошло, что так поместил 1024 нуля

RXL, Вад,  list не буду, наверное. Сделаю свой класс на основе вектора. Представлю на скорый суд ))

[Антон (LogRus)]

ждём с нетерпением