Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > SWITCH

Автор: np9mi7 1.4.2005, 15:15

Добрый день Столкнулся с такой проблемой, хочеться реализовать паттерн switch.

Задача такова:
у меня есть некоторый набор объектов определенного типа. У каждого объекта есть свой уникалиный id, тоже определенного типа. Хочеться чтоб по предъявлению этого идентификатора мне возвращалась ссылка на объект который соотв. этому идентификатору. причем поиск должен осущ. за 1 шаг, те я по адресу в векторе должен стукануться.
Как это сделать? Совершенно не хочеться бегать по вектору в поисках нужного объекта. Вот примерный шаблон.

Код


template <class TYPE, class ID> class Switch
{
    std::vector<TYPE*> m_vcCollection;
//-----------------------------------------
    public:
        Switch    (const std::vector<TYPE*>&);
        Switch    ();
//-----------------------------------------        
        T&    GET    (const ID&);
};

Таким образом, получается касяк в обращении за один шаг к нужному объекту.

Автор: Fire-Plug 1.4.2005, 17:40

Здесь не паттерн нужен, a std::map<ID, Type>
ID - тип идентификатора твоего обьекта;
Type - это тип ссылки или указателя(выбор твой) на твой обьект.

Как получить обьект из map:

Код


typedef std::map<ID, Type> TMyObjMap;

TMyObjMap myObjMap; // как-то инициализирована

ID id= ....;
TMyObjMap::const_iterator it= myObjMap.find(id);
if( it == myObjMap.end())
{
 // not found 
  return; // or do something
}
Type& obj= it->second;

Автор: Fire-Plug 1.4.2005, 18:04

Цитата(np9mi7 @ 1.4.2005, 15:15)

причем поиск должен осущ. за 1 шаг, те я по адресу в векторе должен стукануться.

std::map как пишут в руководствах реализует алгоритм двоичного поиска (т.к. элементы map отсортированы по первому аргументу-ключу).
Поэтому число итераций поиска oпрeдeляется зависимостью:

log 2 (N), N - к-во элементов.

Поиск за один шаг осущ. так наз. совершенный хэш (perfect hash).
Но я этим не занимался. Мне достаточно STL.

Автор: np9mi7 1.4.2005, 19:15

Fire-Plug smile

perfect hash, а что это такое? Можешь дать ссылку?

Может у кого другие предложения??? smile

По сути, ты предложил поиск, а я тебе про поиск в один шаг.

Автор: Fire-Plug 1.4.2005, 20:31

Цитата(np9mi7 @ 1.4.2005, 19:15)

perfect hash, а что это такое? Можешь дать ссылку?

http://www.google.com/search?hl=en&q=perfect+hash&btnG=Google+Search

Цитата(np9mi7 @ 1.4.2005, 19:15)

По сути, ты предложил поиск, а я тебе про поиск в один шаг

Я предложил весьма практичное решение на основе STL, к-рое будет приемлемо в 95% прикладных задач.
Число итераций метода двоичного поиска:
Для контейнера из 10-ти элементов - 3
- " - из 100 элементов - 7 (2^7 = 128)
- " - из 1000 элементов - 10 (2^10 = 1024) и т.д.

Простейший (и тупейший) хэш - обычный массив.
Или можно с тем же успехом и по тому же принципу юзать vector.

Код


T* array[MAXOBJECTS]; // инициализирован 0

void SetObject(T* obj, size_t Id) // Id < MAXOBJECTS
{
    array[Id]= obj;
}

T* GetObject(size_t Id) // Id < MAXOBJECTS
{
    return array[Id];
}

Автор: np9mi7 1.4.2005, 21:13

Fire-Plug, ты как обычно пытаешся доказать что ты сто процентов прав! да ты прав! только, можно чуть лучше, согласись.... Гуглом я тоже пользоватьеся умею.... Только хотелось получить источник их которого ты это узнал, поэтому и спросил....

Понимаешь, мне нужен доступ за один шаг! Понимаешь? Поэтому и спросил, так сказать это в условии задачи обозначено...

За perfect hash спасибо, но про ln предлагаю больше не офтоппить.... ок?

Автор: bel_nikita 1.4.2005, 21:44

Цитата

Понимаешь, мне нужен доступ за один шаг! Понимаешь?

Цитата

У каждого объекта есть свой уникалиный id, тоже определенного типа.

что представляет из себя уникальный id?
Если Id - это обычный enum, то пихай все в array[MAX_ENUM];

Автор: yaja 1.4.2005, 21:48

Нужны ссылки??
http://algolist.manual.ru/ds/s_has.php

или можешь почитать в любой книжке по алгоритмам ))

Автор: Fire-Plug 1.4.2005, 21:57

Цитата(np9mi7 @ 1.4.2005, 15:15)

Хочеться чтоб по предъявлению этого идентификатора мне возвращалась ссылка на объект

Цитата(np9mi7 @ 1.4.2005, 21:13)

Понимаешь, мне нужен доступ за один шаг! Понимаешь?

Нет, не понимаю. Потому, что "Хочеться" вместо обоснования, почему никакие другие решения принципиально не подходят.
Если вопрос этот в плане учебы, повышения проф.уровня и т.д. и т.п., об этом прямо и честно надо заявить! Тогда будет смысл искать требуемое решение.
А если "Хочеться", то когда сроки прижмут фигней заниматься, то сразу перехочется.

Цитата(np9mi7 @ 1.4.2005, 21:13)

получить источник их которого ты это узнал

Источник - один крутой мэн, с к-рым у меня когда-то было интервью, в т.ч. по методам поиска. Он и рассказал, что есть такой perfect hash, но делать не заставлял - std::map катила...
Добавлено @ 21:59

Цитата(np9mi7 @ 1.4.2005, 21:13)

но про ln предлагаю больше не офтоппить

ln - ? Это что?

Автор: np9mi7 1.4.2005, 22:59

Цитата

что представляет из себя уникальный id?
Если Id - это обычный enum, то пихай все в array[MAX_ENUM];

, уникальный ID есть некое свойство для объекта, причем оно это свойство однозначно опр. этот объект. Типа как первичный ключ.

Ну да, при такой постановке задачи без поиска никак...

Цитата

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

, ну да...

Автор: chipset 2.4.2005, 01:35

Я никогда раньше не знал про perfect hash, но как я подумалл, можно добиться скорости в один шаг, только помещая в ключ указатель на адрес памяти где находится соответствующий этому ключу обьект.
Тогда не нужно будет поиска, программа просто читает по адресу.

Автор: Fire-Plug 2.4.2005, 10:16

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

Автор: chipset 2.4.2005, 10:27

Цитата(Fire @ 1.4.2005, 23:16)

Что значит примитивный ключ? Какое может быть множество допустимых значений у сложного класса?
Я и хочу то всего лишь сделать базовый класс hash_object с указателем на область void, который задействуется лишь когда он будет учтен в базе map и в этот указатель будет записан указатель на соответствующий обьект.
Будет один шаг, но требование все-таки придется ввести для паттерна.

Автор: np9mi7 3.4.2005, 12:03

Всем спасибо за советы, топик закрыт. Немного не правильная постановка задачи, мной недопонятая.

Автор: chipset 3.4.2005, 13:12

Всё догнал, моё предложение не будет работать в большинстве случаев потому что значение ключа не хранит в себе указатель.