Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
77 / 50 / 16
Регистрация: 17.05.2015
Сообщений: 262
1

Массив, индекс как уникальный ID

03.07.2015, 08:27. Показов 2580. Ответов 11
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Добрый день.
Пытаюсь сделать список, который хранит в себе список всех обьектов. У этого списка есть поле - ID. По идеи оно должно быть уникальным. Но вот вопрос. При создании массива, стоит ли использовать индекс, как уникальный ID?

Class
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <string>
#include <thread>
#include <chrono>
#include "entity.h"
 
struct item {
    int &ID;
    position &pos;
    std::string &title;
    
};
 
class object_list
{
private:
    item * list;
    int top;
public:
    object_list();
    ~object_list();
 
    bool push(int &ID, position &pos, std::string &title);
    bool del_item(int ID);
};
функция.
C++
1
2
3
4
5
6
7
8
9
10
11
12
bool object_list::push(int &ID, position &pos, std::string &title) {
    for (int i = 0; i <= top; i++) {
        if (list[i].ID == ID) {
            return false;
        }
    }
    list[top].ID = ID;
    list[top].pos = pos;
    list[top].title = title;
    top++;
    return true;
}
Что если сделать так?:
C++
1
2
3
4
5
6
bool object_list::push(int ID, position &pos, std::string &title) {
    if (list[ID] != NULL) return false;
    list[ID].pos = pos;
    list[ID].title = title;
    return true;
}
Но т.к. массив выделяется с помощью new, боюсь если ID будут иметь пятизначный вид - будет много памяти жрать.

Сейчас делаю подобие стака, но после каждого удаления объекта - идет сортировка массива. (Сдвиг, что бы занять свободное пространство)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.07.2015, 08:27
Ответы с готовыми решениями:

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

Не обнаружен уникальный индекс
Доброго времени суток! В акцессе работаю 1 день, помогите разобратсья с парочкой проблем и...

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

Не обнаружен уникальный индекс
CREATE TABLE TypeSpis( + Integer PRIMARY KEY, + ...

11
Модератор
Эксперт С++
13507 / 10757 / 6412
Регистрация: 18.12.2011
Сообщений: 28,718
03.07.2015, 08:37 2
Цитата Сообщение от Valeryn Посмотреть сообщение
int &ID;
И это компилируется?
Здесь нельзя объявлять ссылки.
0
Неэпический
17870 / 10635 / 2054
Регистрация: 27.09.2012
Сообщений: 26,737
Записей в блоге: 1
03.07.2015, 08:48 3
Но т.к. массив выделяется с помощью new, боюсь если ID будут иметь пятизначный вид - будет много памяти жрать.
У некоторых гигабайтами жрет и не боятся :-)
Сейчас делаю подобие стака, но после каждого удаления объекта - идет сортировка массива. (Сдвиг, что бы занять свободное пространство)
Че т как-то не совпадает с назначением стека. В стеке доступ имеется только к последнему элементу, поэтому и прочитать/удалить/изменить мы можем только его. Стек с произвольным доступом - не стек.
У Вас получатся скорее упорядоченный массив, а не стек.

А если нужна сортировка по ключу (ID), то может std::map использовать?
0
77 / 50 / 16
Регистрация: 17.05.2015
Сообщений: 262
03.07.2015, 09:12  [ТС] 4
Цитата Сообщение от zss Посмотреть сообщение
И это компилируется?
Здесь нельзя объявлять ссылки.
В таком виде я еще не компилировал. Я пытаюсь сделать, что бы ссылки в структуре напрямую вели на ID объекта. Авось получиться =).

