Код

typedef  map<int,int> map_t; map_t  my_map; for(int i=0; i<50; i+=5)     my_map.insert(map_t::value_type(i, i)); // теперь получаем итератор map_t::iterator  iter = my_map.find(25); // добавляем еще 10 элементов в список for(int i=2; i<52; i+=5)     my_map.insert(map_t::value_type(i, i));

Вопрос: останется ли итератор "iter" валидным ?
Т.е. можно ли будет обращаться к нему по "*iter" ?
Тот же самый вопрос по контейнерам "set", "multimap", "list".
Тот-же вопросик -- для случая если удалить элемент из контейнера ?

Цитата

Вопрос: останется ли итератор "iter" валидным ?

В общем случае - нет. Мне неизвестно, оговаривает ли стнадарт способ хранения эл-ов в виде связанного списка, но даже если элементы храняться именно так, то такой код потенциальный источник ошибок. Не только потому, что во втором цикле необходимо проверить все возвращаемые пары оператором my_map.insert(map_t::value_type(i, i)); на предмет того, выполнена ли вставка в контейнер нового элемента, но и потому что ассоциативные контейнеры в будущем захочется заменить хешированными и все через полгода окажется что программа не всегда работает верно.
Кроме того, даже если хранение реализовано в виде связанного списка, то нестандартный аллокатор мог как-то хитро перерасперделить память и использование такого итератора опять же будет рискованно (наверно по этой причине стандарт все же не регламентирует такой способ хранения).

Цитата

Тот же самый вопрос по контейнерам "set", "multimap", "list".

C set ситуация полностью анналогична. C multimap однозначно нельзя, ведь когда в контейнер добавиться копия нового элемента, то возможно старый итератор не сможет корректно выполнить операции перехода, да и сам элемент может "переместиться".
С list можно, но осторожно

DENNN, получается я не смогу использовать систему глобальных идентификаторов, при которой ID'ом является итератор, а строковым эквивалентом - значение разыменования "*" итератора ?

Код

// AfxId.h typedef map<string_t,bool> mapAFXID_t; typedef mapAFXID_t::value_type mapAFXID_vt; typedef mapAFXID_t::iterator mapAFXID_i; typedef mapAFXID_i AFX_ID; bool IdLookup(string_t strID, AFX_ID &id); AFX_ID IdRegister(string_t strID); void IdUnregister(string_t strID); io_t &operator>>(io_t &archive, AFX_ID id); io_t &operator<<(io_t &archive, AFX_ID id); // ....... // AfxId.cpp io_t &operator>>(io_t &archive, AFX_ID id) {     archive<<(*id).first;     return archive; } io_t &operator<<(io_t &archive, AFX_ID id) {     string_t str;     archive>>str;     IdRegister(str);     return archive; } bool IdLookup(string_t strID, AFX_ID &id) {     CModuleGlobal &mod = AfxGetModuleGlobal();     id = mod.m_mapAFXID.find(strID);     return id != mod.m_mapAFXID.end(); } AFX_ID IdRegister(string_t strID) {     return (AfxGetModuleGlobal().m_mapAFXID.insert(mapAFXID_vt(strID, true))).first; } void IdUnregister(string_t strID) {     AfxGetModuleGlobal().m_mapAFXID.erase(strID); }

Какой из контейнеров STL (или какая реализация STL) поддерживает алгоритм хеширования, или это

Цитата

ассоциативные контейнеры в будущем захочется заменить хешированными

просто пример ?

И, последнее, в доке по стандарту STL говорится что вставка и удаление элемента в ассоциативные контейнеры не приводит к изменению валидности существующих итераторов -- относится ли это только к HP-версии STL ?

Цитата

Какой из контейнеров STL (или какая реализация STL) поддерживает алгоритм хеширования

Официально, хешированные контейнеры не входят в стандарт STL, но поставляются со многими реализациями.

Цитата

просто пример ?

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

Цитата

в доке по стандарту STL говорится что вставка и удаление элемента в ассоциативные контейнеры не приводит к изменению валидности существующих итераторов -- относится ли это только к HP-версии STL ?

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

Цитата

получается я не смогу использовать систему глобальных идентификаторов, при которой ID'ом является итератор, а строковым эквивалентом - значение разыменования "*" итератора ?

Немного странный способ сопоставления ID его данным. Скажи какие задачи ты пытаешься реализовать таким образом и я попробую написать свой код.

P.S. AFX- не очень хороший идентификатор, так как легко перепутать с MFC-ми макросами.

DENNN, нужно создать систему (чем-то схожую с виндошными ATOM'ами) глобальных (в рамках одного процесса) идентификаторов (далее - ID'ов). Требования к системе:

• Все ID хранятся в контейнере (map или set), внутри определенного глобального объекта (CModuleGlobal);
  
• ID представляет собой произвольное значение или объект, для которого существует достаточно быстрый оператор "==", и на хранение которого затрачивается минимум памяти;
  
