пора код показать видимо.

однако show me the money и прочий джери мак его гуаер.

Теперь изменим условие: элементы могут удаляться из любой части структуры данных

Если говорить по русски, может удаляться любой элемент, а не только первый/последний. Но добавляться элементы могут только в начало/конец, так?

Теперь возникает такой интересный вопрос - как выбирается элемент для удаления? Есть два сценария:

1) проходястся все элементы структуры, и в процессе прохода некоторые элементы удаляются. Эта задача имеет совсем хорошее решение если элементы можно передвигать в памяти, и просто неплохое решение если элемент не может передвигаться в памяти.

2) произвольный элемент может удаляться случайным образом (т.е. пользователь вдруг решает что нужно убить элемент номер 1239001). В этом случае основной вопрос - по какому ключу осуществляется доступ? Если ключ должен быть постоянным все время жизни элемента, то мы неизбежно приходим к ассоциативному массиву. Если ключ может меняться во время жизни элемента, то задача в общем случае лишена смысла, в тех частных случаях когда задача смысл имеет нужно очень четко оговаривать время жизни ключа.

2 сценарий, ключ постоянный

Тогда ассоциативный массив без вариантов. С учетом добавления только в конец/начало и ограниченного размера используемой памяти можно как то улучшить существующие реализации какого нить дерева, но чудес не будет скорей всего.

А, уникальность ключа нужна (т.е. для каждого нового элемента должен быть новый ключ, не использовавшийся ранее)? Или допустимо повторно использовать ключи удаленных элементов?

да повторное использование имеет место, но в каждый момент времени коллизий нет

ну ты указал время работы log n, а это время даёт и двусвязный список + ассоциативный массив, и как я понял твоё решение меняет двусвязный список на буфер, а ассоциативный массив на дерево счётчиков, правильно?

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

При добавлении элементов ячейки переходят в список занятых элементов, в этом списке элементы лежат в порядке добавления.

Ключом является положение элемента в массиве.

При нехватке места (список свободных ячеек пуст) затираем первый элемент из списка занятых, и перемещаем его в конец списка занятых (кольцевой буфер с курсором).

При удалении элемента ячейка перемещается в список пустых ячеек.

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

Писать начал вчера вечером, но не успел. Пока был занят, всё уже обсудили. Но, тем не менее, опубликую. Код не тестировался и даже не компилировался ни разу. Просто более-менее формальное изложение идеи. Разумеется, глобальные переменные нужно перенести в соответствующие классы, функции превратить в методы этих классов, константы сделать параметрами шаблонов. Но мне было лень.

массив фиксированного размер

#define ITEMS_MAX 100500
item_t items[ITEMS_MAX];

метод добавления элементов не определён(требуется указать в решении)

size_t slot_allocate();

size_t add_item(item_t item)
{
    size_t slot = slot_allocate();
    items[slot] = item;
    return slot;
}

метод извлечения элементов произвольный(то есть любой элемент можно извлечь вне зависимости от других элементов)

void slot_free(size_t slot);

item_t extract_item(size_t slot)
{
    item_t item = items[slot];
    slot_free(slot);
    return item;
}

В случае переполнения массива каждый раз удалять самый старый элемент на данный момент времени и заменять его новым.

#define LIST_HEAD_ALLOCATED (ITEMS_MAX)
#define LIST_HEAD_FREED     (ITEMS_MAX + 1)
#define LIST_SIZE           (ITEMS_MAX + 2)

size_t list_next[LIST_SIZE];
size_t list_prev[LIST_SIZE];

void list_init()
{
    for(size_t i = 0; i < LIST_SIZE; ++i)
    {
        list_next[i] = i;
        list_prev[i] = i;
    }
}

void list_remove(size_t i)
{
    size_t n = list_next[i];
    size_t p = list_prev[i];

    assert(list_next[p] == i);
    assert(list_prev[n] == i);

    list_next[p] = n;
    list_prev[n] = p;

    list_next[i] = i;
    list_prev[i] = i;
}

void list_insert(size_t prev, size_t i)
{
    list_remove(i);

    size_t p = prev;
    size_t n = list_next[prev];

    list_next[p] = i;
    list_prev[i] = p;

    list_next[i] = n;
    list_prev[n] = i;
}

void slot_free(size_t slot)
{
   list_insert(LIST_HEAD_FREED, slot);
}

