Need help to understand this STL code.

First of all, I must say I'm just starting to use STL, in fact I started a day ago to get into it. Now, I'm having some problems to understand some STL code someone wrote. Here is the header code:

Code:

---

class varrays_normalizer
{
public:
        varrays_normalizer(gl_mesh & Mesh);

        size_t Normalize();

private:
        typedef unsigned int index;
        typedef std::vector<index> indices;
        typedef std::vector<float> varray;

        class cmp_lt_vertex
        {
        public:
                cmp_lt_vertex(const varray & Vertex, const varray & Normal, const varray & TexCoord);
                bool operator () (const index & a, const index & b) const;

        private:
                const varray & m_Vertex;
                const varray & m_Normal;
                const varray & m_TexCoord;
        };

        gl_mesh & m_Mesh;
};

inline varrays_normalizer::varrays_normalizer(gl_mesh & Mesh) : m_Mesh(Mesh) { }


inline varrays_normalizer::cmp_lt_vertex::cmp_lt_vertex(const varray & Vertex, const varray & Normal, const varray & TexCoord)
        : m_Vertex(Vertex), m_Normal(Normal), m_TexCoord(TexCoord) { }

---

And the CPP code is here:

Code:

---

size_t varrays_normalizer::Normalize()
{
        typedef std::vector<index *> indices_pointers;
        typedef std::map<index, indices_pointers, cmp_lt_vertex> vertex_map;
        typedef vertex_map::const_iterator vertex_map_const_iterator;

        if (m_Mesh.m_VArrays[gl_mesh::vertex].empty() || m_Mesh.m_VArrays[gl_mesh::normal].empty() || m_Mesh.m_VArrays[gl_mesh::texture_coord0].empty())
                throw ("Normalizer: one of the vertex arrays is empty (need vertex/normal/texcoord0)");


        cmp_lt_vertex CmpFct(
                m_Mesh.m_VArrays[gl_mesh::vertex],
                m_Mesh.m_VArrays[gl_mesh::normal],
                m_Mesh.m_VArrays[gl_mesh::texture_coord0]
        );

        vertex_map VertexMap(CmpFct);


        for (size_t i = 0; i < m_Mesh.m_SubMeshes.size(); ++i) {

                const indices & Indices = m_Mesh.m_SubMeshes[i].Indices();

                for (size_t j = 0; j < Indices.size(); ++j)
                        VertexMap[Indices[j]].push_back((index *) &(Indices[j]));
        }

        size_t NewVASize = VertexMap.size();

        varray Vertex;                Vertex.reserve(NewVASize);
        varray Normal;                Normal.reserve(NewVASize);
        varray TexCoord;        TexCoord.reserve(NewVASize);

        varray & OldVertex = m_Mesh.m_VArrays[gl_mesh::vertex];
        varray & OldNormal = m_Mesh.m_VArrays[gl_mesh::normal];
        varray & OldTexCoord = m_Mesh.m_VArrays[gl_mesh::texture_coord0];

        for (vertex_map_const_iterator It = VertexMap.begin(); It != VertexMap.end(); ++It) {

                const index VAPos = (* It).first;
                const indices_pointers & IndicesPtr = (* It).second;
                const index NewIndex = index(Vertex.size() / 3);

                Vertex.push_back(OldVertex[VAPos * 3 + 0]);
                Vertex.push_back(OldVertex[VAPos * 3 + 1]);
                Vertex.push_back(OldVertex[VAPos * 3 + 2]);

                Normal.push_back(OldNormal[VAPos * 3 + 0]);
                Normal.push_back(OldNormal[VAPos * 3 + 1]);
                Normal.push_back(OldNormal[VAPos * 3 + 2]);

                TexCoord.push_back(OldTexCoord[VAPos * 2 + 0]);
                TexCoord.push_back(OldTexCoord[VAPos * 2 + 1]);

                for (indices_pointers::const_iterator IndIt = IndicesPtr.begin(); IndIt != IndicesPtr.end(); ++IndIt)
                        ** IndIt = NewIndex;
        }


        // Replace the old arrays with the new ones
        std::swap(Vertex, OldVertex);
        std::swap(Normal, OldNormal);
        std::swap(TexCoord, OldTexCoord);

        return NewVASize;
}

