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

[zerone]

Не знает ли  кто-нибудь, толковой документации по STL, где было бы чётко написано какие методы должен содержать класс, который мы используем для шаблона.

Например, у нас есть структура, я хочу запихнуть её в список.

Код:

enum Gender {male, female};
struct Member {string name, Gender gender, int age};

list <Member> members;

При компиляции происходят ошибки. Как я понял, потому что в Member должны наличествовать некоторые операторы, в частности *, <, ==...

Вот и хочется узнать, что нужно конкретно для каждого из контейнеров STL.

[Антон (LogRus)]

Лог с ошибками в студию.
Я вообще обычно пользуюсь ресурсом www.cplusplus.com
Есть еще книга "STL"

Вообще я не помню каких-то специфичных требований к данным хранящимся в контейнере list

[Алексей++]

ошибка тут

struct Member {string name, Gender gender, int age};

STL вообще ни при чём

struct Member
{
  string name;
  Gender gender;
  int age;
};

[zerone]

Согласен. Но это я только так на форуме набрал.
К сожалению в программе структура объявлена правильно и дело не в этом.

[zerone]

Вот ругань компилятора:

Код:

MatchMaker.cpp: In member function ‘void MatchMaker::getBestMatches(std::vector<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::allocator<std::basic_string<char, std::char_traits<char>, std::allocator<char> > > >, std::string, int)’:
MatchMaker.cpp:16: ошибка: template argument for ‘template<class _Alloc> class std::allocator’ uses local type ‘MatchMaker::getBestMatches(std::vector<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::allocator<std::basic_string<char, std::char_traits<char>, std::allocator<char> > > >, std::string, int)::Member’
MatchMaker.cpp:16: ошибка:   при конкретизации ‘template<class _Alloc> class std::allocator’
MatchMaker.cpp:16: ошибка: некорректный аргумент шаблона 2
MatchMaker.cpp:16: ошибка: invalid type in declaration before ‘;’ token

[Антон (LogRus)]

uses local type

Похоже кто-то пытается в шаблон засунуть класс/структуру объявленную внутри функции/метода. Кто бы это мог быть?

[Алексей++]

если использую  std::map , я так понимаю, что контейнер индексирует ключ, а , следовательно, в любое время .find(ключ) очень быстро найдёт запись ? Или сначала надо сортировать ?

[RXL]

Леш, карты не могут быть переупорядочены.
Да, find() имеет логарифмическую сложность поиска.

[Алексей++]

>>>карты не могут быть переупорядочены.

ага, уже понял ) Да и метода sort нет

>>>Да, find() имеет логарифмическую сложность поиска.

а что это значит ? Всё таки быстро то есть ?

[Вад]

Алексей1153++, если коротко - то да, быстро Там же внутреннее представление - дерево (по-моему, красно-чёрное обычно). Поэтому спуск по дереву до нужного элемента при размере карты в N элементов происходит за время порядка log_2(N).

С отсортированным массивом и бинарным поиском можно получить такую же скорость, если не учитывать затраты на собственно сортировку.

[Алексей++]

имеется

Код:

std::map<int,int> M;
std::map<int,int>::iterator it;

с содержимым, скажем

Код:

1,1 (M.begin())
2,4
5,3
7,3
9,1 (M.end()--)

мысленно пронумеруем номерами по порядку

Код:

#0  1,1 (M.begin())
#1  2,4
#2  5,3
#3  7,3
#4  9,1 (M.end()--)

как этот порядковый номер определить ? Пытался так (скажем, для ключа 5)

Код:

DWORD dwdNPP=-1;
it=M.find(5);
if(it!=M.end())
{
  dwdNPP=it-M.begin();
}

но тут одно но: оператор "-" не определён для итератора. Что тут можно сделать ?




а будет ли правильным:

Код:

  dwdNPP=it._Ptr-M.begin()._Ptr;

?

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

Код:

dwdNPP=(M.begin()._Ptr-it._Ptr)/2;