size_t slot_allocate()
{
    size_t slot = list_prev[LIST_HEAD_FREED];
    if(slot == LIST_HEAD_FREED)
        slot = list_prev[LIST_HEAD_ALLOCATED];
    assert(slot < ITEMS_MAX);
    list_insert(LIST_HEAD_ALLOCATED, slot);
    return slot;
}

size_t slot_allocator_init()
{
    list_init();
    for(size_t i = 0; i < ITEMS_MAX; ++i)
        free_slot(i);
}

Могу предложить похожее решение в котором элементы автоматически группируются в одном конце массива( и проблема с фрагментацией решается): так же как ты и говорил на массиве фикс. длины создаётся двусвязный список, помимо этого создаётся очередь внеочерёдно удалённых и пустых ячеек которая изначально не заполнена, работает оно так: при добавлении элементов проверяется очередь пустых ячеек, если в ней ничего нет пишем по порядку просто в двусвязный список, добавляя в ассоциативный массив( ключ - значение элемента, а значение - номер элемента в массиве фикс. длины), в случае удаления произвольного элемента в очередь пустых элементов добавляем номер его положения в фикс. массиве, и потом когда надо будет добавить новый элемент мы его запишем на место удалённого таким образом заполнение будет стремиться к одному из концов массива. Ну естественно каждый добавляемый элемент мы соединяем через указатели и всё такое что требует двусвязный список

В условии твоей задачи также не написано, что ты сам будешь что-то удалять. Там написано: «В случае переполнения массива каждый раз удалять самый старый элемент на данный момент времени и заменять его новым.», что соответствует поведению LRU кеша. Как я понял, у твоей структуры данных всего два метода должно быть: put(key, value) и get(key), где key вполне может быть числом в заранее известном диапазоне.

ну потом, если ты посмотришь комменты, в условии есть извлечение элементов, это и есть удаление.

Сконпелялось

#include <cstring> // for size_t
#include <cassert>

template <size_t Size>
class List
{
	struct Entry
	{
		size_t prev;
		size_t next;
	};

	Entry entries[Size];

	void Remove(size_t i)
	{
		size_t n = entries[i].next;
		size_t p = entries[i].prev;

		assert(entries[p].next == i);
		assert(entries[n].prev == i);

		entries[p].next = n;
		entries[n].prev = p;

		entries[i].next = i;
		entries[i].prev = i;
	}
public:
	List()
	{
		for(size_t i = 0; i < Size; ++i)
		{
			entries[i].next = i;
			entries[i].prev = i;
		}
	}

	void Insert(size_t prev, size_t i)
	{
		Remove(i);

		size_t p = prev;
		size_t n = entries[prev].next;

		entries[p].next = i;
		entries[n].prev = i;

		entries[i].next = n;
		entries[i].prev = p;
	}

	size_t GetPrev(size_t i) const
	{
		return entries[i].prev;
	}
};

template <size_t Size>
class SlotAllocator
{
	enum {
		HeadAllocated = Size,
		HeadFreed = Size + 1
	};

	List<Size + 2> list;
public:
	SlotAllocator()
	{
		for(size_t i = 0; i < Size; ++i)
		{
			Free(i);
		}
	};

	void Free(size_t slot)
	{
		list.Insert(HeadFreed, slot);
	}

	size_t Allocate()
	{
		size_t slot = list.GetPrev(HeadFreed);
		if(slot == HeadFreed)
			slot = list.GetPrev(HeadAllocated);
		assert(slot < Size);
		list.Insert(HeadAllocated, slot);
		return slot;
	}
};

template<size_t Size, typename Item>
class Array
{
	SlotAllocator<Size> slot_allocator;
	Item items[Size];
public:
	size_t Add(const Item &item)
	{
		size_t slot = slot_allocator.Allocate();
		items[slot] = item;
		return slot;
	}

	Item Extract(size_t slot)
	{
		Item item = items[slot];
		slot_allocator.Free(slot);
		return item;
	}
};

int main()
{
	Array<100500, double> array;
	size_t p = array.Add(7);
	size_t q = array.Add(11);
	double seven = array.Extract(p);
	double eleven = array.Extract(q);
	return 0;
}

удаляем из середины... ?

Ути-пути, ну давай забабахаем ещё один массивчик, где по индексу будет хранится ссылка/указатель на соответствующий элемент в списке упорядоченному по времени добавления. При удалении элемента сразу получаем ссылку на нужный элемент списка и всё ок. Заодно будет это вместо карты свободных.

функционала

Функционалы, линейные функционалы, непрерывные функционалы Москвы, дельта-функция скачать бесплатно, функционалы L^2 -> ℂ без СМС скачать, слабая сходимость, теорема Рисса купить

фенвик катит

с добавкой миграцией пустот(амортизированная цена) - шоб при извлечении из середины пустота замещалась следующим ( однократно)

шоб пустоты концентроровались с того края где чаще извлечения (тогда некоторые извлечения края будут резко возвращать в «заведомо пустое»

иначе необходимая память в разы больше гарантированного размера буфера

збс, а где такой алгоритм со случайными удалениями взял?да и можно сделать так что бы он при удалении элемента в середине не шел до конца массива а заполнял освободившиеся ячейки?

а где такой алгоритм со случайными удалениями взял?

Алгоритм очевидный, взял из головы. Анон выше двумя словами описал его же: Вопрос к алгоритмистам (комментарий) , т.е. очевиден этот алгоритм не только мне.

Если тебе не очевидно, то для развития интуиции предлагаю изучить книжку «А. Шень. Программирование: теоремы и задачи». http://www.mccme.ru/free-books/shen/shen-progbook.pdf

да и можно сделать так что бы он при удалении элемента в середине не шел до конца массива а заполнял освободившиеся ячейки?

Можно. Например, если вместо

 	void Free(size_t slot)
	{
		list.Insert(HeadFreed, slot);
	}

 	void Free(size_t slot)
	{
		size_t p = list.GetPrev(HeadFreed);
		list.Insert(p, slot);
	}

ну ок, я никогда не был силён в эффективной реализации алгоритмов :(

как представленное решение согласуется с быстрым извлечением произвольной ячейки из очереди?

из какой очереди уточни пжалста а то могу не так понять :)

когда удаляем из «середины» дека

ну так его метод Add возвращает фактическое положение элемента, и хранить это значение можно в ассоциативном массиве где ключ это элемент а значение его фактическое положение, время поиска по такому массиву будет logn, а это тоже что и твоё решение, правда тут дублируется каждый элемент, но тогда в его реализации можно непосредственно массив элементов вообще выкинуть, и в случае удаления элемента из середины можно находить фактическое значения элемента в ассоциативном массиве и проблем нет, а если удалять самый старый элемент то можно по значению фактического положения в ассоциативном массиве его находить и удалять

а если использовать хеш таблицу то элемент дублироваться не будет, и тогда вполне себе можно оставить массив элементов в его реализации на месте

да и я имел ввиду не сам алгоритм откуда взял а реализацию :) алгоритм то я придумал довольно быстро а вот так же круто как у тебя придумать не смог :)

В упомянутой книжке алгоритмы идут с реализациями. Высококачественными.

Спасибо за подсказку годной книжки)

ЯННП. Какой критерий поиска?

Просто когда говорят и стеках и очередях и тд то при получении доступа к элементу он автоматически удаляется из этой структуры

ЩИТО? Кто тебе сказал такую глупость?

И да, если тебе нужно минимальное время поиска И минимальное время удаления, то гугли «сбалансированные деревья». Там логарифмическое время вставки И поиска.

С массивом время вставки O(N)

Со списком время поиска O(N)

С хешем не получится найти как ты говоришь «самый старый», только «конкретно ЭТОГО времени».

для типа список не определена, например, операция достать n-ный элемент

вполне себе определена, только её цена O(N).

ты используешь слово массив в частном случае(а именно тех массивов с которыми мы знакомились когда начинали кодить), хотя забываешь что на жестких дисках давным давно инфа читалась последовательно, то есть нельзя начать читать файл с середины, и тогда всё равно применялся термин массив данных, хотя технически это частный случай списка

так бы сразу и сказал.

PS: Любопытная шизофазия.

Т.о. в массиве будет два списка: пустые и непустые элементы.

Выборка элемента по индексу - как у массива, за О(1).

ЩИТО?

а кому и зачем нужен твой рандомный индекс?

Доступ по номеру элемента? Ну так в общем случае это быстро не будет.

