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

Контейнер map: реализовать проверку на уникальность ключа - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
31.10.2012, 21:34     Контейнер map: реализовать проверку на уникальность ключа #1
Приветствую форумчан, имеется контейнер map с элементами
C++
1
2
3
4
struct Elemnts {
    int key;
    char *word;
};
Главное требование контейнера map, это уникальность ключей, каким образом можно реализовать проверку на уникальность ключа?
Заранее спасибо.

Добавлено через 33 минуты
Срочно нужна помощь.

Добавлено через 1 минуту
вот код мультикарты, как из нее сделать обычную map?
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include "iostream"
#include <stdio.h>
//МУЛЬТИКАРТА
using namespace std;
int m=4;         //начальный размер контейнера
struct tElem {//элемент контейнера
    int key;
    char *word;
};
struct tIter;
struct tNode{
    tElem * HMap; //хэш-таблица
    double KF;       //коэффициент ее заполнения     
    int Volume;   //число ячеек в массиве hmap
    tIter *Iter;   //попытка создать контейнер внутри контейнера
};
 
int fExtend(tNode *& );
void conout(tNode *& );
tNode*  fCreate(int size){//cоздать мултикарту на основе хэш-таблицы с открытой адресацией
    tElem *map= new  tElem[size];
    //for(int i =0;i<size;i++)
        //map[i].word=new char[64];
    tNode *a=new tNode;
    a->HMap=map;  
    a->Volume=size;
    a->KF=0;
    a->Iter=0;
    int i=0;while(i!=size){
        map[i].word ="nil";i++;} // пометили весь массив как "пустой"
    return a;
}
 
int fDestroy (tNode *& map){//удалить контейнер
    //for(int i =0;i<map->Volume;i++)   почему не работает?
    //  delete map->HMap[i].word;
    delete [] map->HMap;
    delete map;map=NULL;
    return 1;
}
 
//////////////////////////
int Hash(int key,int a){
    return abs(key%a);
}
////////////////////////////
int fCheck(tNode *&map,int key,char *word,int Vol){ //проверка и выдача номера индекса для нового элемента
    if(!strlen(word)) {printf("enter the word\n"); return -1;}
    int q=Hash( key,Vol);
    int i=0;
    while( (*map).HMap[q+i].word!="nil"&&map->HMap[q+i].word!="deleted") {// nill-метка означает пустоту ячейки как для поиска так и для записи , deleted-метка свободна для записи и занята при поиске элемента
        if(!strcmp(map->HMap[q+i].word,word))
          if (map->HMap[q+i].key==key)
            {printf("element is already existance,\n");
        return -1;
        } 
        i++;
        if(q+i==map->Volume)q=i=0;//идем по кругу
    }
        return q+i;//индекс ,куда будем записывать
    }
 
int fAdd(tNode *&map,int key,char *str){//   ф-я добаления 
    char *word=new char[64];strcpy(word,str);
    int i=fCheck( map, key, word,map->Volume);  //проверка и подбор индекса
    if (i==-1)return 0;
    map->HMap[i].key=key;
    map->HMap[i].word=word;
    map->KF += (double)1/map->Volume;
    if(map->KF>0.5)
    fExtend(map);// возможно нужно расширить таблицу
    return 1;
}
int fExtend(tNode *& map){
    int OldVol=map->Volume; //запомнил старый размер таблицы
    tElem *a=new tElem[map->Volume];  //буфер
    int i=map->Volume;
    while(i){
        a[i-1]=map->HMap[i-1];
            i--;
    }
    fDestroy(map);
    map=fCreate(OldVol*2);// создали новый контейнер,скопировали в нег старый, удалили
    for(int i=0;i<OldVol;i++)
        if(a[i].word!="nil"&&a[i].word!="deleted")
           fAdd(map,a[i].key,a[i].word);
    
    delete[]a;
    return 1;
}
 
 
 
