VPF::ваши мысли по расширению функционала

boostcoder

Дата 11.2.2012, 17:39 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

всем привет!

имеется некоторый чужой код:

Код


template <int ID = 0>
class item
{
public:
   
   inline item () :
      array_index (-1)
   {}
   
   inline virtual ~item () {}
   
   inline void index (int index_) { array_index = index_; }
   
   inline int index () { return array_index; }
   
private:
   
   int array_index;
   
   item (const item&);
   const item &operator = (const item&);
};

template <typename T, int ID = 0>
class array {
private:
   
   typedef item <ID> item_t;
   
public:
   
   typedef typename std::vector <T*>::size_type size_type;
   
   inline array () {}
   inline ~array () {}
   
   inline size_type size () { return items.size (); }
   inline bool empty () { return items.empty (); }
   inline T *&operator [] (size_type index_) { return items [index_]; }
   
   inline void push_back (T *item_) {
      if (item_)
         ((item_t*) item_)->index ((int) items.size ());
      items.push_back (item_);
   }
   
   inline void erase (T *item_) {
      erase (((item_t*) item_)->index ());
   }
   
   inline void erase (size_type index_) {
      if (items.back ())
         ((item_t*) items.back ())->index ((int) index_);
      items [index_] = items.back ();
      items.pop_back ();
   }
   
   inline void swap (size_type index1_, size_type index2_) {
      if (items [index1_])
         ((item_t*) items [index1_])->index ((int) index2_);
      
      if (items [index2_])
         ((item_t*) items [index2_])->index ((int) index1_);
      
      std::swap (items [index1_], items [index2_]);
   }
   
   inline void clear () { items.clear (); }
   inline size_type index (T *item_) {
      return (size_type) ((item_t*) item_)->index ();
   }
   
private:
   
   typedef std::vector <T*> items_t;
   items_t items;
   
   array (const array&);
   const array &operator = (const array&);
};

эдакий хитрый контейнер-гибрид вектора с стека.

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

Код


bool array::exists(T* item_) const {
   ....
}

тип items_t изменять нельзя.
сортировать items нельзя.

идеи?

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

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 11.2.2012, 18:19 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

boostcoder, вопрос то в чем ? как быстрей всего в неотсортированном массиве найти нужное значение?

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

http://opendots.net

boostcoder

Дата 11.2.2012, 18:25 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(mes @ 11.2.2012, 18:19

)

как быстрей всего в неотсортированном массиве найти нужное значение?

да нет же!
хотел поинтересоваться, как у Вас дела? что нового?

smile

и про сабж заодно узнать.

Это сообщение отредактировал(а) boostcoder - 11.2.2012, 18:28

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

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 11.2.2012, 18:53 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(boostcoder @ 11.2.2012, 17:25

)

хотел поинтересоваться, как у Вас дела? что нового?

а ну так бы сразу и сказали smile

дела в порядке, в остальном тоже все хорошо ) как у Вас ?

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

http://opendots.net

boostcoder

Дата 11.2.2012, 18:53 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

вот я дурень smile

это же вектор. его адреса располагаются непрерывно. достаточно проверить указатель на предмет его вхожести в диапазон адресов вектора.

Добавлено через 51 секунду

Цитата(mes @ 11.2.2012, 18:53

)

дела в порядке, в остальном тоже все хорошо

вот и славно smile

Цитата(mes @ 11.2.2012, 18:53

)

как у Вас ?

да вот. туплю по полной smile

Добавлено через 5 минут и 39 секунд

Цитата(boostcoder @ 11.2.2012, 18:53

)

достаточно проверить указатель на предмет его вхожести в диапазон адресов вектора.

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

говорю же, туплю..

Добавлено через 10 минут и 25 секунд
вариант - хранить в векторе сами объекты. но нельзя. они не копируемые. да и побочных правок ода наверняка будет огого...

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

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

borisbn

Дата 11.2.2012, 21:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

Цитата(boostcoder @ 11.2.2012, 17:39

)

int ID = 0

просто интересно, а зачем item'у этот ID ? или это - не весь код ?

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

boostcoder

Дата 11.2.2012, 21:31 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(borisbn @ 11.2.2012, 21:25

)

зачем item'у этот ID ?

самому любопытно.

Цитата(borisbn @ 11.2.2012, 21:25

)

не весь код ?

код-то не весь. но в любом случае этот параметр никак и нигде не используется.

а по сабжу будут идеи, кроме как сравнением со всеми элементами вектора?

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

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 11.2.2012, 21:35 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(boostcoder @ 11.2.2012, 20:31

)

а по сабжу будут идеи, кроме как сравнением со всеми элементами вектора?

если с доп. затратами, то хранить для поиска паралельно отсортированный список smile

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

http://opendots.net

boostcoder

Дата 11.2.2012, 21:37 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(mes @ 11.2.2012, 21:35

)

хранить для поиска паралельно отсортированный список

тоже думал об этом. тогда уж лучше "вопрошать" к смене вектора на множество)

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

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 11.2.2012, 21:39 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(boostcoder @ 11.2.2012, 20:37

)

. тогда уж лучше "вопрошать"

так поэтому то и спросил :

Цитата(mes @ 11.2.2012, 17:19

)

вопрос то в чем ? как быстрей всего в неотсортированном массиве найти нужное значение?

ибо топик смахивает на то, что ждете от форумчан волшебства smile

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

http://opendots.net

boostcoder

Дата 11.2.2012, 21:50 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(mes @ 11.2.2012, 21:39

)

топик смахивает на то, что ждете от форумчан волшебства

ну я подумал, что возможно на тех уроках что я прогулял, именно об этом и говорили. мало-ли smile

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

но это только пол беды.
то, что указатель входит в диапазон, еще не говорит о том, что он там есть. придется использовать std::set::find...

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

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 12.2.2012, 01:12 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

boostcoder, чем не устраивает сортированный вектор ?

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

Цитата(boostcoder @ 11.2.2012, 20:50

)

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

множество это дерево ? первый это бегин(), а последний енд() ? тогда не верно ..

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

http://opendots.net

boostcoder

Дата 12.2.2012, 02:04 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(mes @ 12.2.2012, 01:12

)

множество это дерево ?

да.

Цитата(mes @ 12.2.2012, 01:12

)

первый это бегин(), а последний енд() ?

front() и back(). не?

т.е. в нем будут лежать указатели, отсортированно.

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

Цитата(mes @ 12.2.2012, 01:12

)

чем не устраивает сортированный вектор ?

если Вы про сортировку вектора перед вставкой - то нехорошо. элементы очень часто вставляются/удаляются.

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

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 12.2.2012, 02:55 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(boostcoder @ 12.2.2012, 01:04

)

если Вы про сортировку вектора перед вставкой - то нехорошо. элементы очень часто вставляются/удаляются.

тогда вместо вектора, список..

Добавлено через 35 секунд
и не сортировать, после вставки, а вставлять соблюдая упорядочность..

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

http://opendots.net

newbee

Дата 12.2.2012, 10:45 (ссылка)

(голосов:1)

Загрузка ...

Бревно

Профиль
Группа: Участник
Сообщений: 703
Регистрация: 24.8.2011

Репутация: 4
Всего: 19

boostcoder, твоя задача сводится к поиску по контейнеру, лучше по хэшу или (само?)сбалансированному дереву. В зависимости от частоты вставок и поиска можно повыбирать среди деревьев.

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

You're face to face
With man who sold the world

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »