ну, если расположить эти структуры последовательно... только тогда поле next не нужно и смысла во всём этом ровно ноль.

Использовать массив. // К.О. № 1

Использовать дерево, но это уже не O(1). // К.О. № 2

Нельзя. Используй вектор.

> Я знаю что мне нужен элемент с id = 5

возможно вам нужен map<int,int>

struct m *index[10];

Если для общего случая для id (любой) - то нет.

Если для частного случая (id всегда от 0 до 10 например). то надо сделать массив указателей на структуру, и заполнять его в зависимости от id.

Т.е. в начале все указатели - нули. Добавляется структура с id=2 - в массив[2] кладёшь указатель на структуру. list не нужен.

хотя list можно оставить. но всё равно за массивом надо следить, что-бы там «дохлых» указателей не оставалось.

> C/C++

списку

facepalm

10 элементов это для примера, по сути их будет много и не всегда одно и то же количество

думал делать через malloc, что то типа

for(int i = 0; i++; i < 10)
     memcpy(list,(u_char *) + i*(sizeof(struct m)), sizeof(struct m));

но уж больно криво

Можно оптимизировать

Обращение по индексу можно существенно оптимизировать, особенно когда речь идет о последовательном или около того проходе по списку. Во время обращения к элементу по индексу внутри списка сохраняется этот индекс, а также «итератор» (или что угодно, играющее его роль), соответствующий этому индексу. При следующем обращении по индексу проверяешь, откуда до него быстрее добраться: с головы, с сохраненного итератора или с хвоста (если список двухсвязный).

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

Кто пустил музыкантов в Development?

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

>Если для частного случая (id всегда от 0 до 10 например). то надо сделать массив указателей на структуру, и заполнять его в зависимости от id.

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

почему нельзя испоьзовать realloc?

Можно ли как сразу обратиться к 5-му элементу?

нет.
если сразу то array, vector, map.

Если id целые и идут подряд, и размер бол-мене известен, то вектор с запасом по длине и счетчик элементов. Если размер существенно меняется, то вектор с блочным выделением памяти (список векторов). Если id разреженные, то map.

Вы б задачу уточнили, а то вон народ уже велосипеды из списков указателей для Вас строить собрался;-)

под линукс? выдели гиг виртуальной памяти и заполняй по мере необходимости в виде массива, а не списка :) или выдели полгига и сделай там массив указателей на ноды списка :)

Если вы сделаете дополнительно struct m *list, то каждый раз, когда вы будете изменять список, вам придется в среднем по половине этого list перебирать, чтобы обновить его.

Допустим, удаляете вы m[5], для самого списка это делается элементарно и затрагивает лишь два соседних элемента, а вот чтобы обновить массив, придется перебирать все m[6]..m[end].

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

>Допустим, удаляете вы m[5], для самого списка это делается элементарно и затрагивает лишь два соседних элемента, а вот чтобы обновить массив, придется перебирать все m[6]..m[end].

У него, в исходном посте: «id равно n+1'ому элементу массива.». Значит ему всё равно придётся пересчитывать все id у всех последующих элементов.

Видимо, расчёт на то, что удаления не будет, или будет, но редко.

Тогда проще массив сделать, а не список.

>Тогда проще массив сделать, а не список.

Мне, почему-то, кажется, что автор изобретает динамический массив:)

Дык, realloc же есть...

>думал делать через malloc, что то типа

for(int i = 0; i++; i < 10)

тут недавно тред был как раз про такую конструкцию.

тут недавно тред был как раз про такую конструкцию.

Ну, иногда такая запись к плохим вещам не приведет, например, вот два эквивалента:

for(i = -10; i < 0 ; i++)
и
for(i = -10; i++; i < 0)

> тут недавно тред был как раз про такую конструкцию.

Это где неудачник ныл о сложной ошибке, которую сложно обнаружить в коде?

Если неудачник в смысле Alv, то да. http://www.linux.org.ru/forum/development/5973653

Можно ли сделать обращение к элементу списка таких структур, таким же быстрым как к элементу массива, если я точно знаю номер элемента массива, id равно n+1'ому элементу массива.

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

Тут все такие умные в std::map тычут забывая что map это красно-черное дерево и доступ там O(log(n))

> Тут все такие умные в std::map тычут забывая что map это красно-черное дерево и доступ там O(log(n))

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

Да тут уже сказали - хеш-таблица. В расширении stl есть готовая. Если id эти так и остантся численными то хеш значение и будет этот id по маске.

> Да тут уже сказали - хеш-таблица. В расширении stl есть готовая

да - есть, вообще контейнеров разных мастей полно, и все их авторы ссылаются на бенчмарки, что они быстрее всех, но у стандартного map есть один маленький плюс - он стандартный, хотя если конечно задача требует, и это оказывается узким местом - то не вопрос подобрать что-то на замену, но если у человека «10ть элементов» (с), то смысла использовать что-то нестандартное просто нет

хеш-таблица

А как же коллизии?

я вот так набыдлокодил себе(многое над переделать)):

struct J {
  char *name;
  unsigned int id;
};

struct Jarray {
  unsigned int Jc;
  struct J **Jv;
}
struct J *jnew() {
  struct J *newitem = malloc (sizeof (struct J));
  newitem->name = "anon";
  newitem->id = 0;
  return newitem;
}

struct Jarray *jarray_new () {
  struct Jarray *newarray = malloc (sizeof (struct Jarray));
  newarray->Jc = 0;
  newarray->Jv = malloc (sizeof (struct J*));
  *(newarray->Jv) = NULL;
  return newarray;
}

void jarray_append (struct Jarray *vector, struct J *item) {
  struct J **newvalue =  calloc (sizeof (struct J*), vector->Jc + 1);
  int i;
  for (i = 0; i < vector->Jc; i++) {
    *(newvalue + i) = *(vector->Jv + i);
  }
  *(newvalue + vector->Jc) = item;
  free (vector->Jv);
  vector->Jv = newvalue;
  vector->Jc += 1;
}

struct J *jget_by_num(struct Jarray *from, int i) {
  if (i >= from->Jc || i < 0)
    return NULL;
  return *(from->Jv + i);
}

это для неопределившихся с C/C++

> Да тут уже сказали - хеш-таблица. В расширении stl есть готовая. Если id эти так и остантся численными то хеш значение и будет этот id по маске.

А если элементов много больше чем число вариантов хэша, или если все id выьраны так что у них одно и то же хэш значение?;-)

ТС так задачу и не уточнил, так что соревнование «кто больше знает контейнеров и чей контейнер круче» толку не имеет - от задачи все зависит...

Открывать http://ru.wikipedia.org/wiki/Список_структур_данных и выбирать, да. :)

> Тут все такие умные в std::map тычут забывая что map это красно-черное дерево и доступ там O(log(n))

++