Структура данных: упорядоченная таблица(+)

[Sheryld]

Возникли проблемы с сабжем, подскажите что это такое и с чем его едят. Желательно дать ссылку на простенькую реализацию на c++.

Я попробовал реализовать через список:

struct TableItem
{
	int key;
	int release;
	char *info;

	TableItem *next;
};

сортировка идет по полю key, но оно может быть и одинаковым, тогда сортируется по полю release.

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

[Sheryld]

а может кто подскажет, как такую штуку вектором реализовать?

[Drakosha]

Структура данных: упорядоченная таблица - ???

есть СТЛ (http://www.sgi.com/tech/stl/stl_index.html) - стандарт в c++. Там есть и веkтор, и лист, и set и т.д.....

[a_ber]

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

[crawler]

мне кааатся так:

struct TableItem
{
int key;
int release;
char *info;
};

TableItem Table[100];

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

[Sheryld]

хех, а мне как раз надобно не пользоваться STL, а реализовать вручную, есть только cout и cin

[Sheryld]

2a_ber

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

[a_ber]

Извини, что долго не заметил вопроса ;(
Главное отличие списка от вектора (извини, за пересказ учебника за 2й семестр): возможность рандомального (по индексу) доступа за О(1) в векторе против возможности засунуть/убрать на любое указанное место за О(1) с сохранением порядка... Если О(1) << О(н) то это делает выбор, если речь идет о паре-тройке-даже дюжине элементов, то это критерием выбора не является... А то что является, это удовство сочленить элемент интерфейса с внутренним представлением (а тут мне кажется векторы удобнее)