CondensedVector

Класс для хранения разреженного вектора в виде пар индекс-значение. Внутри для хранения данных используется std::vector.

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

Подключение

Поместите копию заголовочного файла CondensedVector.h в папку для заголовочных файлов вашего проекта. Добавьте дерективу include в файл исходного кода:

#include "CondensedVector.h"

Использование

Создание на основе std::vector

Передайте стандартный вектор в конструктор, указав, какие элементы считать "пустыми" и не хранить:

std::vector v = { 1.0, 0.0, 1.5 };
cvn::CondensedVector cv(v, cvn::non_zero);

Функция cvn::non_zero возвращает true для объектов, приводимых к типу int и равных 0. Вместо неё можно передать в конструктор любую функцию, принимающую элемент вектора и возвращающее логическое значение.

Преобразование в std::vector

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

Создание пустого вектора и добавление элементов по одному

cvn::CondensedVector<double> cv;
cv.Put(3, 1.0);
cv.Put(5, 2.0);
std::vector v = { 0.0, 0.0, 0.0, 1.0, 0.0, 2.0 };
std::cout << (v == cv.ToVector());

Доступ к элементам с помощью оператора индексирования

Оператор индексирования [] возвращает ссылку на значение по указанному индексу.

cvn::CondensedVector<double> cv;
cv[3] = 1.0;
cv[5] = 2.0;
std::vector v = { 0.0, 0.0, 0.0, 1.0, 0.0, 2.0 };
std::cout << (v == cv.ToVector());

Метод At так же возвращает ссылку на элемент, но если элемента по указанному индексу не существует, будет выброшено исключение std::out_of_range.

Получение указателя на значение по индексу

Метод GetPointer возвращает указатель на значение элемента или nullptr, если элемента с таким индексом нет.

std::vector v = { 1.0, 0.0, 1.5 };
cvn::CondensedVector cv(v, cvn::non_zero);
v[2] *= 3;
auto* ptr = cv.GetPointer(2);
*(ptr) *= 3;
std::cout << (v == cv.ToVector());

Метод Contains проверяет, есть ли элемент по указанному индексу, и возвращает true или false.

Добавление и удаление последовательных элементов

Метод Insert вставляет заданное количество пустых элементов перед элементом с указанным индексом:

std::vector v = { 1.0, 0.0, 1.5 };
cvn::CondensedVector cv(v, cvn::non_zero);
v.insert(v.begin() + 2, { 0.0, 0.0, 0.0 });
cv.Insert(2, 3);
std::cout << (v == cv.ToVector());

Метод Delete удаляет указанное количество элементов, начиная с заданного:

std::vector v = { 1.0, 0.0, 1.5 };
cvn::CondensedVector cv(v, cvn::non_zero);
v.erase(v.begin() + 1, v.begin() + 3);
cv.Delete(1, 2);
std::cout << (v == cv.ToVector());

Использование итераторов

Методы begin и end возвращают итераторы указывающие на начало и конец внутреннего массива непустых элементов. Каждый элемент представляет собой структуру, содержащую индекс и значение:

struct Element{
	I idx;
	T value;
};

Элемент поддерживает неявное преобразование к типу значения. Это позволяет с некоторыми ограничениями пользоваться функциями стандартной библиотеки, работающими с итераторами, например:

std::vector v = { 1.5, 0.0, 1.0 };
cvn::CondensedVector cv(v, cvn::non_zero);
std::cout << *std::max_element(cv.begin(), cv.end()) << std::endl;
std::cout << std::accumulate(cv.begin(), cv.end(), 0.0) << std::endl;