What is the most efficient way to manipulate a 2D dynamic array of std::strings in memory?

I currently use

std::vector<std::vector<std::string> > MyStringArray

But I h开发者_如何学Cave read several comments here on SO that discourage the use of nested vectors on efficiency grounds.

Unforunately I have yet to see examples of alternatives to nested vector for a situation like this.

Here's a simple dynamic 2D array with runtime-configurable column number:

class TwoDArray
{
  size_t NCols;
  std::vector<std::string> data;

public:
  explicit TwoDArray(size_t n) : NCols(n) { }

  std::string & operator()(size_t i, size_t j) { return data[i * NCols + j]; }
  const std::string & operator()(size_t i, size_t j) const { return data[i * NCols + j]; }

  void set_number_of_rows(size_t r) { data.resize(NCols * r); }

  void add_row(const std::vector<std::string> & row)
  {
    assert(row.size() == NCols);
    data.insert(data.end(), row.begin(), row.end());
  }
};

Usage:

TwoDArray arr(5); // five columns per row
arr.set_number_of_rows(20);
arr(0, 3) = "hello";
arr(17,2) = "world";

This is just a completely arbitrary and random example. Your real class would obviously have to contain interface methods that are suitable to what you're doing; or you might decide not to have a wrapping class at all and address the naked vector directly.

The key feature is the two-dimensional accessor operator via (i,j), which replaces the nested vectors' [i][j].

It seems a reasonable design to me, given your stated design goals. Note that you should avoid operations which resize the outer vector; these may result in a deep copy of all the data in the overall structure (this may be mitigated somewhat with a C++0x STL implementation).

The most efficent way is probably to have the strings be contiguous in memory (separated by null terminators), and having contiguous array of references to each string, and another contiguous array of references to each array.

This is to maintain locality and help use the cache effectively, but it really ultimately depends on how you access the data.