diff --git a/compiler/cpp/src/generate/t_cpp_generator.cc b/compiler/cpp/src/generate/t_cpp_generator.cc
index 00c813e..67a4bd4 100644
--- a/compiler/cpp/src/generate/t_cpp_generator.cc
+++ b/compiler/cpp/src/generate/t_cpp_generator.cc
@@ -870,7 +870,7 @@
     // T_STOP type, so we use the global void type, and special case it when
     // generating its typespec.
 
-    const vector<t_field*>& members = ((t_struct*)ttype)->get_members();
+    const vector<t_field*>& members = ((t_struct*)ttype)->get_sorted_members();
     vector<t_field*>::const_iterator m_iter;
     for (m_iter = members.begin(); m_iter != members.end(); ++m_iter) {
       generate_local_reflection(out, (**m_iter).get_type(), is_definition);
@@ -1112,7 +1112,7 @@
                                              t_struct* tstruct,
                                              bool pointers) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) <<
@@ -1174,7 +1174,7 @@
                                                     t_struct* tstruct,
                                                     bool pointers) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) <<
diff --git a/compiler/cpp/src/generate/t_csharp_generator.cc b/compiler/cpp/src/generate/t_csharp_generator.cc
index e6eff76..5a910ea 100644
--- a/compiler/cpp/src/generate/t_csharp_generator.cc
+++ b/compiler/cpp/src/generate/t_csharp_generator.cc
@@ -565,7 +565,7 @@
   indent_up();
 
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) <<
@@ -625,7 +625,7 @@
   indent_up();
 
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) <<
diff --git a/compiler/cpp/src/generate/t_hs_generator.cc b/compiler/cpp/src/generate/t_hs_generator.cc
index ee17839..c8fda77 100644
--- a/compiler/cpp/src/generate/t_hs_generator.cc
+++ b/compiler/cpp/src/generate/t_hs_generator.cc
@@ -571,7 +571,7 @@
 void t_hs_generator::generate_hs_struct_writer(ofstream& out,
                                                t_struct* tstruct) {
   string name = type_name(tstruct);
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
   string str = tmp("_str");
   string f = tmp("_f");
diff --git a/compiler/cpp/src/generate/t_java_generator.cc b/compiler/cpp/src/generate/t_java_generator.cc
index f709528..3ec816f 100644
--- a/compiler/cpp/src/generate/t_java_generator.cc
+++ b/compiler/cpp/src/generate/t_java_generator.cc
@@ -1081,7 +1081,7 @@
   indent_up();
 
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   // performs various checks (e.g. check that all required fields are set)
@@ -1146,7 +1146,7 @@
   indent_up();
 
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) << "oprot.writeStructBegin(STRUCT_DESC);" << endl;
diff --git a/compiler/cpp/src/generate/t_ocaml_generator.cc b/compiler/cpp/src/generate/t_ocaml_generator.cc
index 68d2c35..0405a04 100644
--- a/compiler/cpp/src/generate/t_ocaml_generator.cc
+++ b/compiler/cpp/src/generate/t_ocaml_generator.cc
@@ -670,7 +670,7 @@
 void t_ocaml_generator::generate_ocaml_struct_writer(ofstream& out,
                                                t_struct* tstruct) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
   string str = tmp("_str");
   string f = tmp("_f");
diff --git a/compiler/cpp/src/generate/t_perl_generator.cc b/compiler/cpp/src/generate/t_perl_generator.cc
index 9fbb92f..ca3210a 100644
--- a/compiler/cpp/src/generate/t_perl_generator.cc
+++ b/compiler/cpp/src/generate/t_perl_generator.cc
@@ -630,7 +630,7 @@
 void t_perl_generator::generate_perl_struct_writer(ofstream& out,
                                                    t_struct* tstruct) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   out << "sub write {" << endl;