tElem * fFind(tNode* &map,int key,char *word){  //поиск
    int q=Hash( key,map->Volume); int i=0,count =0;
 
    while(map->HMap[q+i].word!="nil"){
        if(!strcmp(map->HMap[q+i].word,word))
            if (map->HMap[q+i].key==key)
                return &map->HMap[q+i]; 
        i++;count++;
        if(q+i==map->Volume)q=i=0;//идем по кругу   
    }
    printf("no element\n");
    return  NULL;
}
tElem  fExecute(tNode* &map,int key,char *word){  //извлечение
    tElem* g=fFind(map,key,word);
    tElem a= {-99999,"FAIL-ERROR"};
    if(!g)return a;
    a.key=g->key;a.word=g->word;
    g->word="deleted";
    map->KF -= (double)1/map->Volume;
    
    return a;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.10.2012, 21:34     Контейнер map: реализовать проверку на уникальность ключа
Посмотрите здесь:

C++ Ассоциативный контейнер типа map
контейнер map C++
C++ Контейнер map ?
C++ Контейнер map
C++ Чтение из файла в контейнер map
C++ Контейнер map
Перевернуть контейнер map? C++
Map контейнер сортировка C++
C++ Контейнер map<int, some*>
C++ Контейнер map
C++ Контейнер map
Контейнер map содержащий векторы C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
31.10.2012, 22:03  [ТС]     Контейнер map: реализовать проверку на уникальность ключа #2
Неужели все не вкурсах как реализовать?
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
31.10.2012, 22:10     Контейнер map: реализовать проверку на уникальность ключа #3
Deimoser, алгоритм прост. Допустим, вам надо добавить пару ключ-значение. Ищите по дереву элемент с таким же ключом. Если он есть, то меняете его значение на новое. Если нет, то добавляете новый элемент.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1238 / 987 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
31.10.2012, 22:13     Контейнер map: реализовать проверку на уникальность ключа #4
Не, просто не горю желанием разбирать ваш код :)

А в чём глобальная проблема? У вас есть хешик. Вы пытаетесь добавить новый элемент. Сначала проверяете, есть ли он в хеше. Если есть, то заменяете то значение, что уже есть, на новое. Если нет, то прицепляете к списку новый элемент.
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
31.10.2012, 23:25  [ТС]     Контейнер map: реализовать проверку на уникальность ключа #5
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Не, просто не горю желанием разбирать ваш код :)

А в чём глобальная проблема? У вас есть хешик. Вы пытаетесь добавить новый элемент. Сначала проверяете, есть ли он в хеше. Если есть, то заменяете то значение, что уже есть, на новое. Если нет, то прицепляете к списку новый элемент.
Да, сам алгоритм я понял, но не удается реализовать его на практике. Сейчас допишу один вариант. но сомниваюсь в его работе, как допишу скину наработки.

Добавлено через 55 минут
Как ни странно, удалось написать даже такому недалекому в програмировании челвеку как я, спасибо)

Однако возникла новая проблема, требуется объединить два контейнера, как поступить при наличии в них одинаковых ключей?

Добавлено через 10 минут
Удалить оба элемента, оставить один из них или оставить один как есть, а второму изменить ключ на уникальный?
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
01.11.2012, 04:59     Контейнер map: реализовать проверку на уникальность ключа #6
Deimoser, если вы к одной мапе добавляете другую, то при совпадении ключей логично поступать так же, как и с добавлением одного элемента - т.е. заменяем существующее значение новым
если вы объединяете две мапы в новую, третью мапу - т.е. объединяемые мапы не должны измениться, то из двух объединяемых мап надо выбрать ту, у которой приоритет больше. Приоритет - это условное понятие. Его не надо высчитывать. Надо просто сделать соглашение. Например, та мапа, которая идет вторым аргументом, имеет больший приоритет на той мапой, которая идет первым аргументом
Удалять оба элемента не логично. А менять ключ на уникальный - трудоемко в плане замены и неудобно в плане использования.
Yandex
Объявления
01.11.2012, 04:59     Контейнер map: реализовать проверку на уникальность ключа
Ответ Создать тему
Опции темы

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