Поддержание порядка в неупорядоченном наборе после использования вставки C++

Question

Как я могу сохранить порядок элементов в неупорядоченном наборе после использования вставки (или emplace) без выделения во время построения?

Для деталей в этой проблеме, вот пример:

• Построено неупорядоченное множество S целых чисел
• 480 вставлено в S: S = {480}
• 32 вставлено в S: S = {32 480}
• 23 вставляется в S: S = {23 32 480}
• 16 вставляется в S: S = {16 23 32 480}
• 19 вставлен в S: S = { 19 480 32 23 16 }

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

Answer 1

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

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

Если вам нужен набор с определенным порядком итераций, вот что std::set для. Тем не мение, std::set всегда заказы по значению ключа, а не по порядку вставки.

Вам может потребоваться объединить несколько контейнеров для достижения желаемой семантики доступа.

Answer 2

Один из способов — использовать «std::vector».

      #include <iostream>
#include <vector>
#include <algorithm>

void insertIntoVector(std::vector<int> &vec, int const value) {
    if (std::find(vec.cbegin(), vec.cend(), value) == vec.cend()) {
        vec.push_back(value);
    }
}

int main() {
    std::vector<int> vec;

    insertIntoVector(vec, 1);
    insertIntoVector(vec, 2);
    insertIntoVector(vec, 3);
    insertIntoVector(vec, 3);
    insertIntoVector(vec, 4);

    for (int const value : vec) {
        std::cout << value << std::endl;
    }

    return 0;
}

Answer 3

Неупорядоченные множества обычно основаны на распределении хеш-функций и имеют время доступа O(1).

Упорядоченные наборы обычно основаны на деревьях AVL, а доступ основан на функциях сравнения между ключами. Они имеют время доступа O(log(n)) в целом, но порядок ключей сохранения.

Вам нужно подумать дважды, если вы хотите быстрый доступ или почти такой же быстрый доступ с отсортированными ключами на вашей карте. Но нет возможности иметь и то и другое (как проблема неопределенности в квантовой физике:))