insert(3C++)


insert -- insert an element into a sorted array

Synopsis

   template <class T>
   T* insert(T val, T* b,T* e);
   template <class T>    
   T* insert_r(int (*rel)(const T*,const T*),T val,
        T* b,T* e);

Assumptions

(1) For the plain version, T::operator< defines a total ordering relation on T and the array is sorted w.r.t. that relation.

(2) For the relational version, rel defines a total ordering relation on T and the array is sorted w.r.t. that relation.

(3) T has operator=.

Description

These functions assign the value val to the location in the sorted array that contains the leftmost element greater than val and returns a pointer to this location. Before making the assignment, all elements from that location to the end of the array are moved one location to the right.

   template <class T>
   T* insert(T val,T* b,T* e);

Uses T::operator< to define the ordering relation.

   template <class T>
   T* insert_r(int (*rel)(const T*,const T*),T val,
         T* b,T* e);

Uses rel to define the ordering relation.

Complexity

If N is the size of the array, then complexity is O(N). At most lgN tests of the ordering relation and at most N assignments are done.

Notes

Because a Block (see Block(3C++)) can always be used wherever an array is called for, Array Algorithms can also be used with Blocks. In fact, these two components were actually designed to be used together.

References

Array_alg(3C++), Block(3C++) set_insert(3C++)
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 25 April 2004