-----------------------------

нет, фигня это - работает через раз, а в релизе ._Ptr вообще недоступен )

[Вад]

По-моему, номер в мапе за константное время определить не удастся. А за линейное - с помощью функции distance.

Код:

#include <iterator>
// ...

it=M.find(5);
if(it!=M.end())
{
  dwdNPP=static_cast<DWORD>( std::distance(M.begin(), it)) );
}

[Алексей++]

понятно, спасибо

Добавлено через 82 дня, 11 часов, 1 минуту и 48 секунд:
Имеется

std::map<LONG/*id*/,CString/*описание*/> ,

 где строка может быть достаточно длинной. Чтобы не хранить всё в озу, хочется превратить мап в кеш , то есть если в мапе нет нужного id , то он вместе с описанием подгружается из БД и кладётся в мап.
Вопрос: как содержимое map сдвигать а-ля FIFO, чтобы количество элементов не превысило некоего N ?

[RXL]

Леш, сделай класс, хранящий данные в map. Я так же делал.

Храни id в отдельной структуре - очереди. При превышении размера очереди выталкивай первый id и удаляй соответствующий ему элемент из map.

Только коли это кеш, то надо какой-то алгоритм для сортировки очереди иметь. Например, при обращении к элементу его id следует удалить из очереди и добавить в ее конец.

[Алексей++]

Нет, ну просто написать класс-очередь, это не сложно (но долго), хочется ничего не меняя, использовать уже имеющийся мап.

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

Код:

struct X
{
   CString d;/*описание*/
   DWORD ticks;
};

std::map<LONG/*id*/, X> myMap;

а как индексировать по ticks теперь ?

мысль: пусть будет дополнительный мап. Надо обдумать )

Код:

std::map<LONG/*id*/,CString/*описание*/> myMap;
std::map<DWORD /*тики*/, id> tickIndex;

Добавлено через 15 минут и 26 секунд:
правда, с тиками тут не совсем красиво, если программа будет работать 2 месяца, то первыми из мапа стунут замещаться самые новые записи (когда DWORD переполнится). Применю SYSTEMTIME

[Dimka]

Алексей1153++, при обращении к ID, перемещай его в начало (как свежий), тогда в конце очереди естественным образом окажутся самые неиспользуемые ID - их и удалить.

[Алексей++]

Алексей1153++, при обращении к ID, перемещай его в начало (как свежий), тогда в конце очереди естественным образом окажутся самые неиспользуемые ID - их и удалить.

То есть, уже без map ? Или я тогда не понял. Я сейчас делаю реализацию с двумя мапами, как в предыдущем посте - пока нет разногласий с целью )

Добавлено через 2 часа, 34 минуты и 21 секунду:
вот примерно такое безобразие выходит (не тестировал ещё - засыпаю... )

Код:

class CIdTextKeeper
{
	enum{e_max_count=10000};

	//               id  строка
	typedef std::map<int,CString> td_IdTextMap;

	//               время  id
	typedef std::map<DWORD,int>   td_TimeIdMap;

	//               id  время
	typedef std::map<int,DWORD>   td_IdTimeMap;

	CCriticalSection m_cris;
	td_IdTextMap m_IdTextMap;
	td_TimeIdMap m_TimeIdMap;
	td_IdTimeMap m_IdTimeMap;


public:
	void SetTexts(const int Id,CString Text)
	{
		//засовывание в БД
		//...
	}

