Задать вопрос

Irval

Ответы пользователя по тегу C++

  • Почему доступ к элементам vector-а O(1)?

    @Irval
    Дело в том, что std::vector - достаточно хитрая структура, использующая непрерывные блоки памяти для реализации "динамического" массива. Сам объект хранит в себе 2 различных размера - capacity (вместимость) и непосредственно size. Последний численно равен количеству добавленных Вами элементов, а вот с capacity дела обстоят чуточку сложнее.
    Как Вы, думаю знаете, амортизационная асимптотика вставки элемента в вектор равна O(1). Это достигается благодаря "разрастанию" capacity вдвое каждый раз, когда размер массива переваливает за его вместимость. Структура ищет в памяти блок, размер которого равен 2 * capacity и объявляет его занятым, после чего перемещает всю информацию туда. Поскольку массив хранится на непрерывном участке памяти, то к нему вполне применима адресная арифметика, то есть расстояние от первого элемента вектора до i-ого равно sizeof(datatype) * i. Именно благодаря этому доступ к произвольному элементу осуществляется за константное время.

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

  • Как в С++ получить все возможные двоичные числа определенной длинны?

    @Irval
    Наиболее оптимальный вариант без использования массивов:
    std::string get_binary(int x, int n) {
    string s = "";
    for (int i = n - 1; i >= 0; --i) {
        s.push_back('0' + ((x >> i) & 1));
    }
    return s;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < (1LL << n); ++i) {
        cout << get_binary(i, n) << endl;
    }
}

    С использованием массивов:
    int main() {
    int n;
    cin >> n;
    vector<vector<bool>> arr(1LL << n, vector<bool>(n, 0)); // vector<bool> для чуть большей оптимизации использования памяти
    for (int i = 0; i < n; ++i) {
        bool curr = false;
        int frequency = 1LL << i;
        int j = 0;
        while (j < arr.size()) {
            for (int k = 0; k < frequency; ++k, ++j) {
                arr[j][i] = curr;
            }
            curr = !curr;
        }
    }

    for (int i = 0; i < arr.size(); ++i) {
        for (int j = n - 1; j >= 0; --j) {
            cout << (arr[i][j] ? '1' : '0');
        }
        cout << endl;
    }
}

    Вывод:
    63f916297258a397716968.png
    Ответ написан
    Комментировать
    Комментировать