Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> ваши мысли по расширению функционала, имеющегося контейнера 
V
    Опции темы
rumit7
Дата 12.2.2012, 12:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 6
Всего: 7
Цитата(boostcoder @ 11.2.2012,  17:39)
всем привет!

имеется некоторый чужой код:
[...]
эдакий хитрый контейнер-гибрид вектора с стека.

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

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

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

идеи?

Можете объяснить задачу по конкретнее, а то это похоже на поиск черной кошки в черной комнате..

Нам обязательно искать решение в рамках существующего кода? Если да, то тогда мне не понятна связь между типами "T" и "item_t" если Вы так запросто выполняете преобразование из "T*" в "item_t*":

Код

inline void push_back (T *item_) 
{
      if (item_)
         ((item_t*) item_)->index ((int) items.size ());    // вот здесь
      items.push_back (item_);
}


Да и вообще, зачем нам метод "exists"? Я правильно понимаю, что это больше для самопроверки, чтобы item из одного array-я не удалить случайно из другого. Тогда в этих целях нужно использовать этот загадочный "ID". Его ведь не зря там указывают!? 

Ну в общем было бы легче, если бы Вы пояснили нам что конкретно решаем..
PM MAIL   Вверх
boostcoder
Дата 12.2.2012, 15:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


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

Репутация: 49
Всего: 110
Цитата(mes @  12.2.2012,  02:55 Найти цитируемый пост)
и не сортировать, после вставки, а вставлять соблюдая упорядочность..

так и сделал.

Цитата(mes @  12.2.2012,  02:55 Найти цитируемый пост)
тогда вместо вектора, список..

оператор индекса нужен.

Цитата(rumit7 @  12.2.2012,  12:06 Найти цитируемый пост)
Можете объяснить задачу по конкретнее, а то это похоже на поиск черной кошки в черной комнате..

что конкретно не понятно?

Цитата(rumit7 @  12.2.2012,  12:06 Найти цитируемый пост)
Нам обязательно искать решение в рамках существующего кода?

да. с минимумом изменений.

Цитата(rumit7 @  12.2.2012,  12:06 Найти цитируемый пост)
мне не понятна связь между типами "T" и "item_t"

каждый Т является наследником item_t.

Цитата(rumit7 @  12.2.2012,  12:06 Найти цитируемый пост)
Да и вообще, зачем нам метод "exists"? Я правильно понимаю, что это больше для самопроверки, чтобы item из одного array-я не удалить случайно из другого.

да.

Цитата(rumit7 @  12.2.2012,  12:06 Найти цитируемый пост)
Тогда в этих целях нужно использовать этот загадочный "ID". Его ведь не зря там указывают!?

этот ID всего лишь позволяет T узнать его собственный индекс в контейнере.

Добавлено через 2 минуты и 53 секунды
newbee, как уже говорил - код чужой. свобода действий ограничена.
по поводу хеш-контейнеров: подходит std::set. но у него нет оператора индекса.
использование std::map повлечет большие изменения в коде.



--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
boostcoder
Дата 12.2.2012, 17:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


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

Репутация: 49
Всего: 110
вот что получилось:
Код

#include <iostream>
#include <vector>
#include <cstring>

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 *&front ()
    {
        return items[0];
    }
    
    inline T *&back ()
    {
        return items[items.size()-1];
    }
    
    inline T *&operator [] (size_type index_)
    {
        return items [index_];
    }

    inline bool exists(T *item_) {
        size_type left = 0, right = items.size (), mid;
        while (left != right) {
            mid = (left + right) / 2;
            T *ptr = items[mid];
            
            if (ptr == item_) {
                std::cout
                << "found: left = " << left << ", right = " << right
                << ", item = " << (void*)item_ << ", ptr = " << (void*)ptr << std::endl;
                return true;
            }
            if (ptr > item_)
                right = mid;
            else
                left = mid + 1;
            std::cout
            << "exists: left = " << left << ", right = " << right
            << ", item = " << (void*)item_ << ", ptr = " << (void*)ptr << std::endl;
        }
        return false;
    }
    
    inline void push_back (T *item_)
    {
        if (!item_) return;

        ((item_t*) item_)->index ((int) items.size ());
        
        size_type left = 0, right = items.size (), mid;
        while (left != right) {
            mid = (left + right) / 2;
            T *ptr = items[mid];
            
            if (ptr == item_) {
                right = mid + 1;
                break;
            }
            if (ptr > item_)
                right = mid;
            else
                left = mid + 1;
            std::cout
            << "push: left = " << left << ", right = " << right
            << ", item = " << (void*)item_ << ", ptr = " << (void*)ptr << std::endl;
        }
        
        items.insert(items.begin() + right, item_);
    }

    inline void erase (T *item_) {
        erase (((item_t*) item_)->get_array_index ());
    }

    inline void erase (size_type index_) {
        if (items.back ())
            ((item_t*) items.back ())->set_array_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_])->set_array_index ((int) index2_);
        if (items [index2_])
            ((item_t*) items [index2_])->set_array_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_)->get_array_index ();
    }