	void GetTexts(const int IdToFind,CString* pText)
	{
		if(!pText)return;

		CSingleLock(&m_cris,1);

		//находим новое время
		DWORD dwdNewTime=0;
		if(m_TimeIdMap.size())
		{
			td_TimeIdMap::iterator it=m_TimeIdMap.end();
			it--;
			dwdNewTime=it->first+1;

			//боремся с переполнением таймера
			if(!dwdNewTime)
			{
				m_IdTextMap.clear();

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

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

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

				IdToDel=m_TimeIdMap.begin()->second;

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

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

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

			//text << БазаДанных[IdToFind]

			//новая запись
			*pText=text;
			//вставляем текст
			m_IdTextMap[IdToFind]=text;
		}
	
		//обновляем время
		m_TimeIdMap[dwdNewTime]=IdToFind;
		m_IdTimeMap[IdToFind]=dwdNewTime;
	}
};

[Антон (LogRus)]

как я делал нечто подобное.
1. один std::map<unsigned long, >

Код:

struct Element
{
   std::string decription_;
   DWORD lastUpdate_; // время последнего обращения
}

std::map<unsigned long, Element> cont;

2. размер не ограничено, НО //далее специфика моей задачи
2.1. есть timeout хранения
2.2. известно, что при разумном timeout, колличество элементов в очереди будет не слишком велико.
3. зачистка старых элементов выполняется в отдельном потоке. Цель: уменьшить всплески нагрузки посредине обработки запроса, т.е. что бы не возникало ситуации, когда вдруг время обработки запроса резко возрастало по отношению к среднему из-за зачистки кэша. НО // далее специфика моей задачи
раз в несколько минут был краткий технологический период приостановки обработки запросов (это старый артефакт я тут не причем, просто он мне был удобен в моей задаче), в этот момент и происходила зачистка буфера иначе получаем, то от чего убегали.
4. с переполнением таймера я боролся вот так

Код:

if (currentTime - elem.lastUpdate_ > TTL ) // тут ОДНО переполнение учитывается автоматически

твое решение тоже ничего
я тут вижу такую проблему:
1. существует некий поток запрос, какие-то частые какие-то не очень
2. в конце очереди скопились те, что не слишком частые
3. в потоке запросов какой-то процент запросов, практически уникальных, т.е. ОЧЕНЬ редких, но их достаточно много
4. в итоге в конце очереди наблюдается некоторый дребезг, т.е. не слишком частые запросы часто и много вытесняются уникальными (очень редкими) и тут же возвращаются назад (получаем 2 обращения в БД), т.е. не смотря на то, что были закэшированы частые запросы, мы имеет очень много обращений к БД.
в цифрах: 10% запросов уникально, 30% очень редкие (уникальных id среди них в соотношении 1/10), 30% редкие(уникальных id среди них в соотношении 1/30), 30% частые (уникальных id среди них в соотношении 1/100)
и из-за 10% уникальных запросов, может получится, что каждое пускай 5-е обращение пойдёт в обход кэша

тут нужно иметь или достаточно большой размер очереди для нивирования проблемы или дополнительный механизм контроля, например, TTL
нужно, только немного модифицировать вот это:

Код:

			//освобождаем место для новой записи
			int IdToDel;
			for(;m_IdTextMap.size()>=e_max_count;)
			{
				//определяем самый "старый" id

				IdToDel=m_TimeIdMap.begin()->second;

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

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

[lapulya]

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

[Алексей++]

LogRus, то есть, у меня не хватает, грубо говоря, периодического удаления "очень старых" записей (по некоему критерию). Например, раз в 5 минут можно очищать 2/3 части мапа старой, захватывая старую часть ?

Насчёт специфики моей задачи: показывается лог сообщений, у каждого сообщения приписана та длинная строка. Обычно на экране около 100 последних сообщений, если только кто-то не возьмётся прокручитвать список.

[Антон (LogRus)]

1. неограниченный размер или достаточно большой размер
2. удаление по таймауту,а не 2/3 данных

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

параметры я бы сделал или настраиваемыми или вычисляемыми на лету.

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

иногда, требуется иметь не очищаемый кэш. Собственно у нас почти весь кэш БД такой (+ много логики по его актуализации при изменениях в БД)

[Алексей++]

LogRus, таймаут то где хранить ? Как индексировать для быстроты поиска ? Ещё одим мап ?

А , кстати, чем плохо просто обрезать старую часть? Ну, с 2/3 это я погорячился, ну , скажем взять первое и последнее время и пропорционально вычислить 30% и удалить это старое время. А при переполнении (оно, кстати, наступит не скоро - я же счётчик веду, а не тики достаю) можно просто очистить кеш полностью - притормаживание раз в 200 лет никто не заметит ))

