• Почему доступ к элементам 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
    Ответ написан
    Комментировать
  • Как Просмотреть запись ВК через API?

    @Irval
    Тот же вопрос. Натыкался в интернете на скрытый метод stats.viewPosts, но реализовать его не получилось
    Ответ написан
    Комментировать