private:

    typedef std::vector<T*> items_t;
    items_t items;

    array (const array&);
    const array &operator = (const array&);
};

int main() {
   char *str = strdup("33");
   char tmp[32] = "\0";
   array<char> v;
   
   for ( int idx = 0; idx < 5; ++idx ) {
      sprintf(tmp, "%d", idx);
   
      // alloc new memory
      char *p = strdup(tmp);
      std::cout << "p = " << (void*)p << std::endl;
      
      v.push_back(p);
   }
   std::cout << "x = " << (void*)str << std::endl;
   v.push_back(str);
   
   std::cout << std::endl;
   for ( std::size_t idx = 0; idx < v.size(); ++idx ) {
      std::cout << (void*)v[idx] << " = " << v[idx] << std::endl;
   }
   
   std::cout << std::boolalpha << v.exists(str) << std::endl;
}

http://liveworkspace.org/code/1dca57b8401c...c10861f7e910c24

вывод:
Цитата

Execution output:
p = 0x97a2e10
p = 0x97a2e30
push: left = 1, right = 1, item = 0x97a2e30, ptr = 0x97a2e10
p = 0x97a2e20
push: left = 0, right = 1, item = 0x97a2e20, ptr = 0x97a2e30
push: left = 1, right = 1, item = 0x97a2e20, ptr = 0x97a2e10
p = 0x97a2e40
push: left = 2, right = 3, item = 0x97a2e40, ptr = 0x97a2e20
push: left = 3, right = 3, item = 0x97a2e40, ptr = 0x97a2e30
p = 0x97a2e68
push: left = 3, right = 4, item = 0x97a2e68, ptr = 0x97a2e30
push: left = 4, right = 4, item = 0x97a2e68, ptr = 0x97a2e40
x = 0x97a2e00
push: left = 0, right = 2, item = 0x97a2e00, ptr = 0x97a2e30
push: left = 0, right = 1, item = 0x97a2e00, ptr = 0x97a2e20
push: left = 0, right = 0, item = 0x97a2e00, ptr = 0x97a2e10

0x97a2e00 = 33
0x97a2e10 = 0
0x97a2e20 = 2
0x97a2e30 = 1
0x97a2e40 = 3
0x97a2e68 = 4
exists: left = 0, right = 3, item = 0x97a2e00, ptr = 0x97a2e30
exists: left = 0, right = 1, item = 0x97a2e00, ptr = 0x97a2e10
found: left = 0, right = 1, item = 0x97a2e00, ptr = 0x97a2e00
true


вот только не уверен на счет эффективности..

будут предложения?

Это сообщение отредактировал(а) boostcoder - 12.2.2012, 17:22


--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
rumit7
Дата 12.2.2012, 17:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 6
Всего: 7
Цитата(boostcoder @ 12.2.2012,  17:05)
вот что получилось:
[...]
вот только не уверен на счет эффективности..

будут предложения?


Мне одному кажется что здесь ошибка

Код

((item_t*) item_)->index ((int) items.size ());


т.к. item_ это

Код

char *p = strdup(tmp);



Это сообщение отредактировал(а) rumit7 - 12.2.2012, 17:31
PM MAIL   Вверх
boostcoder
Дата 12.2.2012, 17:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


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

