Использование std :: sort для сортировки Matrix

Question

Есть ли способ сортировки матричных элементов с помощью функции сортировки из std?

//Using this matrix
vector<vector<string>> mat;

Например, если у вас есть

5 2 1
0 0 2
1 4 3

Результат будет

0 0 1
1 2 2
3 4 5

Answer 1

Вы можете отсортировать вложенные векторы без дополнительного копирования данных, создав собственный класс матрицы-оболочки и определив свой собственный итератор:

#include <algorithm>
#include <iterator>
#include <string>
#include <vector>

class MyMatrix {
 public:
  using DataStore = std::vector<std::vector<std::string> >;

  // Note: Make sure MyMatrix DO NOT out-live its `data` argument!
  MyMatrix(DataStore& data) : data_(data) {
    // Check that
    //  1. data.size() > 0;
    //  2. data[i].size() > 0 and same for all valid i.
  }

  class Iterator : public std::iterator<std::random_access_iterator_tag,
                                        std::string, int> {
   public:
    Iterator(DataStore& data) : data_(&data), index_(0) {}
    Iterator(DataStore& data, int index) : data_(&data), index_(index) {}
    Iterator(const Iterator& it) : data_(it.data_), index_(it.index_) {}

    Iterator& operator=(const Iterator& it) {
      data_ = it.data_;
      index_ = it.index_;
    }
    operator bool() const {
      return index_ >= 0 && index_ < data_->size() * (*data_)[0].size();
    }

    bool operator==(const Iterator& it) const {
      return data_ == it.data_ && index_ == it.index_;
    }
    bool operator!=(const Iterator& it) const {
      return data_ != it.data_ || index_ != it.index_;
    }

    Iterator& operator++() { ++index_; return *this; }
    Iterator& operator--() { --index_; return *this; }
    Iterator operator++(int) { return Iterator(*data_, index_++); }
    Iterator operator--(int) { return Iterator(*data_, index_--); }

    Iterator& operator+=(int offs) { index_ += offs; return *this; }
    Iterator& operator-=(int offs) { index_ -= offs; return *this; }
    Iterator operator+(int offs) { return Iterator(*data_, index_ + offs); }
    Iterator operator-(int offs) { return Iterator(*data_, index_ - offs); }
    int operator-(const Iterator& it) { return index_ - it.index_; }

    std::string& operator*() {
      return (*data_)[index_ / data_->size()][index_ % (*data_)[0].size()];
    }
    const std::string& operator*() const { return operator*(); }

   private:
    DataStore* data_;
    int index_;
  }; // class Iterator

  Iterator iterator() { return Iterator(data_); }
  Iterator begin() { return Iterator(data_, 0); }
  Iterator end() { return Iterator(data_, data_.size() * data_[0].size()); }

 private:
  DataStore& data_;
};  // class MyMatrix

Тогда sort можно применить к MyMatrix следующим образом:

#include <iostream>

int main()
{
  std::vector<std::vector<std::string> > store = {
    { "5", "2", "1" },
    { "0", "0", "2" },
    { "1", "4", "3" }
  };

  MyMatrix matrix(store);

  for (const auto& row : store) {
    for (const auto& item : row) { std::cout << item <<' '; }
    std::cout <<'\n';
  }
  std::cout <<'\n';

  std::sort(matrix.begin(), matrix.end());

  for (const auto& row : store) {
    for (const auto& item : row) { std::cout << item <<' '; }
    std::cout <<'\n';
  }
  std::cout <<'\n';
}

Запуск приведенного выше кода приведет к следующему выводу:

5 2 1 
0 0 2 
1 4 3 

0 0 1 
1 2 2 
3 4 5 

Answer 2

Для хранения матрицы вложенность std::vector - не лучшее решение.Поскольку любая строка управляет своим собственным размером, нет уникального размера столбца, изначально присваиваемого классом матрицы.

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

Одним из решений (с наименьшими усилиями по реализации) было бы

1. для копирования матрицы (std::vector<std::vector<std::string> >) во временный тип std::vector<std::string>
2. применить std::sort() к этому временному
3. назначить отсортированный вектор матрице снова.

Учитывая, что перемещение элементов может быть дорогим, альтернативой может быть

1. для построения вектора индексной пары
2. std::sort() с помощью специального функтора less (который учитывает матричные элементы).

Впоследствии вектор индексной пары можетиспользоваться для доступа к исходным элементам матрицы в отсортированном порядке.

Последнее показано в моем примере кода:

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

typedef std::vector<std::string> Row;
typedef std::vector<Row> Matrix;
typedef std::pair<size_t, size_t> IndexPair;

struct LessMatrix {
  const Matrix &mat;
  LessMatrix(const Matrix &mat): mat(mat) { }
  bool operator()(const IndexPair &i1, const IndexPair &i2)
  {
    return mat[i1.first][i1.second] < mat[i2.first][i2.second];
  }
};

std::ostream& operator<<(std::ostream &out, const Matrix &mat)
{
  for (const Row row : mat) {
    for (const std::string elem : row) out << ' ' << elem;
    out << '\n';
  }
  return out;
}

