diff --git a/compiler/cpp/src/parse/t_field.h b/compiler/cpp/src/parse/t_field.h
index 51cfcb0..67a2125 100644
--- a/compiler/cpp/src/parse/t_field.h
+++ b/compiler/cpp/src/parse/t_field.h
@@ -122,6 +122,18 @@
       type_->get_fingerprint_material();
   }
 
+  /**
+   * Comparator to sort fields in ascending order by key.
+   * Make this a functor instead of a function to help GCC inline it.
+   * The arguments are (const) references to const pointers to const t_fields.
+   */
+  struct key_compare {
+    bool operator()(t_field const * const & a, t_field const * const & b) {
+      return a->get_key() < b->get_key();
+    }
+  };
+
+
  private:
   t_type* type_;
   std::string name_;
diff --git a/compiler/cpp/src/parse/t_struct.h b/compiler/cpp/src/parse/t_struct.h
index a18b131..7980f80 100644
--- a/compiler/cpp/src/parse/t_struct.h
+++ b/compiler/cpp/src/parse/t_struct.h
@@ -20,7 +20,9 @@
 #ifndef T_STRUCT_H
 #define T_STRUCT_H
 
+#include <algorithm>
 #include <vector>
+#include <utility>
 #include <string>
 
 #include "t_type.h"
@@ -36,6 +38,8 @@
  */
 class t_struct : public t_type {
  public:
+  typedef std::vector<t_field*> members_type;
+
   t_struct(t_program* program) :
     t_type(program),
     is_xception_(false),
@@ -62,14 +66,28 @@
     return xsd_all_;
   }
 
-  void append(t_field* elem) {
+  bool append(t_field* elem) {
     members_.push_back(elem);
+
+    typedef members_type::iterator iter_type;
+    std::pair<iter_type, iter_type> bounds = std::equal_range(
+            members_in_id_order_.begin(), members_in_id_order_.end(), elem, t_field::key_compare()
+        );
+    if (bounds.first != bounds.second) {
+      return false;
+    }
+    members_in_id_order_.insert(bounds.second, elem);
+    return true;
   }
 
-  const std::vector<t_field*>& get_members() {
+  const members_type& get_members() {
     return members_;
   }
 
+  const members_type& get_sorted_members() {
+    return members_in_id_order_;
+  }
+
   bool is_struct() const {
     return !is_xception_;
   }
@@ -80,8 +98,8 @@
 
   virtual std::string get_fingerprint_material() const {
     std::string rv = "{";
-    std::vector<t_field*>::const_iterator m_iter;
-    for (m_iter = members_.begin(); m_iter != members_.end(); ++m_iter) {
+    members_type::const_iterator m_iter;
+    for (m_iter = members_in_id_order_.begin(); m_iter != members_in_id_order_.end(); ++m_iter) {
       rv += (*m_iter)->get_fingerprint_material();
       rv += ";";
     }
@@ -91,26 +109,16 @@
 
   virtual void generate_fingerprint() {
     t_type::generate_fingerprint();
-    std::vector<t_field*>::const_iterator m_iter;
-    for (m_iter = members_.begin(); m_iter != members_.end(); ++m_iter) {
+    members_type::const_iterator m_iter;
+    for (m_iter = members_in_id_order_.begin(); m_iter != members_in_id_order_.end(); ++m_iter) {
       (*m_iter)->get_type()->generate_fingerprint();
     }
   }
 
-  bool validate_field(t_field* field) {
-    int key = field->get_key();
-    std::vector<t_field*>::const_iterator m_iter;
-    for (m_iter = members_.begin(); m_iter != members_.end(); ++m_iter) {
-      if ((*m_iter)->get_key() == key) {
-        return false;
-      }
-    }
-    return true;
-  }
-
  private:
 
-  std::vector<t_field*> members_;
+  members_type members_;
+  members_type members_in_id_order_;
   bool is_xception_;
 
   bool xsd_all_;