Representational Equality

[This page is being used to collaborate on a paper. You are welcome to read and comment on it, but consider it a work in progress, not a final product.]

Title: Representational Equality

Authors: Sean Parent, Alex Stepanov

Contents

1. Abstract
2. Introduction
3. Body
4. Proposal
5. Related Work
6. Acknowledgments

Abstract

Introduction

Body

Definitions -

identical

I(a, b) - same instance, &a == &b representationally equal: R(a, b) - representation is equal logically equal: L(a, b) - all corresponding parts are equal

locational less than

std::less<T*>(&a, &b) representationally less than:

I ==> R ==> L

I - complexity

small, constant time (pointer comparison)

R - complexity

average small constant time, worst case O(area)

L - complexity

may be significant - time to find corresponding parts

identical

&a == &b

representationally equal

R(a, b) ==>

Desired attributes for logical less symmetric with other operators - esp. + and *

Examples of types where < and/or == is problematic:

float and double - reason is NaN complex - operator < not defined because of symmetry with operator*() solution is provide representational_less priority_queue - operator == and operator < not defined because of complexity and resource consumption

Proposal

Related Work

Acknowledgments