用扁平内存结构替换嵌套的向量

Question

我有以下类型：

std::vector<std::vector<int>> indicies

内部向量的大小始终为2。问题在于，向量在内存中是非连续的。我希望用连续的东西替换内部向量，以便我可以将压平的数组强制转换：

int *array_a = (int *) &(a[0][0])

如果新类型有[]运算符，那就太好了，这样我就不必改变整个代码了。（如果必要的话），我有以下两种想法：

std::vector<std::array<int, 2>>

或者

std::vector<std::pair<int, int>>

这些在内存中是什么样子？我写了一个小测试：

#include <iostream>
#include <array>
#include <vector>
int main(int argc, char *argv[])
{
    using namespace std;

    vector<array<int, 2>> a(100);

    cout << sizeof(array<int, 2>) << endl;

    for(auto i = 0; i < 10; i++){
        for(auto j = 0; j < 2; j++){
            cout << "a[" << i << "][" << j << "] " 
                <<&(a[i][j]) << endl;
        }
    }
    return 0;
}

这会导致：

8
a[0][0] 0x1b72c20
a[0][1] 0x1b72c24
a[1][0] 0x1b72c28
a[1][1] 0x1b72c2c
a[2][0] 0x1b72c30
a[2][1] 0x1b72c34
a[3][0] 0x1b72c38
a[3][1] 0x1b72c3c
a[4][0] 0x1b72c40
a[4][1] 0x1b72c44
a[5][0] 0x1b72c48
a[5][1] 0x1b72c4c
a[6][0] 0x1b72c50
a[6][1] 0x1b72c54
a[7][0] 0x1b72c58
a[7][1] 0x1b72c5c
a[8][0] 0x1b72c60
a[8][1] 0x1b72c64
a[9][0] 0x1b72c68
a[9][1] 0x1b72c6c

在这种情况下似乎可以工作。这种行为是标准行为还是仅仅是幸运的巧合？有更好的方法来做到这一点吗？

- Stein

---

向量的元素是连续存储的。 - default

我认为问题是： std::pairs和std::arrays是否可能存在填充？仅仅因为std::vector的元素是连续存储的并不足够。 - Wintermute

一个向量的向量不能保证存储元素是连续的。只有对象本身（内部向量作为地址或任何表示正在使用的方式）被连续地存储，但不是每个单独的内部向量数据指针所指向的数据。 - vsoftco

@Wintermute https://dev59.com/GWIk5IYBdhLWcg3wn_f1@Wintermute https://dev59.com/GWIk5IYBdhLWcg3wn_f1的大小是否由标准定义 - user2100815

我不相信你可以依赖这个链接：https://stackoverflow.com/questions/40476058/does-stdvectorsimd-wrapper-have-contiguous-data-in-memory/40476277#40476277 - Galik

Answer 1

一个array<int,2>将会是一个包含int[2]数组的结构体；标准没有直接规定它，但实际上没有其他合理和实用的方法来实现它。

请参见标准中的23.3.7 [array]。我找不到标准中要求sizeof(std::array<char,10>)==1024为false的内容。这将是一种荒谬的QOI（实现质量）；我看过的每个实现都有sizeof(std::array<T,N>) == N*sizeof(T)，其他任何情况我都认为是敌对的。

数组必须是连续的容器，它们是可由最多N个类型可转换为T的参数初始化的聚合体。

标准允许在这样的数组之后进行填充。我知道0个编译器会插入这样的填充。

连续的std::array<int,2>缓冲区不能保证作为int的平坦缓冲区安全访问。事实上，别名规则几乎肯定禁止这种访问作为未定义行为。您甚至不能使用int[3][7]！请参见这里的SO问题和答案，这里，以及这里。

大多数编译器都可以使您描述的内容正常工作，但优化器可能会决定通过int*和array<int,2>*进行访问不能访问同一内存，并生成不合理的结果。这似乎不值得。

符合标准的方法是编写一个数组视图类型（它接受两个指针并形成一个可迭代范围，其中[]被重载）。然后编写一个平坦缓冲区的2D视图，其中较低的维度是运行时或编译时的值。它的[]将返回一个数组视图。

在一个拥有向量的类型中合并2D视图，就可以得到你的2D向量。

唯一的行为差异是当旧的向量代码复制较低的维度（如auto inner=outer[i]）时，它会复制数据，之后它将创建一个视图。

- Yakk - Adam Nevraumont

---

在我看来，允许将由int[2]组成的结构体别名为ints。 - M.M

