Попалась на глаза книжка "Порождающее программирование" и возникла идея применить принципы, описанные в книге, при реализации эффективной реализации списков.

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

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

Например:
— указав, что наш список имеет фиксированную длину и операции вставки и удаления не предвидятся, должна быть сформирована реализация списка на основе массива
— наоборот, указав, что предвидится большое количество вставок будет сформирована реализация на основе связный список и т.п.

Для воплощения всего этого в жизнь надо:

1. Определиться с какими-то элементарными операциями над списками. Например:
— вставка элемента в начало/конец/конкретную позицию
— удаление элемента из начала/конца/конкретной позиции
— обновление элемента в начале/конце/конкретной позиции
— соединение списков
— разделение списков
— ... добавьте свое, удалите лишнее и пр.

2. Определиться с возможными "строительными блоками", например:
— реализация на основе массива (всегда полностью заполненный массив). Легко читать и обновлять, но если требуется вставка или удаление приходится копировать массив в другое место
— реализация на основе не полностью заполненного массива (т.е. длина массива больше или равна длине списка). Здесь при вставке и удалении не приходится копировать массив, но все же если количество элементов превысит размер массива, то его также придется копировать (добавив некоторые количеством дополнительных элементов)
— реализация на основе односвязного списка
— реализация на основе двусвязного списка
— ... добавьте свое, удалите лишнее и пр.
— а также большое количество различных комбинаций: массив массивов, список массивов, массив списков, список списков с любыми уровнями вложенности.

3. Определиться со способом задания требований:
— на основе нужно/не нужно: вставка будет, удаление нет, обновление будет
— по количеству операций: вставка столько-то % от всех операций, обновление столько-то %
— по оценкам: память не больше O(10n), время вставки O(1)
— ... добавьте свое, удалите лишнее и пр.

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

Кто-что думает по этому поводу?. Ну и критика/комментарии п.1, п.2, п.3

P.S. Только не спрашивайте зачем это нужно
Во-первых, это может быть еще кому-то интересно.
Во-вторых, возможно, такие вещи можно использовать в компиляторах языков, активно работающих со списками. Например на основе анализа кода или же прямых указаний пользователя происходят некоторые оптимизации работы со списками.
Хотя, может уже все придумано?