diff --git a/compiler/cpp/src/generate/t_php_generator.cc b/compiler/cpp/src/generate/t_php_generator.cc
index fcd00b4..436a632 100644
--- a/compiler/cpp/src/generate/t_php_generator.cc
+++ b/compiler/cpp/src/generate/t_php_generator.cc
@@ -811,7 +811,7 @@
 void t_php_generator::generate_php_struct_writer(ofstream& out,
                                                  t_struct* tstruct) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   if (binary_inline_) {
diff --git a/compiler/cpp/src/generate/t_py_generator.cc b/compiler/cpp/src/generate/t_py_generator.cc
index d63fec7..5db7f8b 100644
--- a/compiler/cpp/src/generate/t_py_generator.cc
+++ b/compiler/cpp/src/generate/t_py_generator.cc
@@ -521,19 +521,6 @@
 }
 
 /**
- * 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.
- * Unfortunately, we cannot declare it within the function.  Boo!
- * http://www.open-std.org/jtc1/sc22/open/n2356/ (paragraph 9).
- */
-struct FieldKeyCompare {
-  bool operator()(t_field const * const & a, t_field const * const & b) {
-    return a->get_key() < b->get_key();
-  }
-};
-
-/**
  * Generates a struct definition for a thrift data type.
  *
  * @param tstruct The struct definition
@@ -545,8 +532,6 @@
 
   const vector<t_field*>& members = tstruct->get_members();
   vector<t_field*>::const_iterator m_iter;
-  vector<t_field*> sorted_members(members);
-  std::sort(sorted_members.begin(), sorted_members.end(), FieldKeyCompare());
 
   out <<
     "class " << tstruct->get_name();
@@ -586,12 +571,12 @@
   // for structures with no members.
   // TODO(dreiss): Test encoding of structs where some inner structs
   // don't have thrift_spec.
-  if (sorted_members.empty() || (sorted_members[0]->get_key() >= 0)) {
+  if (members.empty() || (members[0]->get_key() >= 0)) {
     indent(out) << "thrift_spec = (" << endl;
     indent_up();
 
     int sorted_keys_pos = 0;
-    for (m_iter = sorted_members.begin(); m_iter != sorted_members.end(); ++m_iter) {
+    for (m_iter = members.begin(); m_iter != members.end(); ++m_iter) {
 
       for (; sorted_keys_pos != (*m_iter)->get_key(); sorted_keys_pos++) {
         indent(out) << "None, # " << sorted_keys_pos << endl;
@@ -772,7 +757,7 @@
 void t_py_generator::generate_py_struct_writer(ofstream& out,
                                                t_struct* tstruct) {
   string name = tstruct->get_name();
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator f_iter;
 
   indent(out) <<
diff --git a/compiler/cpp/src/generate/t_st_generator.cc b/compiler/cpp/src/generate/t_st_generator.cc
index db01165..3600a3b 100644
--- a/compiler/cpp/src/generate/t_st_generator.cc
+++ b/compiler/cpp/src/generate/t_st_generator.cc
@@ -693,7 +693,7 @@
 
 string t_st_generator::struct_writer(t_struct *tstruct, string sname) {
   std::ostringstream out;
-  const vector<t_field*>& fields = tstruct->get_members();
+  const vector<t_field*>& fields = tstruct->get_sorted_members();
   vector<t_field*>::const_iterator fld_iter;
 
   out << "[oprot writeStructBegin: " <<
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_;
diff --git a/compiler/cpp/src/thrifty.yy b/compiler/cpp/src/thrifty.yy
index 2c16ca0..bf5408e 100644
--- a/compiler/cpp/src/thrifty.yy
+++ b/compiler/cpp/src/thrifty.yy
@@ -830,11 +830,10 @@
     {
       pdebug("FieldList -> FieldList , Field");
       $$ = $1;
-      if (!($$->validate_field($2))) {
+      if (!($$->append($2))) {
         yyerror("Field identifier %d for \"%s\" has already been used", $2->get_key(), $2->get_name().c_str());
         exit(1);
       }
-      $$->append($2);
     }
 |
     {
diff --git a/test/DebugProtoTest.thrift b/test/DebugProtoTest.thrift
index 12c4613..d3d2580 100644
--- a/test/DebugProtoTest.thrift
+++ b/test/DebugProtoTest.thrift
@@ -240,3 +240,14 @@
   4: map<list<i32>,set<map<i32,string>>> b4;
 }
 
+
+struct ReverseOrderStruct {
+  4: string first;
+  3: i16 second;
+  2: i32 third;
+  1: i64 fourth;
+}
+
+service ReverseOrderService {
+  void myMethod(4: string first, 3: i16 second, 2: i32 third, 1: i64 fourth);
+}
\ No newline at end of file