Sorting Out the Relationships Between Pairs of Iterators, Values, and References

  • Krister Åhlander
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3676)


Motivated by a wish to sort an array A while simultaneously permuting another array B, iteration over array pairs (A,B) is considered.

Traditional solutions to this problem require an adaption of either the algorithm or of the data structure. The generic programming approach described in this paper involves the construction of an iterator adaptor: an iterator pair. The different approaches are implemented in C++ and compared with respect to flexibility and performance.

Our design is also compared with another iterator-based design. When examining our solution, we identify the relationship between a reference type and a value type as an independent abstraction. We find that a valid “reference type” to a value type T is not necessarily T&. The reference pair developed in this paper serves as an example of a reference type which refers to a standard value pair without being a standard reference.

Our understanding of the relationships between iterator pairs, value pairs, and reference pairs, makes our design simpler than the alternative. It is argued that a recognition of these relationships is useful in many other generic programming contexts as well.


C++ iterators reference types 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Comsol homepage,
  2. 2.
  3. 3.
    Williams, A.: Pairing off iterators. Overload (2001), Avaliable at: (2005-04-07)
  4. 4.
    The C++ Standard, Incorporating Technical Corrigendum No. 1.2 edn. John Wiley & Sons, Ltd. (2003)Google Scholar
  5. 5.
    Abrahams, D., Siek, J., Witt, T.: New iterator concepts (2003),
  6. 6.
    Musser, D., Saini, A.: STL Tutorial and Reference Guide. Addison-Wesley, Reading (1996)Google Scholar
  7. 7.
    C++ standard library active issues list, revision 35 (2005), (2005-03-04)
  8. 8.
    Alexandrescu, A.: Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley, Reading (2001)Google Scholar
  9. 9.
    Musser, D.: Introspective sorting and selection algorithms. Software–Practice and Experience 8, 983–993 (1997)CrossRefGoogle Scholar
  10. 10.
    Abrahams, D., Gurtovoy, A.: C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and beyond. Addison-Wesley, Reading (2005)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Krister Åhlander
    • 1
  1. 1.Department of Information TechnologyUppsala UniversityUppsalaSweden

Personalised recommendations