У меня еще идея... Добавить доп. поле, говорящее об "занят/не занят". И не сортировать массив каждый раз при удалении произвольной записи, а просто оставлять поле пустым, пока его не займет новый обьект, которому надо будет найти пустое поле. А при удалении просто менять этот флаг.
0
2782 / 1935 / 570
Регистрация: 05.06.2014
Сообщений: 5,600
03.07.2015, 16:42 5
Цитата Сообщение от zss Посмотреть сообщение
И это компилируется?
А то. Главное, не забыть инициализировать ссылку в конструкторе.
0
77 / 50 / 16
Регистрация: 17.05.2015
Сообщений: 262
06.07.2015, 02:54  [ТС] 6
Цитата Сообщение от Croessmah Посмотреть сообщение
то может std::map использовать?
Не пойдет. Я вилосепедоизобритатель.
Я все переделал и немного упростил.
https://github.com/Valeryn4/Minions

Сейчас создал корневой класс, От которого будут наследоваться все другие объекты. Содержит в себе координаты, ID и title.
И есть класс "лист обьектов", который и будет хранить в этом списке все существующие обьекты программы.
Единственное, я не придумал лучшего способа, кроме как указывать ссылку на лист в конструкторе, в обязательном порядке, что бы обьект автоматически прописывал себя в списке при инициализации. Так же не знал, как придумать авто-удаление из списка, кроме как забить в классе указатель на список, а после при вызове дискриптора по укзаателю удалять себя из списка, но это на костыль больше смахивает.

Так же думаю над генерацией ID. Либо генерировать во время создания обьекта, в конструкторе, либо генерировать отдельно, уже в дочерних классах, когда они будут инициализировать особые параметры обьектов.
0
Эксперт С++
8739 / 4317 / 960
Регистрация: 15.11.2014
Сообщений: 9,760
06.07.2015, 07:25 7
Цитата Сообщение от Valeryn Посмотреть сообщение
Добавить доп. поле, говорящее об "занят/не занят".
ещё чутка, и вы изобретете объектный пул.

Цитата Сообщение от Valeryn Посмотреть сообщение
Так же думаю над генерацией ID
в качестве автоматического айдишника объекта можно использовать его адрес.
потому что адреса всех объектов гарантированно уникальны.
0
77 / 50 / 16
Регистрация: 17.05.2015
Сообщений: 262
06.07.2015, 08:03  [ТС] 8
Цитата Сообщение от hoggy Посмотреть сообщение
его адрес.
потому что адреса
Интересный подход, в планах у меня есть расчет, что вся эта порнография может быть сохранена в файл и из него выгружена и ID могут уже не соответствовать адресу.
Цитата Сообщение от hoggy Посмотреть сообщение
ещё чутка, и вы изобретете объектный пул.
больше велосипедов богу велосипедов

Правда эта программа не прилично долго создает объекты я заметил. Примерно 1обьект в секунду, хотя что самое долгое там может быть, так это только функция rand().
0
Эксперт С++
8739 / 4317 / 960
Регистрация: 15.11.2014
Сообщений: 9,760
06.07.2015, 08:22 9
Цитата Сообщение от Valeryn Посмотреть сообщение
Интересный подход, в планах у меня есть расчет, что вся эта порнография может быть сохранена в файл и из него выгружена и ID могут уже не соответствовать адресу.
гм...

ну а если так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <atomic>
#include <iostream>
 
 
 
// что бы получать id, нужно унаследоваться от этого класса
class AutoID
{
    typedef std::atomic<size_t> 
        count_t;
public:
 
    AutoID()
        :mID( ++GenID() )
    {}
    
    AutoID(const AutoID& r)
        :mID(r.mID)
    {}
    
    
    // единственный метод получения айдишника
    size_t GetID()const 
        { return mID; }
    
private:
    static count_t& GenID()
        { static count_t n(0); return n; }
    
    size_t mID;
};
 
 
struct sample : AutoID
{};
 
 
 
int main()
{
    std::cout << "Hello, world!\n";
    
    
    sample arr[3];
    
    for(const auto& i: arr)
        std::cout << "id = " 
            << i.GetID() 
            << '\n';
    
}
все классы наследуются от AutoID,
который в конструкторе получает айдишник для объекта.