тоже дерево нужно. Просто в каждом узле надо его вес хранить. Вес левого поддерева + вес правого поддерева + 1. Тогда, если вес левого поддерева корня 20, а вес правого поддерева корня 30, то слева лежат узлы за номерами 0..19, сам корень имеет №20, а правее него узла №№21..50. Время поиска узла по номеру O(log(N)) если дерево не вырожденное.

Тред не читал.

«Массив фиксированного размера», как же надо извратиться, чтобы хоть какую-то операцию над ним сделать неконстантной по времени?

Чтобы не быть голословным вот сходил в вики только что:

f(n)∈Θ(g(n)) f ограничена снизу и сверху функцией g асимптотически ∃(C,C′>0),n0:∀(n>n0)|Cg(n)|<|f(n)|<|C′g(n)|

тета от эн - это строгая ассимтотическая сложность, означающая, что алгоритм всегда имеет одинаковый рост по времени, не зависимо от входных данных. Обратить внимание надо на ∀(n>n0) , то есть если есть (можно найти, выбрать) некое n0, достаточно большое, начиная с которого функция роста принадлежит семейству неких функций для любого n > n0, то тэта от эн будет являться собственно таковой функцией. Ну дык это... Берем n0 === максимальному размеру массива, по определению массив дальше расти не может (все существующие n, это только n === n0), для этого n0 время прохода по массиву будет константным (будь то список, массив, хеш таблица, дерево), а значит время любой операции будет также константным.

Смысл «константное время операции» применим только к структурам данных произвольной величины.

«Среднее время поиска» - это еще веселее, если мы оперируем таким понятием (подбираем под него решение), значит сложность зависит от самих входных данных, чтобы оперировать этим надо знать какую-то дополнительную информацию об элементах, которые мы планируем добавлять/удалять. Опять же это неприменимо к фиксированным по размеру структурам данных.

посмотри реализацию Manhunt, добавь к ней хеш таблицу где ключ - элемент, значение - фактическое положение в массиве( то что возвращает функция Add), хеш таблица не нужна для поиска самых старых значений, а для удаления рандомных из середины, если в зависимости от входных данных правильно подобрать хеш-функцию мы получим время поиска по ней стремящееся к О(1), а если нужно удалить самый старый элемент на данный момент то мы просто из списка удаляем такой элемент и по элементу находим его в хеш таблице и удаляем оттуда.

«Массив фиксированного размера», как же надо извратиться, чтобы хоть какую-то операцию над ним сделать неконстантной по времени?

1. из ОП следует, что у ТСа иногда(не всегда) бывает переполнение. А значит то, что он называет «фиксированный» на самом деле «ограниченный сверху».

2. операция вставки/удаления в/из определённого места. В любом случае, рано или поздно наступит момент, когда тебе придётся двигать данные внутри массива. А это сложность O(N).

посмотри реализацию Manhunt

wtf?

хеш таблица не нужна для поиска самых старых значений, а для удаления рандомных из середины, если в зависимости от входных данных правильно подобрать хеш-функцию мы получим время поиска по ней стремящееся к О(1), а если нужно удалить самый старый элемент на данный момент то мы просто из списка удаляем такой элемент и по элементу находим его в хеш таблице и удаляем оттуда.

ЯННП. У тебя хеш-таблица, массив и список сразу?

И да, что-бы в хеш-таблицы получить время поиска O(1), необходимо, что-бы число коллизий было →0. А для этого необходимо, что-бы число эл-тов было →0.

Про реализацию:

1. как ты собрался по эл-ту искать хеш? Как вообще хеш-таблица организована?

2. когда ты удаляешь «самый старый» у тебя получается дырка в конце, где старые хранятся. А где новые — места уже нет. Предлагаешь сдвигать все элементы на место старых?

3. или у тебя не массив, а что-то другое? Тогда — что?

по 2)просто возьми реализацию Manhunt и в main напиши так:

Array<6, double> array;
    size_t p = array.Add(7);
    size_t q = array.Add(11);
    size_t t = array.Add(8);
    size_t y = array.Add(10);
    double seven = array.Extract(p);
    double eleven = array.Extract(q);
    p = array.Add(30);
    eleven = array.Extract(p);
    q = array.Add(16);
    q = array.Add(18);
    q = array.Add(18);
    q = array.Add(18);