Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Нужно удалить значение в ассоциативном массиве

Автор: vovamakr 5.11.2015, 13:15

Нужно удалить значение в ассоциативном массиве
Я так реализовал:

Код


void Remove(AssociativeArray* array, const char* key)
{
    for (unsigned index = 0; index < array->size; ++index)
        array->entries[index] = array->entries[index + 1];
    --array->size;
}

но не знаю правильно ли это, так как не могу понять как в меине это все вывести(

Автор: xvr 5.11.2015, 15:15

Ваш код делает непонятно что. Точнее понятно - что то удаляет, но явно не то, что хотелось. Подсказка - где у вас в удалении используется значение параметра key ? Ответ 'нигде' (как у вас и есть) явный признак неправильной реализации smile

Автор: vovamakr 5.11.2015, 15:23

xvr,

Код


void Remove(AssociativeArray* array, const char* key)
{
    for (unsigned index = 0; index < array->size; ++index)
        array->entries[index]->key = array->entries[index + 1]->key;
    --array->size;
}

Автор: math64 5.11.2015, 15:35

Цитата(vovamakr @ 5.11.2015, 15:23

)

Код


array->entries[index]->key = array->entries[index + 1]->key;

key здесь поле внутри записи, одноименное с параметром функции. Параметр функции же здесь снова не используется.

Автор: vovamakr 5.11.2015, 15:38

math64,

Код


void Remove(AssociativeArray* array, const char* key)
{
    for (unsigned index = 0; index < array->size; ++index)
    {
        AssociativeArray::Entry* entry = array->entries[index];
        if (strcmp(entry->key, key) == 0)
        {
            array->entries[index]->key = array->entries[index + 1]->key;
            --array->size;
            
        }
}

Автор: math64 5.11.2015, 15:49

Так ты не все элементы сдвигаешь. Хотя можно не сдвигать, а оставить дырку. Но тогда нужно различать size (чмсло ненулевый элементов) и reservedSize (число выделенных элементов в массиве). Да ещё нужно не забыть delete.

Добавлено через 1 минуту и 20 секунд
И еще: не array->entries[index]->key == key, а strcmp(array->entries[index]->key, key) == 0

Добавлено через 3 минуты и 4 секунды
И копировать(если копировать) не только ключи, в всю запись - как было в первом варианте.

Автор: feodorv 5.11.2015, 16:11

Цитата(vovamakr @ 5.11.2015, 15:38

)

void Remove(AssociativeArray* array, const char* key)
{
    for (unsigned index = 0; index < array->size; ++index)
    {
        AssociativeArray::Entry* entry = array->entries[index];
        if (strcmp(entry->key, key) == 0)
        {
            array->entries[index] ->key = array->entries[index + 1] ->key;
            --array->size;

        }
}

Нет сдвига остальных записей после успешного сравнения smile

А если встретятся в массиве два одинаковых значения key?

Автор: vovamakr 5.11.2015, 16:12

feodorv,

Код


void Remove(AssociativeArray* array, const char* key)
{
    for (unsigned index = 0; index < array->size; ++index)
    {
        AssociativeArray::Entry* entry = array->entries[index];
        if (strcmp(entry->key, key) == 0)
        {
            if (index != array->size - 1)
            {
                for (unsigned current = index; current < array->size - 1; ++current)
                    array->entries[current]->key = array->entries[current + 1]->key;
            }
            array->size--;
        }
    }
}

Автор: feodorv 5.11.2015, 16:25

Цитата(vovamakr @ 5.11.2015, 16:12

)

if (index != array->size - 1)

Уже радует.

Но цикл в цикле не очень хорошо выглядит. А Вам точно нужно удалять все значения key из массива, или только первое встретившееся?

Добавлено через 1 минуту и 22 секунды
И, всё-таки, копируйте всю структуру)))

Автор: vovamakr 5.11.2015, 16:43

feodorv,

Код


array->entries[current] = array->entries[current + 1];

Добавлено @ 16:44
feodorv,
я не знаю как сделать что бы цикл не был в цикле

Код

 + я сделал  еще функцию, я правильно понимаю что в getValue нужно возвращать значение,
int* GetValue(const AssociativeArray* array, const char* key)
{
    return array->entries[value];
}