айдишники растут, пока не переполнится тип данных size_t.
0
77 / 50 / 16
Регистрация: 17.05.2015
Сообщений: 262
06.07.2015, 08:46  [ТС] 10
Цитата Сообщение от hoggy Посмотреть сообщение
все классы наследуются от AutoID,
Мне кажется что это не не гибко и не удобно.

У себя я пока что так сделал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "entity.h"
 
entity::entity(class object_list &objlist) {
 
    srand(time(NULL)*(rand() % 10));
    ID = rand() % 1000;
 
    for (int i = 0; i < objlist.return_size(); i++) {
        if (objlist.return_ID(i) == ID) {
            srand(time(NULL)*(rand() % 10));
            ID = rand() % 1000;
            i--;
        }   
    }
    list_ = &objlist;
    list_->push(ID, title, x, y);
}
 
 
entity::~entity() {
    list_->trash(ID);
}
Оказывается использоваться srand(time(NULL)) не самая лучшая затея. Из за него у меня в цикле "if (objlist.return_ID(i) == ID)" срабатывала раз сто.
0
Эксперт С++
8739 / 4317 / 960
Регистрация: 15.11.2014
Сообщений: 9,760
06.07.2015, 08:53 11
Цитата Сообщение от Valeryn Посмотреть сообщение
Мне кажется что это не не гибко и не удобно.
просто унаследоваться от некоторого класса,
и не заморачиваться - это не гибко и не удобно?

Цитата Сообщение от Valeryn Посмотреть сообщение
Оказывается использоваться srand(time(NULL)) не самая лучшая затея.
это нужно вызывать только 1 раз за все время жизни программы.

вот эта штука:
C++
1
2
3
4
5
6
7
for (int i = 0; i < objlist.return_size(); i++) {
        if (objlist.return_ID(i) == ID) {
            srand(time(NULL)*(rand() % 10));
            ID = rand() % 1000;
            i--;
        }   
    }
очень тормозное решение.
и чем больше объектов будет набиваться в лист,
тем медленее оно будет работать.
0
77 / 50 / 16
Регистрация: 17.05.2015
Сообщений: 262
06.07.2015, 10:06  [ТС] 12
Цитата Сообщение от hoggy Посмотреть сообщение
это нужно вызывать только 1 раз за все время жизни программы.
с ним я наблюдал такую картину:
код, внимание на cout!
Код конструктора, вызывается при создании обьекта.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include "entity.h"
#include <iostream>
entity::entity(class object_list &objlist) {
 
    srand(time(NULL));
    ID = rand() % 1000;
    for (int i = 0; i < objlist.return_size(); i++) {
        if (objlist.return_ID(i) == ID) {
            ID = rand() % 1000;
            std::cout << "\n !!! Collision!!! ID: " << ID << std::endl;
            i--;
        }   
    }
    list_ = &objlist;
    list_->push(ID, title, x, y);
}
В моем решении сид генерации почти каждый раз уникальный.

Вывод см во вложении.
Полный код программы на гитхабе.
Миниатюры
Массив, индекс как уникальный ID  
0
06.07.2015, 10:06
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.07.2015, 10:06
Помогаю со студенческими работами здесь

Не обнаружен уникальный индекс
Как можно связать дату с датой, Н рейса с Н рейса?

Уникальный индекс с датой
Есть таблица в которую импортирую данные из Экселя. Три поля Дата. Сумма, Счет - по ним создан...

Составной уникальный индекс
Здравствуйте! Можно ли в DataTable создать составной уникальный индекс? Или надо вручную проверять...

Не может обнаружить уникальный индекс
При создании таблицы наткнулся на такую проблему: &quot;Не обнаружен уникальный индекс для адресуемого...

Уникальный индекс по двум полям
есть уникальный индекс по двум полям. Нужно ли отдельно индексировать поле входящее в этот индекс,...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru