C ++: присвоение значений непостоянным индексам в векторах?

Question

Если я хочу объявить вектор неизвестного размера, назначьте значения для индекса 5, индекса 10, индекса 1, индекса 100 в указанном порядке. Это легко сделать в векторе?

Кажется, нет простого пути. Потому что, если я инициализирую вектор без размера, то я не могу получить доступ к индексу 5 без предварительного выделения памяти для него с помощью resize () или пяти push_back (). Но изменение размера очищает ранее сохраненные значения в векторе. Я могу сконструировать вектор, задав для него размер, но я не знаю, насколько большим должен быть вектор.

Так как мне не нужно объявлять фиксированный размер и по-прежнему обращаться к непостоянным индексам в векторе?

(я сомневаюсь, что для этой задачи массив будет проще).

Answer 1

Разве std :: map между целочисленными ключами и значениями не будет простым решением здесь? Для векторов потребуется непрерывное распределение памяти, поэтому, если вы используете только случайный индекс, вы «потратите» много памяти.

Answer 2

Изменение размера не очищает вектор. Вы можете легко сделать что-то вроде:

  if (v.size() <= n)
      v.resize(n+1);
  v[n] = 42;

Это сохранит все значения в векторе и добавит достаточно инициализированных значений по умолчанию, чтобы индекс n стал доступен.

Тем не менее, если вам не нужны все индексы или непрерывная память, вы можете рассмотреть другую структуру данных.

Answer 3

resize() не очищает ранее сохраненные значения в векторе.
см. эту документацию

Я бы также сказал, что если это то, что вам нужно сделать, то вполне возможно, что vector не может быть контейнером для вас. Вы рассматривали возможность использования map возможно?

Answer 4

Структуры данных, которые не содержат непрерывный набор значений, известны как разреженные или сжатые структуры данных. Кажется, это то, что вы ищете.

Если это так, вы хотите разреженный вектор . Один из них реализован в boost, см. текст ссылки

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

Создайте шаблонный класс, который содержит вектор и перенаправляет все векторные методы в него. Измените ваш оператор [], чтобы изменить размер вектора, если индекс выходит за границы.

// A vector that resizes on dereference if the index is out of bounds.
template<typename T>
struct resize_vector
{
    typedef typename std::vector<T>::size_type size_type;
    // ... Repeat for iterator/value_type typedefs etc

    size_type size() const { return m_impl.size() }
    // ... Repeat for all other vector methods you want

    value_type& operator[](size_type i)
    {
        if (i >= size())
            resize(i + 1); // Resize
        return m_impl[i];
    }
    // You may want a const overload of operator[] that throws
    // instead of resizing (or make m_impl mutable, but thats ugly).

private:
    std::vector<T> m_impl;
};

Как отмечено в других ответах, элементы не очищаются при изменении размера вектора. Вместо этого, когда новые элементы добавляются изменением размера, вызывается их конструктор по умолчанию. Поэтому при использовании этого класса вам необходимо знать, что operator[] может вернуть вам ссылку на созданный объект по умолчанию. Поэтому ваш конструктор по умолчанию для <T> должен установить для объекта разумное значение для этой цели. Например, вы можете использовать значение Sentinel, если вам нужно знать, было ли элементу ранее присвоено значение.

Предложение использовать std::map<size_t, T> также имеет смысл в качестве решения, если вы не возражаете против использования дополнительной памяти, несмежного хранения элементов и поиска O (logN), а не O (1) для вектора. Все это сводится к тому, хотите ли вы разреженное представление или автоматическое изменение размера; надеюсь, что этот ответ охватывает оба.