[Антон (LogRus)]

такой пример:
1. запрос 1 прошла 1 секунда
2. запрос 2 прошло 2 секунда
3. запрос 3 прошло 3 секунда
при этом запрос 1 приходит раз в секунду
при этом запрос 2 приходит раз в 2 секунды
при этом запрос 3 приходит раз в 3 секунды
далее предположим, что обычно других запросов то и нет

ты удаляешь 2/3 контейнера и получаешь слишком частые обращения в БД по запросам 2 и 3

где хранить? ну вроде у тебя уже есть решение

имхо я бы сделал просто настройку, и если она будет не достаточной тогда двинусь дальше
можно конечно в софтину вложить вместо 100 часов 10000 часов, она будет вся из себя, НО кому это действительно надо? Бизнес требования? Не думаю. Поэтому я бы делал итерациями с постепенным улучшением функционала.

[Алексей++]

У меня же нет штампа времени, у меня счётчик.  Чем больше счётчик - тем моложе запись. Новое значение счётчика генерирую из последнего элемента m_TimeIdMap.
То есть можно задать "интервал старости" и придётся связать его с максимальным размером мапа - e_max_count , например

enum{e_old_distance=e_max_count*20/100};

тогда добавляем метод, который следует вызывать раз в N минут

Код:

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

			if(!m_TimeIdMap.size())return;

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

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

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

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

			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_IdTextMap.erase(itdel->second);
				m_IdTimeMap.erase(itdel->second);
				itdel++;
			}

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

[Антон (LogRus)]

может вместо счётчика GetTickCount?

[Алексей++]

LogRus, а смысл ? Я всё равно обеспечиваю увеличение счётчика, а о переполнении можно не заботиться

[Антон (LogRus)]

смысл в то, что счётчик это удалённость элемента относительно друг друга в пространстве, а не во времени.
некоторый всплеск активности по уникальным запросам может отодвинуть часто используемый запрос в конец очерди

[Алексей++]

не вижу разницы

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

4. в итоге в конце очереди наблюдается некоторый дребезг, т.е. не слишком частые запросы часто и много вытесняются уникальными (очень редкими) и тут же возвращаются назад (получаем 2 обращения в БД),

блин, никак не могу понять, откуда 2 чтения из базы: даже если парочка другая (даже десятков) редких записей дёрнется наверх, часто используемые вряд ли вытеснятся в конце. А, кроме того, они (часты) вскоре снова перейдут наверх.

[Антон (LogRus)]

2 чтения:
1. читаем уникальный идентификатор
2. читаем вытесненный

не вижу разницы

.....даже если парочка другая (даже десятков) редких записей дёрнется наверх ....

ну при таких потоках данных, в общем-то пополам
но допустим поток 1000 запросов в секунду или 10000
при этом часто повторяющихся (не реже раз в 5 минут) всего 10% от общего числа запросов
5 минут это 60*5*1000 = 300 000 запросов
получается, что в худшем случае между 2-мя обращения для одного и того же ключа в течении 5 минут может влезть сотня другая тысяч запросов которая вытеснит его из кэша
если же ты используеся время, а не счётчик, то запрос не вытеснится

[Алексей++]

ну с этим понятно. Можно и с тиками переделать - одну строчку исправить то

Но у меня нет 1000 запросов в секунду. Чаще - 0 запросов в час, и это не предел, но когда начинают листать лог (иногда нужно), то будет, ну, скажем, 100 строк в секунду перематываться. Потому то и жаль всё в озу хранить - оно так редко может понадобится, что просто неприлично озу забивать

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

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