int main()
{
  Matrix mat = {
    { "5", "2", "1" },
    { "0", "0", "2" },
    { "1", "4", "3" }
  };
  // print input
  std::cout << "Input:\n" << mat << '\n';
  // indexify matrix
  std::vector<IndexPair> indices;
  for (size_t i = 0, n = mat.size(); i < n; ++i) {
    const std::vector<std::string> &row = mat[i];
    for (size_t j = 0, m = row.size(); j < m; ++j) {
      indices.push_back(std::make_pair(i, j));
    }
  }
  // sort matrix
  LessMatrix less(mat);
  std::sort(indices.begin(), indices.end(), less);
  // print output
  Matrix matOut;
  { size_t i = 0; const size_t nCols = 3;
    for (const IndexPair &index : indices) {
      if (i % nCols == 0) matOut.push_back(Row());
      matOut.back().push_back(mat[index.first][index.second]);
      ++i;
    }
  }
  std::cout << "Output:\n" << matOut << '\n';
  // done
  return 0;
}

Вывод:

Input:
 5 2 1
 0 0 2
 1 4 3

Output:
 0 0 1
 1 2 2
 3 4 5

Демонстрация жизни на колиру

---

ОП жаловался на создание отдельного вектора индекса.Я подозревал, что пользовательский итератор произвольного доступа может быть заменой (для прямой сортировки матрицы).Должен признать, что раньше этого не делал, но из любопытства я попытался разобраться в этом:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>

typedef std::vector<std::string> Row;
typedef std::vector<Row> Matrix;

struct MatrixIterator {
  typedef size_t difference_type;
  typedef std::string value_type;
  typedef std::string* pointer;
  typedef std::string& reference;
  typedef std::random_access_iterator_tag iterator_category;

  // accessed matrix
  Matrix &mat;
  // index of row, index of column
  size_t i, j;

  MatrixIterator(Matrix &mat, size_t i = 0, size_t j = 0): mat(mat), i(i), j(j) { }

  MatrixIterator& operator =(const MatrixIterator &iter)
  {
    assert(&mat == &iter.mat);
    i = iter.i; j = iter.j;
    return *this;
  }

  size_t nCols() const { return mat.front().size(); }

  std::string& operator *() { return mat[i][j]; }
  const std::string& operator *() const { return mat[i][j]; }

  MatrixIterator& operator ++() { return *this += 1; }
  MatrixIterator operator ++(int) { MatrixIterator iter(*this); ++*this; return iter; }

  MatrixIterator& operator --() { return *this -= 1; }
  MatrixIterator operator --(int) { MatrixIterator iter(*this); --*this; return iter; }

  MatrixIterator& operator += (size_t n)
  {
    j += i * nCols() + n; i = j / nCols(); j %= nCols(); return *this;
  }

  MatrixIterator operator + (size_t n) const
  {
    MatrixIterator iter(*this); iter += n; return iter;
  }
  friend MatrixIterator operator + (size_t n, const MatrixIterator &iter)
  {
    MatrixIterator iter2(iter); iter2 += n; return iter2;
  }

  MatrixIterator& operator -= (size_t n)
  {
    j += i * nCols() - n; i = j / nCols(); j %= nCols();
    return *this;
  }

  MatrixIterator operator - (size_t n) const
  {
    MatrixIterator iter(*this); iter -= n; return iter;
  }
  size_t operator - (const MatrixIterator &iter) const
  {
    return (i * nCols() + j) - (iter.i * iter.nCols() + iter.j);
  }

  std::string& operator[](size_t i) { return mat[i / nCols()][i % nCols()]; }
  const std::string& operator[](size_t i) const { return mat[i / nCols()][i % nCols()]; }

  bool operator == (const MatrixIterator &iter) const
  {
    return i == iter.i && j == iter.j;
  }
  bool operator != (const MatrixIterator &iter) const { return !(*this == iter); }

  bool operator < (const MatrixIterator &iter) const
  {
    return i * nCols() + j < iter.i * iter.nCols() + iter.j;
  }
  bool operator > (const MatrixIterator &iter) const { return iter < *this; }
  bool operator <= (const MatrixIterator &iter) const { return !(iter > *this); }
  bool operator >= (const MatrixIterator &iter) const { return !(*this < iter); }
};

MatrixIterator begin(Matrix &mat) { return MatrixIterator(mat, 0, 0); }
MatrixIterator end(Matrix &mat) { return MatrixIterator(mat, mat.size(), 0); }

std::ostream& operator<<(std::ostream &out, const Matrix &mat)
{
  for (const Row row : mat) {
    for (const std::string elem : row) out << ' ' << elem;
    out << '\n';
  }
  return out;
}

int main()
{
  Matrix mat = {
    { "5", "2", "1" },
    { "0", "0", "2" },
    { "1", "4", "3" }
  };
  // print input
  std::cout << "Input:\n" << mat << '\n';
  // sort matrix
  std::sort(begin(mat), end(mat));
  // print output
  std::cout << "Output:\n" << mat << '\n';
  // done
  return 0;
}

Вывод:

Input:
 5 2 1
 0 0 2
 1 4 3

Output:
 0 0 1
 1 2 2
 3 4 5

Life demo на coliru

Примечания:

Я использовал описания на cppreference.com

• Концепции C ++: RandomAccessIterator
• Концепции C ++: BidirectionalIterator
• Концепции C ++: ForwardIterator
• Концепции C ++: Iterator
• std :: iterator_traits

как "шпаргалка требований" и реализовал все описанное там.Некоторые детали я решил догадаться.(Особенно, что касается typedef s, я не совсем уверен, как сделать их правильно.)