Một cách thích hợp để tạo ma trận trong C++

Question

Tôi muốn tạo ma trận kề cho biểu đồ. Vì tôi đọc nó là không an toàn để sử dụng mảng của các hình thức matrix[x][y] bởi vì họ không kiểm tra phạm vi, tôi quyết định sử dụng lớp mẫu vector của stl. Tất cả những gì tôi cần lưu trữ trong ma trận là các giá trị boolean. Vì vậy, câu hỏi của tôi là, nếu sử dụng std::vector<std::vector<bool>* >* sản xuất quá nhiều chi phí hoặc nếu có một cách đơn giản hơn cho một ma trận và làm thế nào tôi có thể khởi tạo nó đúng cách.

EDIT: Cảm ơn rất nhiều câu trả lời nhanh. Tôi chỉ nhận ra rằng, tất nhiên tôi không cần bất kỳ con trỏ nào. Kích thước của ma trận sẽ được khởi tạo ngay từ đầu và sẽ không thay đổi cho đến khi kết thúc chương trình. Nó là cho một dự án trường học, vì vậy nó sẽ là tốt nếu tôi viết "đẹp" mã, mặc dù hiệu suất kỹ thuật không phải là quá quan trọng. Sử dụng STL là tốt. Sử dụng một cái gì đó như tăng, có lẽ không được đánh giá cao.

Answer 1

Cân nhắc xem biểu đồ/ma trận của bạn lớn đến mức nào, hiệu suất có quan trọng không? Biểu đồ có tĩnh hay có thể phát triển theo thời gian, ví dụ: bằng cách thêm các cạnh mới?

Answer 2

Lưu ý rằng bạn cũng có thể sử dụng boost.ublas để tạo ma trận và thao tác và cũng boost.graph để đại diện và thao tác đồ thị trong một số cách khác nhau, cũng như sử dụng các thuật toán trên họ, vv

Sửa: Dù sao, làm một phiên bản tầm kiểm tra của một vector cho mục đích của bạn không phải là một điều khó khăn:

template <typename T> 
class BoundsMatrix 
{ 
     std::vector<T> inner_; 
     unsigned int dimx_, dimy_; 

public: 
     BoundsMatrix (unsigned int dimx, unsigned int dimy) 
       : dimx_ (dimx), dimy_ (dimy) 
     { 
       inner_.resize (dimx_*dimy_); 
     } 

     T& operator()(unsigned int x, unsigned int y) 
     { 
       if (x >= dimx_ || y>= dimy_) 
         throw 0; // ouch 
       return inner_[dimx_*y + x]; 
     } 
}; 

Lưu ý rằng bạn cũng sẽ cần phải thêm phiên bản const của các nhà khai thác, và/hoặc lặp, và việc sử dụng kỳ lạ của ngoại lệ, nhưng bạn có ý tưởng.

Answer 3

Tâm trí bạn std::vector cũng không thực hiện kiểm tra phạm vi.

Answer 4

Điều tôi sẽ làm là tạo lớp của riêng tôi để xử lý ma trận (có thể là mảng [x * y] vì tôi quen với C (và tôi có kiểm tra giới hạn), nhưng bạn có thể sử dụng vectơ hoặc bất kỳ cấu trúc con nào khác trong lớp đó).

Làm cho công cụ của bạn hoạt động đầu tiên rồi lo lắng về tốc độ chạy. Nếu bạn thiết kế lớp đúng cách, bạn có thể kéo ra thực hiện mảng [x * y] của bạn và thay thế nó bằng các vectơ hoặc bitmask hoặc bất kỳ thứ gì bạn muốn mà không thay đổi phần còn lại của mã.

Tôi không hoàn toàn chắc chắn, nhưng tôi điều đó là những gì các lớp học được có nghĩa là cho, khả năng trừu tượng thực hiện cũng ra khỏi tầm nhìn và chỉ cung cấp giao diện :-)

Answer 5

Cách tốt nhất:

Làm cho lớp ma trận của riêng bạn, theo cách đó bạn kiểm soát mọi khía cạnh cuối cùng của nó, bao gồm kiểm tra phạm vi.

ví dụ: Nếu bạn thích ký hiệu "[x] [y]", hãy làm như sau:

class my_matrix { 
    std::vector<std::vector<bool> >m; 
public: 
    my_matrix(unsigned int x, unsigned int y) { 
    m.resize(x, std::vector<bool>(y,false)); 
    } 
    class matrix_row { 
    std::vector<bool>& row; 
    public: 
    matrix_row(std::vector<bool>& r) : row(r) { 
    } 
    bool& operator[](unsigned int y) { 
     return row.at(y); 
    } 
    }; 
    matrix_row& operator[](unsigned int x) { 
    return matrix_row(m.at(x)); 
    } 
}; 
// Example usage 
my_matrix mm(100,100); 
mm[10][10] = true; 

nb. Nếu bạn lập trình như thế này thì C++ cũng an toàn như tất cả các ngôn ngữ "an toàn" khác.

Answer 6