Автор: feodorv 5.11.2015, 17:17

Цитата(vovamakr @ 5.11.2015, 16:43

)

я не знаю как сделать что бы цикл не был в цикле

Если Вам нужно удалить из списка первый же элемент с ключом key, то это можно сделать так:

Код

AssociativeArray::Entry *Remove( AssociativeArray* array, const char* key)
{
    unsigned int index;
    AssociativeArray::Entry *entry;

    for (index = 0; index < array->size; ++index)
        if( strcmp(array->entries[index]->key, key) == 0) break;

    if( index >= array->size ) return nullptr;
    entry = array->entries[index];

    /* Почему не memmove? */
    for (unsigned current = index; current < array->size - 1; ++current)
        array->entries[current] = array->entries[current + 1];

    array->size--;
    return entry; // Для дальнейшего использования/высвобождения памяти
}

Если же Вам нужно удалить все записи с ключом key, то можно ввести два индекса, чтобы обойтись одним циклом, но я так и не понял, что Вам в точности нужно.

Автор: vovamakr 5.11.2015, 17:34

feodorv,  getValue()?
int* GetValue(const AssociativeArray* array, const char* key)
{
    for (unsigned index = 0; index < array->size; ++index)
    {
        AssociativeArray::Entry* entry = array->entries[index];
        if (strcmp(entry->key, key) == 0)
            return entry->key;
        return nullptr;
}

Автор: feodorv 5.11.2015, 18:30

Цитата(vovamakr @ 5.11.2015, 17:34

)

feodorv, getValue()?

Да, забыл

Цитата(vovamakr @ 5.11.2015, 17:34

)

int* GetValue(const AssociativeArray* array, const char* key)
{
    for (unsigned index = 0; index < array->size; ++index)
    {
        AssociativeArray::Entry* entry = array->entries[index];
        if (strcmp(entry->key, key) == 0)
            return entry->key value;
    }
    return 0;
}

А у Вас entry->value имеет тип (int *)??? Или это как дополнительный индикатор, найдена ли запись с данным ключом или нет? Тогда

Код


return &entry->value;

Автор: vovamakr 5.11.2015, 18:31

feodorv,

Код


struct Entry
    {
        char* key;
        int value;
    };

Добавлено через 3 минуты и 50 секунд

Код


const int* GetValue(const AssociativeArray* array, const char* key)
{
    for (unsigned index = 0; index < array->size; ++index)
    {
        const AssociativeArray::Entry* entry = array->entries[index];
        if (strcmp(entry->key, key) == 0)
            return &entry->value;
    }
        return nullptr;
}

Автор: feodorv 5.11.2015, 18:47

vovamakr, smile

Но с таким же успехом Вы можете возвращать указатель на саму запись:

Код


const struct Entry* GetValue(const AssociativeArray* array, const char* key)
{
    for (unsigned index = 0; index < array->size; ++index)
    {
        const AssociativeArray::Entry* entry = array->entries[index];
        if (strcmp(entry->key, key) == 0) return entry;
    }
    return nullptr;
}

Автор: math64 6.11.2015, 08:16

vovamakr, а удалять entry и entry->key кто будет?

Обычно в ассоциативных массивах не сдвигают записи при удалении, а оставляют дырки.
Имеется size (число ненулевых записей) и reservedSize (число выделенных записей в массиве).
size <= reservedSize. Добавлении нового элемента при равенстве reservedSize увеличивается.
Если мы больше не планируем добавлять новых ключей, делается упаковка.
При поиске, добавлении и удалении ключа сначала вычисляется кеш-код. Берется остаток от деления кэш-кода на reservedSize и получаем index, по которому предпочтительно разместить новый ключ.
Если index занят другим ключом, проверяем index+1 и т. д. В неблагоприятном случае придется просмотреть весь массив, но чаще всего будем сразу попадать на нужную запись.

Автор: xvr 6.11.2015, 11:50

Если порядок записей в ассоциативном массиве не важен (а это в большинтстве случаев так), то при удалении элемента можно просто менять местами последний элемент и удаляемый, а потом уменьшать на 1 счетчик активных элементов в массиве. Но в этом случае нужно 2 счетчика - размер массива и количество активных элементов (как уже советовал math64).