# Programming Finite Element Methods in C++

I am trying to develop a library for finite element methods in C++ and for that I am looking at the data structures for meshes. Based on what I've read up on fenics and deal.ii, the general understanding seems to be that a basic mesh class should have the following members:

1. Cells, Faces, vertices.
2. Connectivity relationships (What are the neighbors of a given cell, common faces between cells, vertices of a given cell, boundary indicators for cells, faces and vertices)
3. Cell iterators

These are my questions:

1. What is the best way to store cells of a mesh. I think an STL vector would suffice. Is this the popular option? I have also read that linked lists have been used for cells but I cannot see the advantage of linked lists over vectors in this case.
2. Again, for the connectivity relationships, STL maps seem to be the best method for me. Any comments on this?
3. Does the same data structure work for both triangular and quadrilateral meshes. I think it should but I am not sure if I am missing anything basic here?
4. Are there any more connectivity relationships to be kept in mind?
5. Are there any good references for programming a finite element library?

Thank you.

• I guess all of your questions may be answered checking source code for the libraries you mentioned. What features are missing in dealii or fenics? I personally have experience only on dealii and they have quite an active community, you really want to work all alone? – Nicola Cavallini Oct 29 '14 at 9:52
• Thank you Nicola. I am working on this project out of interest in building software libraries. I am assuming that dealii and fenics use advanced/efficient programming concepts for the questions I mentioned above and I wanted to know if vectors and maps are good enough for basic finite element libraries. – gk1 Oct 29 '14 at 10:02

In deal.II, we basically only use vectors. Maps are too slow and scatter data all around memory, so we typically don't use them if the keys are integers and within a given range. For example, for the connectivity between cells, you can do arrays (STL vectors) in which you store neighbor indices and so that neighbor indices $4i\ldots 4i+3$ correspond to cell $i$ (in 2d, because there are 4 neighbors per cell). This way you can do direct array lookup, rather than walking through the tree in STL maps.
• Would you recommend vector of int or vector of data structures? i.e. std::vector<int> vs std::vector<Vertex&>. Is this relevant to cache misses? – user1800 Feb 21 '16 at 3:54