Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
#1

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

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

Добрый день.
Пытаюсь сделать список, который хранит в себе список всех обьектов. У этого списка есть поле - 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 будут иметь пятизначный вид - будет много памяти жрать.

Сейчас делаю подобие стака, но после каждого удаления объекта - идет сортировка массива. (Сдвиг, что бы занять свободное пространство)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2015, 08:27     Массив, индекс как уникальный ID
Посмотрите здесь:
C++ как переделать массив что бы не было его остановки и как добавить индекс
Создать уникальный двумерный массив C++
C++ Как поместить элемент в массив используя (индекс и значение) определенной размерности?
C++ Ввести массив А. В массив В перенести все элементы массива А, стоящие правее максимального элемента, и имеющие нечетный индекс. Массив В отсортировать
C++ Как правильно передать уникальный аргумент в функцию
массив и индекс C++
В массив В перенести все элементы массива А, имеющие четный индекс C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
6321 / 5905 / 1913
Регистрация: 18.12.2011
Сообщений: 15,184
Завершенные тесты: 1
03.07.2015, 08:37     Массив, индекс как уникальный ID #2
Цитата Сообщение от Valeryn Посмотреть сообщение
int &ID;
И это компилируется?
Здесь нельзя объявлять ссылки.
Croessmah
Модератор
Эксперт CЭксперт С++
13052 / 7315 / 814
Регистрация: 27.09.2012
Сообщений: 18,052
Записей в блоге: 3
Завершенные тесты: 1
03.07.2015, 08:48     Массив, индекс как уникальный ID #3
Но т.к. массив выделяется с помощью new, боюсь если ID будут иметь пятизначный вид - будет много памяти жрать.
У некоторых гигабайтами жрет и не боятся :-)
Сейчас делаю подобие стака, но после каждого удаления объекта - идет сортировка массива. (Сдвиг, что бы занять свободное пространство)
Че т как-то не совпадает с назначением стека. В стеке доступ имеется только к последнему элементу, поэтому и прочитать/удалить/изменить мы можем только его. Стек с произвольным доступом - не стек.
У Вас получатся скорее упорядоченный массив, а не стек.

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

У меня еще идея... Добавить доп. поле, говорящее об "занят/не занят". И не сортировать массив каждый раз при удалении произвольной записи, а просто оставлять поле пустым, пока его не займет новый обьект, которому надо будет найти пустое поле. А при удалении просто менять этот флаг.
Renji
1876 / 1274 / 290
Регистрация: 05.06.2014
Сообщений: 3,633
03.07.2015, 16:42     Массив, индекс как уникальный ID #5
Цитата Сообщение от zss Посмотреть сообщение
И это компилируется?
А то. Главное, не забыть инициализировать ссылку в конструкторе.
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
06.07.2015, 02:54  [ТС]     Массив, индекс как уникальный ID #6
Цитата Сообщение от Croessmah Посмотреть сообщение
то может std::map использовать?
Не пойдет. Я вилосепедоизобритатель.
Я все переделал и немного упростил.
https://github.com/Valeryn4/Minions

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

Так же думаю над генерацией ID. Либо генерировать во время создания обьекта, в конструкторе, либо генерировать отдельно, уже в дочерних классах, когда они будут инициализировать особые параметры обьектов.
hoggy
6427 / 2645 / 458
Регистрация: 15.11.2014
Сообщений: 5,834
Завершенные тесты: 1
06.07.2015, 07:25     Массив, индекс как уникальный ID #7
Цитата Сообщение от Valeryn Посмотреть сообщение
Добавить доп. поле, говорящее об "занят/не занят".
ещё чутка, и вы изобретете объектный пул.

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

Правда эта программа не прилично долго создает объекты я заметил. Примерно 1обьект в секунду, хотя что самое долгое там может быть, так это только функция rand().
hoggy
6427 / 2645 / 458
Регистрация: 15.11.2014
Сообщений: 5,834
Завершенные тесты: 1
06.07.2015, 08:22     Массив, индекс как уникальный ID #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.
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
06.07.2015, 08:46  [ТС]     Массив, индекс как уникальный ID #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)" срабатывала раз сто.
hoggy
6427 / 2645 / 458
Регистрация: 15.11.2014
Сообщений: 5,834
Завершенные тесты: 1
06.07.2015, 08:53     Массив, индекс как уникальный ID #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--;
        }   
    }
очень тормозное решение.
и чем больше объектов будет набиваться в лист,
тем медленее оно будет работать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2015, 10:06     Массив, индекс как уникальный ID
Еще ссылки по теме:
Массив: определить индекс столбца с максимальным количеством нулевых элементов C++
Создать массив. Вывести на дисплей значение и индекс второго четного элемента C++
Массив: произвести сдвиг элементов на к позиций, где к-индекс максимального элемента массива C++
Дан массив A размера N. Вставить 0 перед каждым элементом, индекс которого кратен K C++
C++ Разработать шаблон функции, в которую передается массив и размер и возвращается индекс минимального элемента

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

Или воспользуйтесь поиском по форуму:
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
06.07.2015, 10:06  [ТС]     Массив, индекс как уникальный ID #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  
Yandex
Объявления
06.07.2015, 10:06     Массив, индекс как уникальный ID
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru