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, которая делает это?» - Нет, но легко написать свой собственный код, который делает это.

4386427 26.10.2018 07:17

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

4386427 26.10.2018 07:19

Напишите двусвязный список или переключитесь на C++ и используйте std::list или std::deque

smac89 26.10.2018 07:21

Думаю, вы можете заглянуть в memmove и реализовать переключение самостоятельно, если действительно хотите.

xjedam 26.10.2018 07:24

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

Antti Haapala 26.10.2018 07:25

Что касается того, «какой язык программирования может это сделать»: * каждый язык программирования, полный по Тьюрингу, может делать то же самое »

Antti Haapala 26.10.2018 07:27

@AnttiHaapala Что касается "Что касается", какой язык программирования может это делать ":" - я не хотел знать этого, я хотел знать о встроенных модулях; В любом случае спасибо за кольцевой буфер!

bukwyrm 26.10.2018 11:26

Массив и memmove могут делать именно то, о чем вы просите. Когда массив заполнен, memmove (array, &array[1], sizeof array - sizeof *array); теперь добавляет новый элемент в конец. (но кольцевой буфер будет эффективнее)

David C. Rankin 26.10.2018 12:46
2
8
110
2

Ответы 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 26.10.2018 11:16

@bukwyrm, как я сказал в своем ответе, C++, java и python предоставляют реализацию для этого типа структуры данных. Таким образом, вам не нужно реализовывать это самостоятельно.

suvojit_007 26.10.2018 11:31

Я заглянул в C++ deque - он не позволяет автоматически отбрасывать старые члены, если приходят новые. А вот Python делает. Спасибо за это!

bukwyrm 26.10.2018 11:48

@bukwyrm ну, вам нужно изменить поведение в соответствии с вашими потребностями в зависимости от языка, который вы используете.

suvojit_007 26.10.2018 12:01

В 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; а вы не знаете ни одного языка, на котором эта функция встроена?

bukwyrm 26.10.2018 11:16

Я знаком только с некоторыми. Фортран, C, C++. Python. Perl. Delphi, Java. Не на этих языках.

P.W 26.10.2018 11:18

Да, только что проверил это прямо сейчас. Собирался прокомментировать. :)

P.W 26.10.2018 11:29

Интересно, что этот рецепт двухсторонней очереди, похоже, реализован в C. docs.python.org/3/library/collections.html#deque-recipes

P.W 26.10.2018 11:32

Collections.deque из Python - это возможность, которую я искал: новые элементы слева автоматически выталкивают старые элементы справа. Спасибо!

bukwyrm 26.10.2018 11:51

Я заглянул в C++ deque - он не позволяет автоматически отбрасывать старые члены, если приходят новые.

bukwyrm 26.10.2018 11:58

@bukwyrm: да, это не автоматический отказ в C++. Приходится выскакивать вручную. Вы хотите, чтобы я вместо этого поместил в ответ пример Python?

P.W 26.10.2018 11:59

Да, пожалуйста. Я также только что узнал, что в Java есть класс LinkedHashMap, который делает это (после переопределения removeEldest), и com.google.common.collect Class EvictingQueue также может быть тем, о чем я просил.

bukwyrm 26.10.2018 12:13

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

bukwyrm 26.10.2018 12:20

@bukwyrm: Также добавлен пример Python. Вы можете принять этот ответ, если вас устраивает.

P.W 26.10.2018 12:32

Другие вопросы по теме