Репутация: 49
Всего: 110
Цитата(rumit7 @  12.2.2012,  17:30 Найти цитируемый пост)
Мне одному кажется что здесь ошибка

точно smile

Добавлено @ 17:41
но работает жо! smile 

новый тест. оптимизировал вставку первого и второго элементов:
Код

#include <iostream>
#include <vector>
#include <string>
#include <cstring>

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 *&front ()
    {
        return items[0];
    }
    
    inline T *&back ()
    {
        return items[items.size()-1];
    }
    
    inline T *&operator [] (size_type index_)
    {
        return items [index_];
    }

    inline bool exists(T *item_) {
        size_type left = 0, right = items.size (), mid;
        while (left != right) {
            mid = (left + right) / 2;
            T *ptr = items[mid];
            
            if (ptr == item_) {
                std::cout
                << "found: left = " << left << ", right = " << right
                << ", item = " << (void*)item_ << ", ptr = " << (void*)ptr << std::endl;
                return true;
            }
            if (ptr > item_)
                right = mid;
            else
                left = mid + 1;
            std::cout
            << "exists: left = " << left << ", right = " << right
            << ", item = " << (void*)item_ << ", ptr = " << (void*)ptr << std::endl;
        }
        return false;
    }
    
    inline void push_back (T *item_)
    {
        if (!item_) return;

        ((item_t*) item_)->index ((int) items.size ());
        
        size_type left = 0, right = items.size (), mid;

        if (right <= 1) {
            items.insert(items.begin() + right, item_);
            return;
        }
        
        while (left != right) {
            mid = (left + right) / 2;
            T *ptr = items[mid];
            
            if (ptr == item_) {
                right = mid + 1;
                break;
            }
            if (ptr > item_)
                right = mid;
            else
                left = mid + 1;
            std::cout
            << "push: left = " << left << ", right = " << right
            << ", item = " << (void*)item_ << ", ptr = " << (void*)ptr << std::endl;
        }
        
        items.insert(items.begin() + right, item_);
    }

private:

    typedef std::vector<T*> items_t;
    items_t items;

    array (const array&);
    const array &operator = (const array&);
};

/***************************************************************************/

struct type: item<> {
   type(const char *str)
      :str(str)
   {}
   
   std::string str;
};

/***************************************************************************/

int main() {
   type *x = new type("33");
   char tmp[32] = "\0";
   array<type> v;
   
   for ( int idx = 0; idx < 5; ++idx ) {
      sprintf(tmp, "%d", idx);
      
      type *p = new type(tmp);
      std::cout << "p = " << p << std::endl;
      
      v.push_back(p);
   }
   std::cout << "x = " << x << std::endl;
   v.push_back(x);
   
   std::cout << std::endl;
   for ( std::size_t idx = 0; idx < v.size(); ++idx ) {
      std::cout << v[idx] << " = " << v[idx] << std::endl;
   }
   
   std::cout << std::boolalpha << v.exists(x) << std::endl;
}

/***************************************************************************/

http://liveworkspace.org/code/5bf40dd59dd9...323870ae99873cc

вывод:
Цитата

p = 0x833ae28
p = 0x833ae60
push: left = 1, right = 1, item = 0x833ae60, ptr = 0x833ae28
p = 0x833ae50
push: left = 0, right = 1, item = 0x833ae50, ptr = 0x833ae60
push: left = 1, right = 1, item = 0x833ae50, ptr = 0x833ae28
p = 0x833ae88
push: left = 2, right = 3, item = 0x833ae88, ptr = 0x833ae50
push: left = 3, right = 3, item = 0x833ae88, ptr = 0x833ae60
p = 0x833aee0
push: left = 3, right = 4, item = 0x833aee0, ptr = 0x833ae60
push: left = 4, right = 4, item = 0x833aee0, ptr = 0x833ae88
x = 0x833ae00
push: left = 0, right = 2, item = 0x833ae00, ptr = 0x833ae60
push: left = 0, right = 1, item = 0x833ae00, ptr = 0x833ae50
push: left = 0, right = 0, item = 0x833ae00, ptr = 0x833ae28