Ngoài tất cả các câu trả lời đã được đăng cho đến thời điểm này, bạn có thể làm tốt để kiểm tra số C++ FAQ Lite. Câu hỏi 13.10 - 13.12 và 16.16 - 16.19 bao gồm một số chủ đề liên quan đến việc cuộn lớp ma trận của riêng bạn. Bạn sẽ thấy một vài cách khác nhau để lưu trữ dữ liệu và đề xuất về cách viết tốt nhất toán tử subscript.

Ngoài ra, nếu biểu đồ của bạn đủ thưa thớt, bạn có thể không cần ma trận chút nào. Bạn có thể sử dụng std::multimap để ánh xạ từng đỉnh cho những điểm mà nó kết nối.

Answer 7

Vectơ chuẩn KHÔNG thực hiện kiểm tra phạm vi theo mặc định.

tức là Toán tử [] không thực hiện kiểm tra phạm vi.

Phương thức tại() tương tự như [] nhưng thực hiện kiểm tra phạm vi.
Nó sẽ ném một ngoại lệ ra ngoài phạm vi.

std::vector::at()
std::vector::operator[]()

ghi chú khác: Tại sao một vector <Pointers>?
Bạn có thể dễ dàng có một vector < Đối tượng >. Bây giờ không cần phải lo lắng về việc quản lý bộ nhớ (tức là rò rỉ).

std::vector<std::vector<bool> > m; 

Lưu ý: vector <bool> bị quá tải và không phải là rất hiệu quả (ví dụ: cấu trúc này đã được tối ưu hóa cho kích thước không tăng tốc độ) (Đó là một cái gì đó mà bây giờ được công nhận là có thể là một sai lầm bởi các ủy ban tiêu chuẩn).

Nếu bạn biết kích thước của ma trận tại thời gian biên dịch, bạn có thể sử dụng std :: bitset?

std::vector<std::bitset<5> > m; 

hoặc nếu nó chạy được định nghĩa sử dụng tăng :: dynamic_bitset

std::vector<boost::dynamic_bitset> m; 

Tất cả những điều trên sẽ cho phép bạn làm:

m[6][3] = true; 

Answer 8

Nếu bạn muốn thực hiện mảng 'C' , nhưng với sự an toàn bổ sung và ngữ nghĩa giống như STL (trình lặp, begin() & end() v.v.), hãy sử dụng boost::array.

Về cơ bản nó là một trình bao bọc khuôn mẫu cho 'C'-mảng với một số NDEBUG biện pháp kiểm tra phạm vi có thể đo được (và cũng có một số std::range_error truy cập ngoại trừ ném).

tôi sử dụng công cụ như

boost::array<boost::array<float,4>,4> m; 

thay vì

float m[4][4]; 

tất cả các thời gian và nó hoạt động tuyệt vời (với typedefs thích hợp để giữ tính cách rườm rà xuống, dù sao).

---

UPDATE: Sau một số cuộc thảo luận trong các ý kiến ​​ở đây việc thực hiện tương đối của boost::array vs boost::multi_array, tôi muốn chỉ ra rằng mã này, biên soạn với g++ -O3 -DNDEBUG trên Debian/Lenny amd64 trên Q9450 với 1333MHz DDR3 RAM mất 3,3 giây cho boost::multi_array so với 0,6 giây cho boost::array.

#include <iostream> 
#include <time.h> 
#include "boost/array.hpp" 
#include "boost/multi_array.hpp" 

using namespace boost; 

enum {N=1024}; 

typedef multi_array<char,3> M; 
typedef array<array<array<char,N>,N>,N> C; 

// Forward declare to avoid being optimised away 
static void clear(M& m); 
static void clear(C& c); 

int main(int,char**) 
{ 
    const clock_t t0=clock(); 

    { 
    M m(extents[N][N][N]); 
    clear(m); 
    } 

    const clock_t t1=clock(); 

    { 
    std::auto_ptr<C> c(new C); 
    clear(*c); 
    } 

    const clock_t t2=clock(); 

    std::cout 
    << "multi_array: " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s\n" 
    << "array  : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s\n"; 

    return 0; 
} 

void clear(M& m) 
{ 
    for (M::index i=0;i<N;i++) 
    for (M::index j=0;j<N;j++) 
     for (M::index k=0;k<N;k++) 
    m[i][j][k]=1; 
} 


void clear(C& c) 
{ 
    for (int i=0;i<N;i++) 
    for (int j=0;j<N;j++) 
     for (int k=0;k<N;k++) 
    c[i][j][k]=1; 
} 

Answer 9

Có thể, không liên quan vì đây là câu hỏi cũ, nhưng bạn có thể sử dụng thư viện Armadillo, cung cấp nhiều loại dữ liệu và chức năng đại số tuyến tính.

Dưới đây là một ví dụ cho vấn đề cụ thể của bạn:

// In C++11 
Mat<bool> matrix = { 
    { true, true}, 
    { false, false}, 
}; 

// In C++98 
Mat<bool> matrix; 
matrix << true << true << endr 
     << false << false << endr; 

Answer 10

cách yêu thích của tôi để lưu trữ đồ thị là vector<set<int>>; n phần tử trong vector (các nút 0..n-1),> = 0 phần tử trong mỗi bộ (cạnh). Chỉ cần đừng quên thêm một bản sao ngược của mỗi cạnh hai hướng.