Контейнер, не меняющий порядок элементов при итерации

Question

[romy4]

пускай есть хеш-контейнер

typedef .... container
/// ...
container<string,string> c;

в который добавляются элементы в таком порядке:

c["Update"] = "...";
c["Connection"] = "..."; 
c["Sec"] = "...";

и есть некая итерация по нему

for ( auto it : c )
{
    cout << c.first << ": " << c.second <<  endl;
}

Ожидается:

Update: ...
Connection: ...
Sec: ...

Если бы это был map, то порядок был бы:

Connection: ...
Sec: ...
Update: ...

Если бы unordered_map, то порядок вобще любой

Sec: ...
Connection: ...
Update: ...

Подскажите контейнер для требуемого результата?

Answer 1

[Ан]

Посмотрите на подобный вопрос
Там в ответах много вариантов, частично пересекающихся с теми, что даны тут.

Comments

[romy4]

спасибо. Пробую реализовать сей интересный вариант.

Answer 2

[Amper]

Может быть это «из пушки по воробьям», но можете посмотреть в сторону Boost Multi-index

Comments

[romy4]

Возможно, но надо разобраться как сделать, чтобы ключи были уникальными.

[Amper]

Наверное, должно быть что-то в этом роде (лишь предположение при взгляде на туториал):

struct element
{
  std::string key;
  std::string value;
};

typedef multi_index_container<
  element, 
  indexed_by< 
    sequenced<>,  
    ordered_unique< member<element, std::string, &element::key> > 
  > 	
> mysupermap;

[Amper]

А нет, я ошибся — у меня всё не верно… судя по ссылке из комментария ниже для сохранения порядка нужно использовать random_access (с hashed_unique по ключу), а не sequenced.

[romy4]

Спасибо! Похоже, что это то, что надо.

[romy4]

Получилось такое:

struct Header { std::string name; str::string value; };

typedef boost::multi_index::multi_index_container <
			Header, boost::multi_index::indexed_by <
				boost::multi_index::random_access<>, boost::multi_index::hashed_unique <
					boost::multi_index::tag<name>, boost::multi_index::member <
						Header, std::string, &Header::name
					>
				>
			>
		> Headers;

Поиск по такому делу писать неудобно. Но, хотя бы, решает задачу.

[romy4]

Разобраться в Boost.MultiIndex можно, но чёрт ногу сломит в документации. Нашёл перевод на русский

Answer 3

[ixSci]

Ну Вы и название придумали. Я прежде чем зайти думал какой-то это контейнер меняет порядок при итерации :)

По поводу вопроса: «Вам шашечки или ехать?» Вы хотите иметь быстрый доступ и сохранение порядка? но так не пойдет. Выбирайте либо то, либо то. Если у Вас не большие объемы, то можете хранить vector c нужными строками и std::hash/map со строками, в качестве значений которых будут индексы в векторе.

Comments

[romy4]

Вариант иметь две переменные всегда есть. Но использовать set для хранения порядка ключей нельзя (сортировка), list нельзя (нет произвольного доступа/поиска), deque или vector нельзя (может иметь дубли). В любом из этих случаев надо городить свой велосипед. Я думал есть что-то готовое.

[ixSci]

А что мешает исключить появление дублей в векторе?

[romy4]

Кстати вектор вообще не подходит. В нём нет ни поиска, ни произвольного доступа к элементу по хэшу, например; только индекс. А мешает то, что поиск по вектору — это горождение ненужного кода.

[ixSci]

std::find тот же поиск, просто не является методом. та же одна строчка.

[ixSci]

с доступом по хешу да, вектор явно не кандидат.

Answer 4

[Ramires]

Если я правильно понял, Вам нужна FIFO-очередь. Могу ошибаться, но посмотрите std::queue(если элементы по очереди извлекаются) или std::vector, std::list(насколько я помню, в них порядок не меняется). Уже в очередь можно запихнуть Вашу структуру с двумя полями.

Comments

[romy4]

мне не столько FIFO надо, как иметь два функционала: 1) произвольный доступ; 2) buckets в виде ключ-значение, чего нет в deque/vector

[romy4]

ну да, по типу размещения элементов в нём — FIFO

Answer 5

[Анатолий]

Обычный массив числовой. Сохранение порядка 100%;

Comments

[romy4]

Не подходит под задачу.