0x833ae00 = 0x833ae00
0x833ae28 = 0x833ae28
0x833ae50 = 0x833ae50
0x833ae60 = 0x833ae60
0x833ae88 = 0x833ae88
0x833aee0 = 0x833aee0
exists: left = 0, right = 3, item = 0x833ae00, ptr = 0x833ae60
exists: left = 0, right = 1, item = 0x833ae00, ptr = 0x833ae28
found: left = 0, right = 1, item = 0x833ae00, ptr = 0x833ae00
true



Это сообщение отредактировал(а) boostcoder - 12.2.2012, 17:58


--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
rumit7
Дата 12.2.2012, 18:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 6
Всего: 7
Цитата(boostcoder @ 12.2.2012,  15:30)
Цитата(rumit7 @  12.2.2012,  12:06 Найти цитируемый пост)
Тогда в этих целях нужно использовать этот загадочный "ID". Его ведь не зря там указывают!?

этот ID всего лишь позволяет T узнать его собственный индекс в контейнере.

Я все же имел ввиду ID, а не array_index.

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

Как-то так..
PM MAIL   Вверх
boostcoder
Дата 12.2.2012, 18:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


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

Репутация: 49
Всего: 110
Цитата(rumit7 @  12.2.2012,  18:24 Найти цитируемый пост)
Думаю автор кода хотел использовать его для тех же целей, для которых Вы сейчас используете двоичный поиск - "для самопроверки, чтобы item из одного array-я не удалить случайно из другого"

значит он только хотел. ибо нигде этот ID не используется. как и у item`ов.



--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
rumit7
Дата 12.2.2012, 18:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 6
Всего: 7
Цитата(boostcoder @ 12.2.2012,  18:31)
Цитата(rumit7 @  12.2.2012,  18:24 Найти цитируемый пост)
Думаю автор кода хотел использовать его для тех же целей, для которых Вы сейчас используете двоичный поиск - "для самопроверки, чтобы item из одного array-я не удалить случайно из другого"

значит он только хотел. ибо нигде этот ID не используется. как и у item`ов.

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

Добавлено через 7 минут и 29 секунд
Цитата(boostcoder @ 12.2.2012,  15:30)
Цитата(rumit7 @  12.2.2012,  12:06 Найти цитируемый пост)
мне не понятна связь между типами "T" и "item_t"

каждый Т является наследником item_t.

Еще одна вещь: зачем public наследовать от item_t, а потом в коде явное преобразовывать в базовый:

Код

((item_t*) item_)->index ((int) items.size ());


Разве не проще так:

Код

item_->index ((int) items.size ());
PM MAIL   Вверх
boostcoder
Дата 12.2.2012, 18:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


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

Репутация: 49
Всего: 110
Цитата(rumit7 @  12.2.2012,  18:36 Найти цитируемый пост)
зачем public наследовать от item_t

для того чтоб образовать стойкий ABI. указатели передаются меж процессов.



--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
rumit7
Дата 12.2.2012, 19:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 6
Всего: 7
Цитата(boostcoder @ 12.2.2012,  18:54)
Цитата(rumit7 @  12.2.2012,  18:36 Найти цитируемый пост)
зачем public наследовать от item_t

для того чтоб образовать стойкий ABI. указатели передаются меж процессов.

И что ABI требует чтобы указатель на объект наследника был явно преобразован в указатель на базовый класс? А просто вызвать метод index() базового класса нельзя!? 

Это сообщение отредактировал(а) rumit7 - 12.2.2012, 19:10
PM MAIL   Вверх
boostcoder
Дата 12.2.2012, 19:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


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

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

из процесса я получаю указатель на void

Добавлено через 1 минуту и 7 секунд
rumit7, к тому же, код не мой. не терроризируй smile


--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
rumit7
Дата 12.2.2012, 19:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 6
Всего: 7
Цитата(boostcoder @ 12.2.2012,  19:28)
не понял..

из процесса я получаю указатель на void

Добавлено @ 19:29
rumit7, к тому же, код не мой. не терроризируй smile

 smile 
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0928 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.