@MaximEgorushkin，那不是标准。我想知道标准规定在哪里。我敢打赌标准规定T[N]的大小为N*sizeof(T)，但即使如此，我也需要一个引用（编译器是否允许在数组的末尾放置填充？），你之前声称标准要求这样做。其次，标准中的别名规则是严格的；即使没有填充，通过不同类型的指针和引用进行访问也是无法定义的。 - Yakk - Adam Nevraumont

你在回答中的第一句和第三句是错误的，因此我会给你一个负评。我不会再提供任何证据，因为你的断言没有参考资料，这意味着它们可以被无视。 - Maxim Egorushkin

@Yakk 看看 C++ 版本的 sizeof，他们没有费心阐述。 - Maxim Egorushkin

@MaximEgorushkin和其他3个SO答案引用了数组的别名问题，将数组的数组转换为数组是不合法的；包含数组的结构体的别名转换为数组则较少。其中一些答案引用了标准的部分内容。标准没有声明“这是不合法的”，但是将指向X的指针视为指向Y的指针只允许狭窄的方式，并且这不是其中之一。我无法提供“标准从未允许此操作”的引用，除了整个标准外，因为添加到标准的任何段落都可能允许它；您无法引用否定的内容。 - Yakk - Adam Nevraumont

Answer 2

有更好的方法吗？

我最近完成了另一个版本的生命游戏。

游戏板是2D的，向量中有浪费空间。

在我的最新尝试中，我选择尝试使用1D向量来代替2D游戏板。

typedef std::vector<Cell_t*>  GameBoard_t;

然后我创建了一个简单的索引函数，用于提高代码的可读性，当使用行/列时：

inline size_t gbIndx(int row, int col)
  { return ((row * MAXCOL) + col); }

示例：访问第27行，第33列：

Cell_t* cell = gameBoard[ gbIndx(27, 33) ];

现在gameBoard中的所有Cell_t*都被打包成了一个向量，可以按行/列顺序使用gbIndx()轻松访问（初始化、显示等）（向量的定义）。

---

此外，我可以利用简单的索引来进行各种尝试：

void setAliveRandom(const GameBoard_t& gameBoard)
{
   GameBoard_t  myVec(m_gameBoard); // copy cell vector

   time_t seed = std::chrono::system_clock::
        now().time_since_epoch().count();

   // randomize copy's element order
   std::shuffle (myVec.begin(), myVec.end(), std::default_random_engine(seed));

   int count = 0;
   for ( auto it : myVec )
   {  
      if (count & 1)  it->setAlive(); // touch odd elements
      count += 1;
   }
}

我惊讶于在使用时很少需要行/列索引。

- 2785528

---

g++ v6.2告诉我"std::default_random_engine(...)"是实现定义的。现在我使用std::mt19937_64 gen(rd)和std::random_device rd;。 - 2785528

Answer 3

据我所知，std::vector 在内存中是连续的。看一下这些问题：

为什么 std::vector 是连续的？

std::vector 的元素是否保证是连续的？

如果你需要调整内部向量的大小，那么你就不会有整个结构连续，但内部向量仍然是连续的。不过，如果你使用一个向量的向量，你将拥有一个完全连续的结构（我在这里编辑，抱歉我误解了你的问题），这意味着指向你的内部向量的指针也将是连续的。

如果你想实现一个始终连续的结构，从第一个向量的第一个元素到最后一个向量的最后一个元素，你可以将其实现为一个自定义类，该类具有一个 vector<int> 和 elems_per_vector，它指示每个内部向量中的元素数量。

然后，您可以重载operator()，以便访问a(i,j)实际上是访问a.vector[a.elems_per_vector*i+j]。但是，为了插入新元素并使内部向量在它们之间保持恒定的大小，您将不得不进行与内部向量数量相同的插入操作。

- J.Checa

---

一个 std::vector 存储其元素是连续的，但不是局部的。也就是说，在一个向量的向量中，每个内部向量都按顺序存储其元素，但一个内部向量的最后一个元素通常不会与下一个内部向量的第一个元素相邻存储，这就是 OP 所需要的。 - Wintermute

如果您使用一个向量的向量，那么您将拥有一个完全连续的结构。这是错误的。向量的向量确实将内部向量（作为对象）连续存储。然而，每个内部向量在内部存储一个代表其数据的指针。这些指针本身并不保证指向连续的内存区域。 - vsoftco

抱歉，我误解了OP的问题。他似乎希望将所有元素，从第一个向量的第一个元素到最后一个向量的最后一个元素，对齐在内存中。是的，确实，如果您创建一个向量的向量，您将获得一个连续的内存区域，其中包含指向内部向量的指针。此外，我的最后一句话导致了混淆，我想说的是所有您的元素将是连续的，指的是指针本身。我会编辑我的答案以避免混淆。感谢@vsoftco和Wintermute的评论:D - J.Checa