zerone
Гость
|
|
« : 21-02-2009 08:46 » |
|
Не знает ли кто-нибудь, толковой документации по STL, где было бы чётко написано какие методы должен содержать класс, который мы используем для шаблона. Например, у нас есть структура, я хочу запихнуть её в список. enum Gender {male, female}; struct Member {string name, Gender gender, int age};
list <Member> members;
При компиляции происходят ошибки. Как я понял, потому что в Member должны наличествовать некоторые операторы, в частности *, <, ==... Вот и хочется узнать, что нужно конкретно для каждого из контейнеров STL.
|
|
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #1 : 21-02-2009 08:53 » |
|
Лог с ошибками в студию. Я вообще обычно пользуюсь ресурсом www.cplusplus.comЕсть еще книга "STL" Вообще я не помню каких-то специфичных требований к данным хранящимся в контейнере list
|
|
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #2 : 21-02-2009 09:19 » |
|
ошибка тут struct Member {string name, Gender gender, int age}; STL вообще ни при чём struct Member { string name; Gender gender; int age; };
|
|
|
Записан
|
|
|
|
zerone
Гость
|
|
« Ответ #3 : 21-02-2009 10:33 » |
|
Согласен. Но это я только так на форуме набрал. К сожалению в программе структура объявлена правильно и дело не в этом.
|
|
|
Записан
|
|
|
|
zerone
Гость
|
|
« Ответ #4 : 21-02-2009 10:36 » |
|
Вот ругань компилятора: 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)
|
|
« Ответ #5 : 21-02-2009 11:29 » |
|
uses local type Похоже кто-то пытается в шаблон засунуть класс/структуру объявленную внутри функции/метода. Кто бы это мог быть?
|
|
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #6 : 27-10-2009 05:00 » |
|
если использую std::map , я так понимаю, что контейнер индексирует ключ, а , следовательно, в любое время .find(ключ) очень быстро найдёт запись ? Или сначала надо сортировать ?
|
|
|
Записан
|
|
|
|
RXL
|
|
« Ответ #7 : 27-10-2009 06:54 » |
|
Леш, карты не могут быть переупорядочены. Да, find() имеет логарифмическую сложность поиска.
|
|
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #8 : 27-10-2009 07:25 » |
|
>>>карты не могут быть переупорядочены.
ага, уже понял ) Да и метода sort нет
>>>Да, find() имеет логарифмическую сложность поиска.
а что это значит ? Всё таки быстро то есть ?
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #9 : 27-10-2009 07:56 » |
|
Алексей1153++, если коротко - то да, быстро Там же внутреннее представление - дерево (по-моему, красно-чёрное обычно). Поэтому спуск по дереву до нужного элемента при размере карты в N элементов происходит за время порядка log_2(N). С отсортированным массивом и бинарным поиском можно получить такую же скорость, если не учитывать затраты на собственно сортировку.
|
|
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #10 : 28-10-2009 05:04 » |
|
имеется 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 вообще недоступен )
|
|
« Последнее редактирование: 28-10-2009 06:02 от Алексей1153 »
|
Записан
|
|
|
|
Вад
|
|
« Ответ #11 : 28-10-2009 06:07 » |
|
По-моему, номер в мапе за константное время определить не удастся. А за линейное - с помощью функции distance. #include <iterator> // ...
it=M.find(5); if(it!=M.end()) { dwdNPP=static_cast<DWORD>( std::distance(M.begin(), it)) ); }
|
|
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #12 : 28-10-2009 06:10 » |
|
понятно, спасибо
Добавлено через 82 дня, 11 часов, 1 минуту и 48 секунд: Имеется
std::map<LONG/*id*/,CString/*описание*/> ,
где строка может быть достаточно длинной. Чтобы не хранить всё в озу, хочется превратить мап в кеш , то есть если в мапе нет нужного id , то он вместе с описанием подгружается из БД и кладётся в мап. Вопрос: как содержимое map сдвигать а-ля FIFO, чтобы количество элементов не превысило некоего N ?
|
|
« Последнее редактирование: 18-01-2010 17:12 от Алексей1153 »
|
Записан
|
|
|
|
RXL
|
|
« Ответ #13 : 18-01-2010 17:07 » |
|
Леш, сделай класс, хранящий данные в map. Я так же делал.
Храни id в отдельной структуре - очереди. При превышении размера очереди выталкивай первый id и удаляй соответствующий ему элемент из map.
Только коли это кеш, то надо какой-то алгоритм для сортировки очереди иметь. Например, при обращении к элементу его id следует удалить из очереди и добавить в ее конец.
|
|
« Последнее редактирование: 18-01-2010 17:08 от RXL »
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #14 : 18-01-2010 17:17 » |
|
Нет, ну просто написать класс-очередь, это не сложно (но долго), хочется ничего не меняя, использовать уже имеющийся мап. К примеру, добавить к описанию время добавления и при подгрузке удалять записи с наименьшим временем. 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
|
|
« Последнее редактирование: 18-01-2010 17:33 от Алексей1153 »
|
Записан
|
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #15 : 18-01-2010 18:06 » |
|
Алексей1153++, при обращении к ID, перемещай его в начало (как свежий), тогда в конце очереди естественным образом окажутся самые неиспользуемые ID - их и удалить.
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #16 : 18-01-2010 18:28 » |
|
Алексей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; } };
|
|
« Последнее редактирование: 18-01-2010 21:03 от Алексей1153 »
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #17 : 19-01-2010 05:43 » |
|
как я делал нечто подобное. 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
Молодой специалист
Offline
|
|
« Ответ #18 : 19-01-2010 13:52 » |
|
LogRus, я бы даже развил тему, если часто запрашиваемые данные составляют очень малую часть от всех (так обычно и бывает )))) ), но при этом опрос уникальных данных производится по всей базе (а в кеше мы храним последние запрошенные), но начиная с какого-то размера кеша попасть в кеш при очередной выборке будет нереально (он будет забит последними уникальными данными)
|
|
|
Записан
|
С уважением Lapulya
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #19 : 19-01-2010 16:56 » |
|
LogRus, то есть, у меня не хватает, грубо говоря, периодического удаления "очень старых" записей (по некоему критерию). Например, раз в 5 минут можно очищать 2/3 части мапа старой, захватывая старую часть ?
Насчёт специфики моей задачи: показывается лог сообщений, у каждого сообщения приписана та длинная строка. Обычно на экране около 100 последних сообщений, если только кто-то не возьмётся прокручитвать список.
|
|
« Последнее редактирование: 19-01-2010 16:59 от Алексей1153++ »
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #20 : 20-01-2010 04:06 » |
|
1. неограниченный размер или достаточно большой размер 2. удаление по таймауту,а не 2/3 данных удаление по таймауту можно сделать по разному, можно налету, можно отложено (в отдельном потоке) почитай про что-нибудь на вроде MemCached. параметры я бы сделал или настраиваемыми или вычисляемыми на лету. LogRus, я бы даже развил тему, если часто запрашиваемые данные составляют очень малую часть от всех (так обычно и бывает )))) ), но при этом опрос уникальных данных производится по всей базе (а в кеше мы храним последние запрошенные), но начиная с какого-то размера кеша попасть в кеш при очередной выборке будет нереально (он будет забит последними уникальными данными)
иногда, требуется иметь не очищаемый кэш. Собственно у нас почти весь кэш БД такой (+ много логики по его актуализации при изменениях в БД)
|
|
« Последнее редактирование: 20-01-2010 04:09 от LogRus »
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #21 : 20-01-2010 04:13 » |
|
LogRus, таймаут то где хранить ? Как индексировать для быстроты поиска ? Ещё одим мап ? А , кстати, чем плохо просто обрезать старую часть? Ну, с 2/3 это я погорячился, ну , скажем взять первое и последнее время и пропорционально вычислить 30% и удалить это старое время. А при переполнении (оно, кстати, наступит не скоро - я же счётчик веду, а не тики достаю) можно просто очистить кеш полностью - притормаживание раз в 200 лет никто не заметит ))
|
|
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #22 : 20-01-2010 04:41 » |
|
такой пример: 1. запрос 1 прошла 1 секунда 2. запрос 2 прошло 2 секунда 3. запрос 3 прошло 3 секунда при этом запрос 1 приходит раз в секунду при этом запрос 2 приходит раз в 2 секунды при этом запрос 3 приходит раз в 3 секунды далее предположим, что обычно других запросов то и нет ты удаляешь 2/3 контейнера и получаешь слишком частые обращения в БД по запросам 2 и 3 где хранить? ну вроде у тебя уже есть решение имхо я бы сделал просто настройку, и если она будет не достаточной тогда двинусь дальше можно конечно в софтину вложить вместо 100 часов 10000 часов, она будет вся из себя, НО кому это действительно надо? Бизнес требования? Не думаю. Поэтому я бы делал итерациями с постепенным улучшением функционала.
|
|
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #23 : 20-01-2010 05:22 » |
|
У меня же нет штампа времени, у меня счётчик. Чем больше счётчик - тем моложе запись. Новое значение счётчика генерирую из последнего элемента 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); }
|
|
« Последнее редактирование: 20-01-2010 05:40 от Алексей1153++ »
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #24 : 20-01-2010 07:07 » |
|
может вместо счётчика GetTickCount?
|
|
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #25 : 20-01-2010 07:32 » |
|
LogRus, а смысл ? Я всё равно обеспечиваю увеличение счётчика, а о переполнении можно не заботиться
|
|
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #26 : 20-01-2010 07:42 » |
|
смысл в то, что счётчик это удалённость элемента относительно друг друга в пространстве, а не во времени. некоторый всплеск активности по уникальным запросам может отодвинуть часто используемый запрос в конец очерди
|
|
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #27 : 20-01-2010 07:43 » |
|
не вижу разницы Добавлено через 33 минуты и 41 секунду:4. в итоге в конце очереди наблюдается некоторый дребезг, т.е. не слишком частые запросы часто и много вытесняются уникальными (очень редкими) и тут же возвращаются назад (получаем 2 обращения в БД),
блин, никак не могу понять, откуда 2 чтения из базы: даже если парочка другая (даже десятков) редких записей дёрнется наверх, часто используемые вряд ли вытеснятся в конце. А, кроме того, они (часты) вскоре снова перейдут наверх.
|
|
« Последнее редактирование: 20-01-2010 08:17 от Алексей1153 »
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #28 : 20-01-2010 09:05 » |
|
2 чтения: 1. читаем уникальный идентификатор 2. читаем вытесненный не вижу разницы
.....даже если парочка другая (даже десятков) редких записей дёрнется наверх ....
ну при таких потоках данных, в общем-то пополам но допустим поток 1000 запросов в секунду или 10000 при этом часто повторяющихся (не реже раз в 5 минут) всего 10% от общего числа запросов 5 минут это 60*5*1000 = 300 000 запросов получается, что в худшем случае между 2-мя обращения для одного и того же ключа в течении 5 минут может влезть сотня другая тысяч запросов которая вытеснит его из кэша если же ты используеся время, а не счётчик, то запрос не вытеснится
|
|
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #29 : 20-01-2010 09:17 » |
|
ну с этим понятно. Можно и с тиками переделать - одну строчку исправить то Но у меня нет 1000 запросов в секунду. Чаще - 0 запросов в час, и это не предел, но когда начинают листать лог (иногда нужно), то будет, ну, скажем, 100 строк в секунду перематываться. Потому то и жаль всё в озу хранить - оно так редко может понадобится, что просто неприлично озу забивать Добавлено через 17 минут и 24 секунды:ага... А как быть с тем, что с GetTickCount индекс в m_TimeIdMap может слегка повториться ? Мысль - эсли это произошло, то брать значение "время самой новой записи+1" , переполнение же в двух местах теперь надо учитывать
|
|
« Последнее редактирование: 20-01-2010 09:35 от Алексей1153 »
|
Записан
|
|
|
|
|