C ++: как хранить отсортированный набор кортежей?

Question

Использование GCC 4.x, g ++ и STL. Какая внутренняя структура должна использоваться для хранения такого массива: ( (1,4), (2,8), (3,7) )? Он должен иметь статические номера элементов, чтобы сохранить исходный (как добавленный) порядок.

Варианты:

• набор <карта (целое, целое)>
• массив
• массив {массив [2], массив [2]}

Можно ли это сделать с векторами в лучшем виде?

Answer 1

Если он уже отсортирован, то vector<pair<int, int> > имеет больше смысла, так как позволит вам сохранить порядок вставки (который в любом случае будет отсортирован!). Вопрос в том, хотите ли вы отсортировать по вставке или нет?

Answer 2

std::set удержание std :: pair - первое, что приходит на ум

однако это может не соответствовать этому требованию:

В нем должны быть номера статических элементов. сохранить первоначальный (как добавленный) порядок.

Answer 3

Это полностью зависит от вашего варианта использования вставки / извлечения.В любом случае, вы должны использовать std::pair или boost::tuple в качестве типа вашего элемента, поскольку они уже реализуют желаемое лексикографическое упорядочение.

Что касается контейнера и вставки / извлечения: вы можете жить без случайногодоступ?Вам нужен доступ ко всем элементам (используйте std::set) или только к вершине (используйте std::priority_queue с std::vector)?Если вам нужен произвольный доступ, используйте std::vector: вставляете ли вы отдельные элементы?Тогда это зависит от того, как вы извлекаете: все элементы, один раз, после того, как вы закончите вставку?Просто используйте push_back и std::sort, когда вы закончите.Или ты много добываешь?Затем сохраните массив отсортированным, используя std::vector::insert и std::lower_bound.