• Каждый ID "регистрируется" в функции или методе, использующем этот ID. Для регистрации используется произвольная строка, определяющая уникальность ID'а;
  
• При попытке регистрации ID со строкой, уже записанной в глобальный контейнер, возвращается значение уже зарегистрированного ID'а (так обеспечивается взаимодействие нескольких функций или методов, "знающих" строковый эквивалент ID'а)
  

Цель данной системы - предоставить возможность сопоставить любому объекту уникальный идентификатор, сохраняемый и загружаемый в/из файла (потока), с возможностью динамической регистрации и поиска ID по строке. Это даст возможность, например, хранить объекты в ассоциативном списке, с ключом-ID'ом (а не строкой), с возможностью быстро получить строку по значению ID; также можно будет свободно проектировать открытую систему с динамически подключаемыми модулями, не зная, например, значение кода сообщения, передаваемого в главный модуль из подключаемого, но зная строковый эквивалент (и это не будет тормозить всю программу, т.к. ID регистрируется только один раз, и далее используется очень быстрая операция сравнения).

Эта система должна работать с максимальной скоростью, конкретные типы данных (строка, ID и контейнер) могут быть произвольными.

До этого я попытался реализовать то же самое с помощью контейнера CMapStringToPtr, и специально написанного класса _AFX_ID (хранящего строку ID'a). Собственно ID'ом был указатель на _AFX_ID, а сами объекты _AFX_ID хранились в вышеуказанном контейнере.

Итераторы выбрал т.к. в HP-версии STL они занимают минимум места (инкапсулируют указатель и ничего более), обеспечивают очень быструю операцию разименования (и получения строки ID'а) и сравнения (сравнивается указатель с указателем). А то, что используется "AFX" в именах типов -- это не более чем старая привычка унаследованная от MFC (там все глобальные переменные и функции начинаются с такого префикса).

Это сообщение отредактировал(а) mr.DUDA - 19.8.2003, 12:02

В обчем, можно было бы делать IDы не итераторами, только будет тормознутее.

Цитата

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

Цитата

предоставить возможность сопоставить любому объекту уникальный идентификатор

Все же какова ситуация: ID сопоставляется строка или идентификатор некоторого объекта может быть представлен как ID так и строкой? Мне все же кажется, что видя вся картину в целом, можно выбрать более простой путь.

Цитата

конкретные типы данных (строка, ID и контейнер) могут быть произвольными.

ну задай их в своем шаблоне.
Если ты хочешь сделать супер-пупер универсальную систему, хранящую любые вообще объекты одновременно, то придеться хранить указатели на них в глобальной памяти, если просто экземпляр такого класса хранит однотипные указатели, то введи этот параметр в шаблон.
Еще я не понял, зачем хранить в контейнере bool?

Код

typedef map<string_t,bool> mapAFXID_t;

Если для последнего варианта, то шаблон такого класса-хранилища будет выглядеть примерно так:

Код

template <class T_ID, class T_str_ID, class T_obj> class SuperPuper{ //T_ID - тип идентификатора (раз уж ты хочешь иметь его настраиваемым), T_str_ID-объект для хранения строки, T_obj-собственно сами хранимые обекты public: typedef map<T_ID, T_str_ID> ID_TO_STR;//наш внутренний контейнер, чтоб хранить соответствие ID текстовой строке typedef map<t_str_ID, T_obj> SUPERCONT; //сами объекты и ассоциированные с ними текстовые идентификаторы private: ID_TO_STR  idtostr; SUPERCONT cont; //экземпляры наших внутренних объектов public: SuperPuper(){}; ~SuperPuper(){}; bool Add(T_ID id, T_str_ID str, T_obj obj) //добавление нового объекта в контейнер, если успешно, возвращаем true, иначе false {if ( idtostr.insert(ID_TO_STR::value_type(id,str)).second )               return ( cont.insert(SUPERCONT::value_type(str,obj))  ).second;   else return false; } bool Del(T_str_ID str)  //удаление элемента по его текстовому идентификатору { bool ret=cont.erase(str)!=0; if (ret) {    ID_TO_STR::iterator it=idtostr.begin();    while (idtostr.end()!=it) //помним, что по логике задачи тестовая строка уникальна!     if (it->second == str) {idtostr.erase(it);break;} else it++;  } return ret; } bool Del(T_ID id) //удаление элемента по его идентификатору ID (звучит как тафтология :) ) { if (idtostr.find(id)!=idtostr.end()) if Del( idtostr.find(id)->second ) {idtostr.erase(id);retrun true;}; return false; } T_obj* GetElement (T_str_ID str) //возвращает указатель на запрошенный элемент (или NULL), возможно в твоем алгоритме можно вернуть копию объекта, но так надежней;) { SUPERCONT::iterator it=cont.find(str); if  (cont.end()==it) return NULL; return it->second; } T_obj* GetElement (T_ID id) //то же для ID { if (cont.end()==idtostr.find(id)) return NULL; else return  GetElement(idtostr.find(id)); } }//описание класса законченно

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

Код

( idtostr.insert(ID_TO_STR::value_type(id,str)).second )               return ( cont.insert(SUPERCONT::value_type(str,obj))  ).second;   else return false;

лучше усложнить, чтоб обработать ситуацию, когда в первый контейнер пара добавлена, а во второй нет.

Самое главное: для твоих объектов T_ID и T_str_ID должна быть верно определена операция "<", конечно можно добавить в шаблон параметр по умолчанию для использования предикатов, но дело не в этом, а в том, что два идентификатора - это гемор.
Еще большая проблема с тем, что различные текстовые контейнеры, обозначенные у меня как T_str_ID могут по разному сравнивать прописные и строчные буквы.
Вообще в целом, задание не формализовано, поэтому и весь код смотрится как бред.

Это сообщение отредактировал(а) DENNN - 19.8.2003, 14:23

Обрати внимание на использование while в строках

Код

while (idtostr.end()!=it) //помним, что по логике задачи тестовая строка уникальна!    if (it->second == str) {idtostr.erase(it);break;} else it++;

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

Ok, расскажу поподробней (выше я привел требования только к самой системе идентификаторов, что действительно м.б. недостаточным для понимания, что же нужно сделать).

Суть задачи сводится к тому, чтобы получить возможность сопоставить чему-либо (не обязательно объекту, и не обязательно объекту в контейнере ) строковый идентификатор. Цель сего -- получить возможность открытости создаваемой программы в плане того, что заранее будут известны строковые идентификаторы объектов, функций и т.п., а не числовые.

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

Идентификаторы (далее - ID) будут очень часто подвергаться сравнению (с другими идентификаторами). Строки сравниваются медленно и занимают слишком много места. Значит, нужно найти решение, при котором строка-идентификатор будет ОДИН раз связана с простым типом данных (например, DWORD) -- т.н. "регистрация ID'а", и все последующие операции по хранению, сравнению и передаче ID будут проводиться не над строкой, а над ее "быстрым" эквивалентом. Обязательное условие -- обеспечить возможность получения строки по значению ID.

Храниться пары "ID<=>строка" должны в глобальном объекте, "представляющем" глобальную область видимости текущего модуля (во завернул).
Коротко насчет модулей. Главный модуль -- это EXE. Остальные модули -- подключаемые DLL (плагины). У каждого модуля есть свой объект CModuleGlobal; но при подключении DLL, последняя "передаёт" все свои зарегистрированные ID'ы главному модулю (чтобы обеспечить единственность контейнера ID'ов); свой контейнер игнорируется и все вызовы IdRegister, IdLookup и т.п. перенаправляются в главный модуль (в примере это не показано, чтобы не запутать и без того запутанный код )

ЗЫ, это всё должно входить в ядро MathCAD-подобного приложения с открытой архитектурой.

COM не подходит?

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

Я поначалу думал делать плагины объектами COM, но вот в чем вся фишка: пока начнешь собственно писать плагин, все зубы сломаешь об интерфейсы, маршаллинг и прочие прокси-стабы , неизвестно что будет больше глючить -- код, посвященный COM, или полезный код.

Цитата

COM не подходит

Не понял, как COM связан с этой задачей?

А почему не сделать бы map<string,pointer>? Вот тебе указатель будет и ID который быстро сравнивать, и при разименовании получаешь значение. Для красоты его можно завернуть в соответсвующую структуру.

Цитата

Обязательное условие -- обеспечить возможность получения строки по значению ID.

Для этого существует два способа:

1. pointer сделать структурой типа:

struct IDPointer
{
pointer ptr;
string name;
pointer operator pointer() {return ptr;};
operator->() {return ptr;};
}

То есть хранить сразу с указателем и его имя.

2. Взять класс типа bimap. Один из вариантов которых лежит на codeproject

Первый вариант (со структурой) не очень катит тем, что строку хранить придется 2 раза - в ключе map'а и внутри структуры.
Если ничего не получится придумать, придется юзать bimap.

Цитата

Первый вариант (со структурой) не очень катит тем, что строку хранить придется 2 раза - в ключе map'а и внутри структуры.

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

Всё. Итераторы в качестве ID юзать не получится, т.к. их (итераторы) нельзя (в свою очередь) хранить в контейнере. Так что придется делать по старой схеме (что-то наподобие того, что предлагает Fantasist):

Код

// ... специальный класс class _AFX_ID { public:     string_t   m_string; }; typedef  _AFX_ID*  AFX_ID;   // это у нас будет типом ID'ов inline  string_t  &IdGetString(AFX_ID id) {return id->m_string;} // ... и контейнер map<string_t, AFX_ID> mapIDs;

Храним в словаре пару "строка<=>указатель на структуру _AFX_ID", получаем ID по строке через "mapIDs.find", получаем строку по ID через IdGetString(id).

ИМХО, через итераторы изящнее получалось

Это сообщение отредактировал(а) mr.DUDA - 19.8.2003, 22:04