C: массив фиксированной длины, который сбрасывает самые старые, сдвигает и добавляет новые
Мне нужна структура, которая представляет собой частичный массив и часть очереди фиксированного размера: я хотел бы иметь возможность добавлять число к одному концу, в то время как число на противоположной стороне сбрасывается. Все это время я хотел бы всегда иметь возможность сказать [i] или что-то подобное и получить значение по этому индексу (просто подглядывать, не выскакивать!).
Итак, прогресс должен выглядеть так:
a = {2,3,4} | append a 5
a = {3,4,5} | append a 99
a = {4,5,99}| now ask for a[1], get 5
и т.д. Есть ли какой-нибудь встроенный в C, который делает то или иное. похожий?
EDIT2: В настоящее время я работаю с чем-то вроде этого, что, очевидно, очень зависит от реализации, при условии, что операция unsigned char 255 + = 1 оценивается как 0:
#include <stdio.h>
#include <limits.h>
unsigned char p =0; // helper that provides the current tail of queue
int a[1 << CHAR_BIT]; // array of size 2^[bit-size of helper]
int from_a(unsigned char i) {
return a[(i+p)]; // addition of helper makes i the true index
}
void append_to_a(int x) {
a[0]=x;
p+=1; // rolling-over of unsigned char provides circularity
}
Просто из интереса, а не в части главного вопроса: есть ли это в другом языке?
Обновлено:
Процесс должен быть автоматическим (не нужно делать добавление .., а затем извлекать / удалять / сдвигать ..), доступ на запись к существующим элементам не требуется (только чтение, но индексирование).
Спасибо всем, кто ответил, что в C нет встроенного и предлагает альтернативы. Я реализовал кое-что странное, но deque, круговая очередь / -буфер и контейнер были ценными условиями поиска.
«Спасибо» всем, кто уверял меня, что в любой полной по Тьюрингу среде это возможно каким-то образом - в противном случае я бы отчаялся (мой вопрос касался встроенных модулей, но знание того, что универсальные компьютеры действительно могут вычислять, весьма успокаивает).
"есть ли другой язык, в котором есть это" - в C++ есть типы контейнеров, которые позволяют очень легко это сделать
Напишите двусвязный список или переключитесь на C++ и используйте std::list или std::deque
Думаю, вы можете заглянуть в memmove и реализовать переключение самостоятельно, если действительно хотите.
Вы Конечно хотите это иметь? Есть вещь под названием кольцевой буфер, но в ней нет ничего двигаться.
Что касается того, «какой язык программирования может это сделать»: * каждый язык программирования, полный по Тьюрингу, может делать то же самое »
@AnttiHaapala Что касается "Что касается", какой язык программирования может это делать ":" - я не хотел знать этого, я хотел знать о встроенных модулях; В любом случае спасибо за кольцевой буфер!
Массив и memmove могут делать именно то, о чем вы просите. Когда массив заполнен, memmove (array, &array[1], sizeof array - sizeof *array); теперь добавляет новый элемент в конец. (но кольцевой буфер будет эффективнее)
Ответы 2
i would like to be able to append a number to the right (or left) while the oldest number gets dumped. So the progress should look like this: [2,3,4], [3,4,5], [4,5,6], etc. Is there some built-in in C that does that?
Нет, вы должны реализовать свою собственную структуру данных.
is there a another language that has this?
Вы можете легко выполнить такую операцию с помощью Deque. В C++ (STL) или Java (в рамках коллекции) есть своя реализация. Дек можно реализовать на python с помощью модуля 'collections'.
спасибо за подтверждение отсутствия в C; а вы не знаете ни одного языка, на котором эта функция встроена?
@bukwyrm, как я сказал в своем ответе, C++, java и python предоставляют реализацию для этого типа структуры данных. Таким образом, вам не нужно реализовывать это самостоятельно.
Я заглянул в C++ deque - он не позволяет автоматически отбрасывать старые члены, если приходят новые. А вот Python делает. Спасибо за это!
@bukwyrm ну, вам нужно изменить поведение в соответствии с вашими потребностями в зависимости от языка, который вы используете.
В C нет такого встроенного. Но с контейнером C++ deque это легко сделать.
Минимальный пример:
#include <iostream>
#include <deque>
int main()
{
// Create a deque containing integers
std::deque<int> d = {1, 2, 3};
int sizeLimit = 3;
if (d.size() == sizeLimit)
{
d.pop_front(); //remove from front
}
d.push_back(4); //add at the end
// Iterate and print values of deque
for(int n : d) {
std::cout << n << '\n';
}
}
У Python есть collections.deque в своей стандартной библиотеке, которая имеет эту функцию.
import collections
d = collections.deque(maxlen=3)
print(d)
for i in range(3):
d.append(i)
print(d)
d.append(3)
print(d)
d.append(4)
print(d)
Вы можете увидеть живую демонстрацию здесь.
спасибо за подтверждение отсутствия в C; а вы не знаете ни одного языка, на котором эта функция встроена?
Я знаком только с некоторыми. Фортран, C, C++. Python. Perl. Delphi, Java. Не на этих языках.
Да, только что проверил это прямо сейчас. Собирался прокомментировать. :)
Интересно, что этот рецепт двухсторонней очереди, похоже, реализован в C. docs.python.org/3/library/collections.html#deque-recipes
Collections.deque из Python - это возможность, которую я искал: новые элементы слева автоматически выталкивают старые элементы справа. Спасибо!
Я заглянул в C++ deque - он не позволяет автоматически отбрасывать старые члены, если приходят новые.
@bukwyrm: да, это не автоматический отказ в C++. Приходится выскакивать вручную. Вы хотите, чтобы я вместо этого поместил в ответ пример Python?
Да, пожалуйста. Я также только что узнал, что в Java есть класс LinkedHashMap, который делает это (после переопределения removeEldest), и com.google.common.collect Class EvictingQueue также может быть тем, о чем я просил.
хотя я не знаю, могу ли я посмотреть любую часть очереди (я бы хотел) или просто заглянуть в начало очереди.
@bukwyrm: Также добавлен пример Python. Вы можете принять этот ответ, если вас устраивает.
«Есть ли встроенная в C, которая делает это?» - Нет, но легко написать свой собственный код, который делает это.