VPF::Структура - Форум программистов

User008

Дата 11.3.2010, 08:56 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 1

Какая структура будет наиболее подходящей для решения следующей задачи: Элементы имеют счётчик. При обращении к элементу его счётчик инкрементируется. В первую очередь обращение происходит к элементам с наибольшим значением счётчика.

Пример:
ABCD
3321

s[2] - C
CABD
3331

s[1] - A
ACBD
4331

s[0] - A
ACBD
5331

Это сообщение отредактировал(а) User008 - 11.3.2010, 08:58

GoldFinch

Дата 11.3.2010, 09:04 (ссылка)

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

Загрузка ...

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

Репутация: 6
Всего: 26

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

Код


template<typename T>
struct wrap
{
T t;
int counter;
T* operator->() { ++counter; return &t; }
};

User008

Дата 11.3.2010, 09:07 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 1

Цитата(GoldFinch @ 11.3.2010, 09:04)

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

Код


template<typename T>
struct wrap
{
T t;
int counter;
T* operator->() { ++counter; return &t; }
};

Не нахожу в этом ответе решения. Можно поподробнее?

GoldFinch

Дата 11.3.2010, 09:09 (ссылка)

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

Загрузка ...

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

Репутация: 6
Всего: 26

наверное я не так понял задачу %)

bsa

Дата 11.3.2010, 13:28 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

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

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

azesmcar

Дата 11.3.2010, 13:33 (ссылка)

(голосов:2)

Загрузка ...

uploading...

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

Репутация: 52
Всего: 211

Цитата(bsa @ 11.3.2010, 13:28

)

User008, вообще-то задание не очень понятно.

Цитата(User008 @ 11.3.2010, 08:56

)

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

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

User008

Дата 11.3.2010, 17:44 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 1

К одному и тому же получится, если обращаться каждый раз с аргументом 0. Если аргумент = 1, то обращение будет ко второму по величине счётчика элементу, если 2 - к третьему...

azesmcar

Дата 11.3.2010, 18:45 (ссылка)

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

Загрузка ...

uploading...

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

Репутация: 52
Всего: 211

User008

Тогда в чем проблема? Создай класс, в нем массив

Код


template <typename T>
class element {
   int count;
   T obj;
public:
   element(T o) : count(0), obj(o)
   T get() {
      ++count;
      return obj;
   }
}

template <typename T, int N>
class elements {
   T e[N];
public:
   T get(int n) {
       int i = <нахождение n-ного по величине счетчика>;
       return e[i].get();
   }
}

что-то вроде этого.

User008

Дата 11.3.2010, 18:52 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 1

Цитата(azesmcar @ 11.3.2010, 18:45

)

Тогда в чем проблема? Создай класс, в нем массив

Проблема не в том, как это реализовать, а в том как это реализовать быстродейственно.

azesmcar

Дата 11.3.2010, 19:59 (ссылка)

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

Загрузка ...

uploading...

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

Репутация: 52
Всего: 211

Код


#include <iostream>

template <typename type>
class element
{
public:
    element() : cnt_(0) {}

    void set(type obj)
    {
        obj_ = obj;
    }

    type get()
    {
        ++cnt_;
        return obj_;
    }

    long count()
    {
        return cnt_;
    }
private:
    long cnt_;
    type obj_;
};

template <typename type, int size>
class elements
{
public:
    void set(int n, type object)
    {
        objects_[n].set(object);
    }

    type get(int n)
    {
        type ret = objects_[n].get();

        if (n != 0 && objects_[n].count() > objects_[n - 1].count())
            std::swap(objects_[n], objects_[n - 1]);

        return ret;
    }
private:
    element<type> objects_[size];
};

int main()
{
    elements<int, 5> el;

    el.set(0, 0);
    el.set(1, 1);
    el.set(2, 2);
    el.set(3, 3);
    el.set(4, 4);

    std::cout << el.get(0) << std::endl;
    std::cout << el.get(1) << std::endl;
    std::cout << el.get(2) << std::endl;
    std::cout << el.get(1) << std::endl;
    std::cout << el.get(0) << std::endl;
}

так пойдет? идея в том, чтобы хранить отсортированный массив (по счетчику), возвращается объект, находящийся по затребованному тобой уровня счетчика. Может есть баги, не тестировал, просто набросал быстро

Это сообщение отредактировал(а) azesmcar - 11.3.2010, 20:02

User008

Дата 11.3.2010, 21:11 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 1

У меня подозрение, что если при такой реализации при состоянии 1 1 1 обратиться к третьему элементу получится 1 2 1 вместо 2 1 1.

azesmcar

Дата 11.3.2010, 21:15 (ссылка)

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

Загрузка ...

uploading...

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

Репутация: 52
Всего: 211

Цитата(User008 @ 11.3.2010, 21:11

)

Да, верно..не предусмотрел, нужно заменить на цикл smile

User008

Дата 11.3.2010, 21:26 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 1

Такое решение приходило в голову. Но я реализовал не вектором со swap'ами, а списком с поиском элемента по сравнению счётчиков и перемещением туда элемента, к которому обратились. Но по возможности желательно увеличить производительность. Быстрее ли будет реализация с вектором и swap'ами?

User008

Дата 11.3.2010, 23:10 (ссылка)

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

Загрузка ...

Опытный

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

Репутация: нет
Всего: 1

Действительно так намного быстрее, спасибо.

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