(construction notes) ADT and OOP

ADT And OOP

1. ADT（Abstract Data Tyoe） Four types of operations

ADT There are four main operations ：
Constructors （creators）： Create a new object
Producer （producers）： Produce a new object from an existing object
viewer （observers）： Return an object of different types from an abstract object type
（ Very simple chestnuts , Is a variety of getXX（） Method ……）
Valuer （mutators）： Methods of changing object properties . Usually back to void（ If the return value is void It must mean that he has changed some internal states of the object , It is also possible to return non null types ）
There may be some confusion between constructors and producers , For constructors , It may be an implemented constructor or static function , For the producer, it starts from the existing objects , Create a new object . The following examples can help understand ：

2. Indicates independence （representation independence)

Indicates independence ： client （client） Use ADT There is no need to consider how it is implemented internally ,ADT Changes in internal representation should not affect external spec And the client .

To put it bluntly, don't let the client know the specific logic of your code , They just need to know what the code input should be , It's enough to give legal input and output .

Also note that unless ADT The operation indicates the specific pre and post conditions , Otherwise you can't change ADT The internal representation of ——spec Specifies the implementer of the client domain code （implementer） A contract between .

Of course, it's not clear , And a chestnut, right ：

As can be seen in the java doc It does not explain how the code is implemented internally （ The specific implementation is not important here ~）, Customers only need to know what this program does , What kind of output the legal input will get is enough .

12. invariant （Invariants）、 Indicates a leak

invariant （invariants）：

It is right at all times . Should be determined by the ADT To be responsible for its invariants , It has nothing to do with the people and behavior of the client .（ Generate a ‘person’ Objects can never be set by the client person Have two legs , The customer set three legs as ok , What if it's set to four, five, six, seven, eight legs , How terrible ！）

Why do we need invariants ： Keep the program correct , Easy to find mistakes .

No amount of saliva is worth a chestnut ：

First, this is the code ：

Let's see how our excellent client is used ：

Oh my god ！ Why did this bastard change his name ？！ Yes, this twitter was stolen …… Steal the plan and be angry ？

This leads to the following concepts ：

Indicates a leak （representation exposure）：

It divulges the data inside the code to the client , This not only affects invariance , It also affects the representation independence （ Because the customer knows the internal implementation of your code , Then he can do some operations on your code that you don't want to see . alas ~ It's really awful ！）, Of course, the official explanation is ： You cannot change its internal representation without affecting the client .（ obscure ……）

Maybe you said that I modified the variable as private, And then add final, It won't change like this . However …… Ha ha Da

Let's take an example ：

Pay attention to the red line , here Date It's a mutable The type of , In this way, the reference to the member variable will not change . However, for its internal value ？

Look at the snapshot at this time ：

Even if you are final How about decoration ？ Fickle in the bone , Change or change . So for this mutable Variable , Defensive copy also plays an important role ：

So everything will be fine , In addition, remember to modify the construction method . Of course, it has been explained in detail in the previous section , There will be no more redundancy ……

13. For invariants RI、 Abstract functions AF

    First of all, let's introduce the representation space R And abstract space A：
    Space （the space of representation values）： Indicated value （rep value ） Space , Consists of the values of the actual implementation entity . In general ADT The expression of is relatively simple , Sometimes it will be expressed in a more complex way .
    Abstract space （the space of abstract values）： The space formed by abstract values ： Values that users see and use .
    ADT Implementers focus on presentation space R, Users focus on abstract space A.

Be careful ：R->A It must be a full shot , But it can not be a single shot .

Abstract functions ：R And A Function of the mapping relationship between .

For invariants RI： Something specific “ Express ” Whether it is “ legal ”, Also can put the RI As a subset of all the representation values , It contains all legal representation values or describes what is “ legal ” A condition that represents the value of .

in addition , Different internal representations require different designs AF and RI, Choose a specific representation R, Then specify that a subset is “ legal ” have to RI, And make a “ explain ”AF—— That is, how to map to values in abstract space .

Even the same R、 alike RI, There may also be different AF, namely “ Explain different ”.

Design ADT step ：

Select the representation space R And abstract space A
give RI—— Legal representation value
How to interpret legal representation values —— mapping AF

Similarly, giving more definitions is not as rewarding as an example ：

Let's explain this example ：

first RI：s The elements in the sequence are sorted from small to large , And it is not allowed to be the same

the second RI：s The length of is odd ,s The elements in the sequence are sorted from small to large , But allow the same

Third RI：s Elements in a sequence are not allowed to be the same

The fourth one RI：null

Now let's look at it add Method ： Its presence s A... Is added c character , So according to c The first, second and third are not supported if they are different RI.

Then come to see remove Method ： Be careful , Only the first one is deleted in this method c, For after c Don't delete , So if s Duplicate character in , Then I'm not satisfied remove Of spec. So it only supports one or three .

Another chestnut ：

At first glance, it seems that all four are ok , But in fact, pay attention to the implementation of this method , Here, the traversal operation is to scan two characters at a time , So when s When it is an odd number of characters , A null pointer exception will occur , So you can only choose the second .

summary ：
Different internal representations , Need to design different AF And RI.

Choose a specific representation R, Then it is legal to specify a subset RI, And explain each value in the subset ”AF“ That is, how to map to values in abstract space .

alike R、 alike RI, There may also be this different AF, That is, the explanation is different .
————————————————
Copyright notice ： This paper is about CSDN Blogger 「 Nanke Hepu on the string 」 The original article of , follow CC 4.0 BY-SA Copyright agreement , For reprint, please attach the original source link and this statement .
Link to the original text ：https://blog.csdn.net/qq_37549266/article/details/80707151