bool varrays_normalizer::cmp_lt_vertex::operator () (const index & a, const index & b) const {
        // Compare the vertex coords
        if (m_Vertex[a * 3 + 0] < m_Vertex[b * 3 + 0])
                return true;
        else if (m_Vertex[a * 3 + 0] > m_Vertex[b * 3 + 0])
                return false;

        else if (m_Vertex[a * 3 + 1] < m_Vertex[b * 3 + 1])
                return true;
        else if (m_Vertex[a * 3 + 1] > m_Vertex[b * 3 + 1])
                return false;

        else if (m_Vertex[a * 3 + 2] < m_Vertex[b * 3 + 2])
                return true;
        else if (m_Vertex[a * 3 + 2] > m_Vertex[b * 3 + 2])
                return false;

        // Compare the normal vector coords
        if (m_Normal[a * 3 + 0] < m_Normal[b * 3 + 0])
                return true;
        else if (m_Normal[a * 3 + 0] > m_Normal[b * 3 + 0])
                return false;

        else if (m_Normal[a * 3 + 1] < m_Normal[b * 3 + 1])
                return true;
        else if (m_Normal[a * 3 + 1] > m_Normal[b * 3 + 1])
                return false;

        else if (m_Normal[a * 3 + 2] < m_Normal[b * 3 + 2])
                return true;
        else if (m_Normal[a * 3 + 2] > m_Normal[b * 3 + 2])
                return false;

        // Compare the texture coords
        if (m_TexCoord[a * 2 + 0] < m_TexCoord[b * 2 + 0])
                return true;
        else if (m_TexCoord[a * 2 + 0] > m_TexCoord[b * 2 + 0])
                return false;

        else if (m_TexCoord[a * 2 + 1] < m_TexCoord[b * 2 + 1])
                return true;
        else if (m_TexCoord[a * 2 + 1] > m_TexCoord[b * 2 + 1])
                return false;

        return false;
}

---

First of all, I need to explain what's the idea of this code. The idea is to normalize a list of vertices, that means that every single vertex has unique information, if two vertices have the same information, then one is removed. Now with that list of vertex you make triangles, so you have ints which point to what vertices in the list make up that face (or triangle) in the model. This means that for example, if a face is made up by the indices [1 2 3] and another face is made up with the indices [4 5 6], then if 2 and 6 have the same information (vertex position, texture coordinate and normal) then the second face should be [4 5 2]. To normalize the list of vertices also means that all those vertices that don't belong to any face are removed. I hope that helps.
Now, the only thing I understand is that this code is trying to use one of the properties of the STL maps and its the fact that two keys can't be equal. What I don't understand is how is the structure set up, what is the key and the value in the map, what is the purpose of the compare value (I know it gets called three times when the push_back is done). Can anyone help me with this problem?

Thanks in advance.

typedef std::map<index, indices_pointers, cmp_lt_vertex> vertex_map;

The type vertex_map uses the type index as the key and the type indices_pointers as the data. Each element of the map map is actually a pair where the the first value of the pair is the key and the second is the data. Each element of the map is stored in the map in sorted order according to the cmp_lt_vertex function.

INMO, using this example to learn STL maps, or other aspects of STL, is like using Hoefstaders "Goedel, Escher, and Bach" to learn English---it can be done, but only with extreme measures.

Quote:

---

Originally Posted by elad

typedef std::map<index, indices_pointers, cmp_lt_vertex> vertex_map;

The type vertex_map uses the type index as the key and the type indices_pointers as the data. Each element of the map map is actually a pair where the the first value of the pair is the key and the second is the data.

---

Yeah, I realized that, what I don't understand is for example, is the following line:

Code:

---

VertexMap[Indices[j]].push_back((index *) &(Indices[j]));

---

I haven't seen any stl map example that uses the push_back function. I suppose that this line stores Indices[j] as the key, and (index *) &(Indices[j]) as the value, is that right?

Quote:

---

Originally Posted by elad

Each element of the map is stored in the map in sorted order according to the cmp_lt_vertex function.

---

I don't understand this one either. How does the compare function works? I know that it has to return a bool, what does it mean if it returns true and what does it mean when it returns false?

Quote:

---

Originally Posted by elad

INMO, using this example to learn STL maps, or other aspects of STL, is like using Hoefstaders "Goedel, Escher, and Bach" to learn English---it can be done, but only with extreme measures.

---

Yeah, too bad I had to bump into this code to realize I had to learn STL. Anyway I got myself a book(STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library (2nd Edition)) that's helping me a bit, but its not enough.

Thanks a lot for the help.

Quote:

---

Originally Posted by Hulag

Yeah, I realized that, what I don't understand is for example, is the following line:

Code:

---

VertexMap[Indices[j]].push_back((index *) &(Indices[j]));

---

I haven't seen any stl map example that uses the push_back function. I suppose that this line stores Indices[j] as the key, and (index *) &(Indices[j]) as the value, is that right?

---

Wrong. VertexMap[Indices[j]] looks up the element of the map with the key Indices[j]. This element is of the type indices_pointers, which is a typedef for vector<index *>. push_back is then called on this vector.

Quote:

---

I don't understand this one either. How does the compare function works? I know that it has to return a bool, what does it mean if it returns true and what does it mean when it returns false?

---

Depends on the function. This particular functor has "lt" in the name, which I guess means "less than". Thus, if the function returns true then the first argument is "less than" the second, whatever that means.
It's not important what exactly it means, what's important is that it creates a strict weak ordering for the keys.