Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Valeryn
72 / 45 / 8
Регистрация: 17.05.2015
Сообщений: 241
#1

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

03.07.2015, 08:27. Просмотров 347. Ответов 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 будут иметь пятизначный вид - будет много памяти жрать.

Сейчас делаю подобие стака, но после каждого удаления объекта - идет сортировка массива. (Сдвиг, что бы занять свободное пространство)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2015, 08:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Массив, индекс как уникальный ID (C++):

как переделать массив что бы не было его остановки и как добавить индекс - C++
Такая вот задача найти индекс максимального элемента массива , вот мой код что тут не так и что следует добавить ? и почему у меня индекс...

Создать уникальный двумерный массив - C++
Пишу программку,которая находит в двумерном массиве(8*8) макс и мин значения.После чего создает прямоугольную область(фотка в...

Как поместить элемент в массив используя (индекс и значение) определенной размерности? - C++
Всем привет. Мне нужно в массив определенной размерности поместить элемент, вводля сперва индекс, а потом само значение. Все это нужно в...

Ввести массив А. В массив В перенести все элементы массива А, стоящие правее максимального элемента, и имеющие нечетный индекс. Массив В отсортировать - C++
Добрый Вечер! Написал первую часть программы по этому заданию&quot;Ввести массив А. В массив В перенести все элементы массива А, стоящие правее...

Как правильно передать уникальный аргумент в функцию - C++
Здравствуйте! Помогите пожалуйста в решении такой проблемы: Есть структура, она должна хранить в себе строку, и уникальный символ. В...

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

11
zss
Модератор
Эксперт С++
6532 / 6094 / 2007
Регистрация: 18.12.2011
Сообщений: 15,851
Завершенные тесты: 1
03.07.2015, 08:37 #2
Цитата Сообщение от Valeryn Посмотреть сообщение
int &ID;
И это компилируется?
Здесь нельзя объявлять ссылки.
0
Croessmah
Ушел
Эксперт CЭксперт С++
13553 / 7704 / 872
Регистрация: 27.09.2012
Сообщений: 19,006
Записей в блоге: 3
Завершенные тесты: 1
03.07.2015, 08:48 #3
Но т.к. массив выделяется с помощью new, боюсь если ID будут иметь пятизначный вид - будет много памяти жрать.
У некоторых гигабайтами жрет и не боятся :-)
Сейчас делаю подобие стака, но после каждого удаления объекта - идет сортировка массива. (Сдвиг, что бы занять свободное пространство)
Че т как-то не совпадает с назначением стека. В стеке доступ имеется только к последнему элементу, поэтому и прочитать/удалить/изменить мы можем только его. Стек с произвольным доступом - не стек.
У Вас получатся скорее упорядоченный массив, а не стек.

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

У меня еще идея... Добавить доп. поле, говорящее об "занят/не занят". И не сортировать массив каждый раз при удалении произвольной записи, а просто оставлять поле пустым, пока его не займет новый обьект, которому надо будет найти пустое поле. А при удалении просто менять этот флаг.
0
Renji
1999 / 1367 / 308
Регистрация: 05.06.2014
Сообщений: 3,899
03.07.2015, 16:42 #5
Цитата Сообщение от zss Посмотреть сообщение
И это компилируется?
А то. Главное, не забыть инициализировать ссылку в конструкторе.
0
Valeryn
72 / 45 / 8
Регистрация: 17.05.2015
Сообщений: 241
06.07.2015, 02:54  [ТС] #6
Цитата Сообщение от Croessmah Посмотреть сообщение
то может std::map использовать?
Не пойдет. Я вилосепедоизобритатель.
Я все переделал и немного упростил.
https://github.com/Valeryn4/Minions

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

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

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

Правда эта программа не прилично долго создает объекты я заметил. Примерно 1обьект в секунду, хотя что самое долгое там может быть, так это только функция rand().
0
hoggy
6701 / 2883 / 494
Регистрация: 15.11.2014
Сообщений: 6,480
Завершенные тесты: 1
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
Valeryn
72 / 45 / 8
Регистрация: 17.05.2015
Сообщений: 241
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
hoggy
6701 / 2883 / 494
Регистрация: 15.11.2014
Сообщений: 6,480
Завершенные тесты: 1
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
Valeryn
72 / 45 / 8
Регистрация: 17.05.2015
Сообщений: 241
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);
}
В моем решении сид генерации почти каждый раз уникальный.

Вывод см во вложении.
Полный код программы на гитхабе.
0
Миниатюры
Массив, индекс как уникальный ID  
06.07.2015, 10:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2015, 10:06
Привет! Вот еще темы с ответами:

В массив В перенести все элементы массива А, имеющие четный индекс - C++
4. Ввести массив А. В массив В перенести все элементы массива А, имеющие четный индекс, справа от которых расположены элементы с нечетным...

Массив: определить индекс столбца с максимальным количеством нулевых элементов - C++
#include &quot;stdafx.h&quot; //стандартно подключенная библеотека #include &lt;conio.h&gt; //для консольного ввода/вывода данных #include &lt;iostream&gt;...

Создать массив. Вывести на дисплей значение и индекс второго четного элемента - C++
Помогите с задачкой такой: Организовать массив (n=8). Вывести на дисплей значение и индекс второго четного элемента. Нужен текст...

Массив: произвести сдвиг элементов на к позиций, где к-индекс максимального элемента массива - C++
помогите пожалуйста разобраться с указателями, т.к. тема для меня новая и, как оказалось, сложная(( В задаче дан массив A. Нужно...


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

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